Author |
Topic: Three Dimensional Random Walk (Read 11643 times) |
|
River Phoenix
Guest
|
 |
Re: Three Dimensional Random Walk
« Reply #50 on: May 22nd, 2005, 1:52pm » |
 Quote  Modify
 Remove
|
Maybe the real question is how to solve the recursion
f(n) = 0.5 f(n-1) + 0.5 f(n+1)
f(0) = 1
f(infinity) = 0
Where we are looking for f(1)
|
|
 IP Logged |
|
|
|
River Phoenix
Guest
|
|
Re: Three Dimensional Random Walk
« Reply #51 on: May 22nd, 2005, 2:25pm » |
Quote Modify
Remove
|
I believe that the actual answer is 1, and that I incorrectly stated f(infinity)=0 when f(infinity)=1. Here's my reasoning:
| hidden: |
f(1) = .5 f(0) + .5 f(2)
f(2) = .5 f(1) + .5 f(3)
= .5 [.5 f(0) + .5 f(2)] + .5 f(3)
f(2) = (1/3) f(0) + (2/3) f(3)
By induction, assume f(n) = 1/(n+1) f(0) + n/(n+1) f(n+1).
Clearly it is true for the base case.
Then f(n+1) = .5 f(n) + .5 f(n+2)
= .5[1/(n+1) f(0) + n/(n+1) f(n+1)] + .5 f(n+2)
f(n+1) = 1/(n+2) f(0) + (n+1)/(n+2) f(n+2)
So the formula holds for all n. We can say that
f(0) = (n+1) f(n) - n f(n+1)
As n->infinity, f(n)=f(n+1)
So f(0) = (n+1-n)f(n) = f(n)
But f(0) = 1, so f(infinity) = 1
It's very unintuitive that the particle infinitely away from the origin has probability 1 of reaching it, so somebody please point out to me the error in my proof if it is indeed wrong. I think that intuitively, the reason it works if it does work has to do with an infinite some of fractional powers of 2.
We can also easily prove by induction that f(n) = 1/n f(1) + (n-1)/n f(n+1) for all n
So f(1) = n f(n) - (n+1) f(n+1) for all n
As n->infinity, we have that:
f(1) = f(n) = f(infinity) = 1
In fact f(n)=1 for all n.
Any good?
|
|
|
IP Logged |
|
|
|
River
Guest
|
|
Re: Three Dimensional Random Walk
« Reply #52 on: May 22nd, 2005, 2:38pm » |
Quote Modify
Remove
|
Sorry, I see that I was foolish, since you may also move to another point which is the same number of units from the origin, since its 3d. probably its still a recursion though.
|
|
IP Logged |
|
|
|
River Phoenix
Guest
|
|
Re: Three Dimensional Random Walk
« Reply #53 on: May 22nd, 2005, 5:08pm » |
Quote Modify
Remove
|
Sorry, my original inclination was correct. Each point has 6 exits, 3 heading 1 unit closer, and 3 heading 1 unit further form the origin.
In 1-d, 2-d, and 3-d, an infinite random walk will visit every point of space. For some dimension (I think the fourth) and above, this is not true.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Three Dimensional Random Walk
« Reply #55 on: May 23rd, 2005, 1:18am » |
Quote Modify
|
on May 22nd, 2005, 5:13pm, River Phoenix wrote:
I think the same mistake was made earlier in this thread. The .34 answer is for the random walk in which only one coordinate changes with each step; in this problem, all three coordinates are changed with every step.
However, you've made some mistakes with the first problem, so let me address that.
Quote:| Can this be simplified to a 1-dimensional random walk, since a particle which is, say, 7 steps from the origin, is symmetrical with every other unit which is 7 steps from the origin. Then it can probably be solved by a recurrence relationship? |
|
What throws a wrench in the works is the fact that different points have different numbers of paths going inwards and outwards: most points have 3 paths inward and 3 paths outward, but points on the axes have only one path inward, and the other points on the axial planes have only two paths inward. This is enough to kill the symmetry argument.
It's interesting that "nearly all" points have 3 paths inward and 3 outward, so it looks like your argument should "almost" work, and the situation should be similar to a walk in one dimension. However, while the answer for one and two dimensions is 1 (the walk almost surely returns to the origin), the little differences drop the probability to barely 1/3!
Quote:Maybe the real question is how to solve the recursion
f(n) = 0.5 f(n-1) + 0.5 f(n+1)
f(0) = 1
f(infinity) = 0
Where we are looking for f(1) |
|
I don't really know what you are talking about here; it looks sort of like a description of a random walk, but I can't make sense of it. For what it's worth, the solution to the first two lines is f(n) = 1 + cn, for some constant c.
We can talk about your next post after you clarify what f means.
Quote:| In 1-d, 2-d, and 3-d, an infinite random walk will visit every point of space. For some dimension (I think the fourth) and above, this is not true. |
|
Note that we have the same situation for higher dimensions: for nearly all points, there are n paths inward and n paths outward, but the probability of returning to the origin goes to 0!
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print