wu :: forums « wu :: forums - Three Dimensional Random Walk » Welcome, Guest. Please Login or Register. Jan 21st, 2022, 9:12am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register wu :: forums  riddles  hard (Moderators: Grimbal, Eigenray, ThudnBlunder, towr, Icarus, william wu, SMQ)  Three Dimensional Random Walk « Previous topic | Next topic » Author Topic: Three Dimensional Random Walk  (Read 11196 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
River Phoenix
Guest  Re: Three Dimensional Random Walk   « Reply #54 on: May 22nd, 2005, 5:13pm » Quote Modify Remove

Many apologies for the quintuple post. But something I did was indeed wrong (can anybody point it out).

http://mathworld.wolfram.com/RandomWalk3-Dimensional.html 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:
 Many apologies for the quintuple post. But something I did was indeed wrong (can anybody point it out).   As it turns out the answer is about .34 :   http://mathworld.wolfram.com/RandomWalk3-Dimensional.html

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

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »