wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Three Dimensional Random Walk
        
(Message started by: william wu on May 23^rd, 2003, 3:54am)

Title: Three Dimensional Random Walk
Post by william wu on May 23^rd, 2003, 3:54am

A particle starts at origin O in three-space. Think of the origin as centered in a cube 2 units on a side. One move in this walk sends the particle with equal likelihood to one of the eight corners of the cube. Thus, at every move the particle has a 50-50 chance of moving one unit up or down, one unit east or west, and one unit north or south. If the walk continues forever, find the fraction of particles that return to the origin.

Title: Re: Three Dimensional Random Walk
Post by tohuvabohu on May 23^rd, 2003, 9:44am

If the walk is infinite, then every particle will eventually visit every possible locus, including the origin, no?

Title: Re: Three Dimensional Random Walk
Post by towr on May 23^rd, 2003, 1:52pm

the cube was only to illustrate how the particle moves (+- one unit along all dimensions)

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on May 23^rd, 2003, 1:57pm

Quote:

the cube was only to illustrate how the particle moves (+- one unit along all dimensions)

So, is your interpretation that it is an infinite 3D lattice?
(That is hardly a Medium puzzle.)

Title: Re: Three Dimensional Random Walk
Post by phobos on May 23^rd, 2003, 8:16pm

Is it possible to move beyond the lattice? Or the particle is confined within the cube.

Suppose there's an infinite lattices, then the fraction coming back to origin for particles one walk away 1/8, for two walk it's 1/64, for three it's 1/512, and so on. Then for infinite number of movements, the fraction coming back is the sum of:
1/8 + 1/64 + 1/512 + .....
Around 14.3% will eventually come back.

Title: Re: Three Dimensional Random Walk
Post by tohuvabohu on May 23^rd, 2003, 9:40pm

The odds are much higher than 14%.
After one move the particle will be at one of the 8 corners of a cube. After 2 moves it will be in the center of one of a 3x3x3 cube of cubes, with a 1/8 chance of being in a corner cube, 3/8 chance of an edge cube, 3/8 chance of a side-center cube, and 1/8 chance of being at the origin.
After 3 moves it will be at one of the corners of those 27 cubes: 1/64 chance of an outer corner, 9/64 of an outer edge, 27/64 of an outer side-center corner, 19/64 of being back at the 8 corners of the inner cube (not counting the particles that have already returned to origin).
So on the fourth move there is a 19/512 chance of hitting the origin. And 260 out of 512 particles are still within 2 moves from the origin.
I'm too tired to figure it out any farther, But I'd estimate that after 6 moves the percentage of particles that have returned to origin is about 18%. And although the rate of return to origin will continue to decrease, (eg. maybe another 1% at origin on move 8), that level of decrease will diminish, because the percentage of particles that move only farther away from origin will get smaller and smaller, and there will be more echo back.
We'll have to get a real mathematician to figure it out to infinity.

Title: Re: Three Dimensional Random Walk
Post by phobos on May 23^rd, 2003, 10:07pm

Ahhh..ok now that I think of it, I'd oversimplified the problem.
I haven't quite catch tohu's logic though..

Title: Re: Three Dimensional Random Walk
Post by tohuvabohu on May 24^th, 2003, 7:57am

I should probably wait for TandB to respond, since he doesn't think this deserves medium difficulty, but here's my analysis:
The particle always moves diagonally, so it alternates from a cube corner after odd moves to a cube center after even moves.
Move one: 8 possible loci. They're symmetrical so treat 'em as one. Coordinates (1,1,1).

Move two: 27 possible loci.
1/8 back to origin,
1/8 to (2,2,2)
3/8 to (2,2,0) (and it's symmetrical equivalents)
3/8 to (2,0,0)

Move three: 64 loci,
From the 1/8 at (2,2,2),
1/8 return to (1,1,1),
1/8 to (3,3,3)
3/8 to (3,3,1)
3/8 to (3,1,1)
From the 3/8 at (2,2,0),
2/8 to (1,1,1)
2/8 to (3,3,1)
4/8 to (3,1,1)
From the 3/8 at (2,0,0)
4/8 to (1,1,1)
4/8 to (3,1,1)
That's 19 at (1,1,1), 1 at (3,3,3), 9 at (3,3,1), and 27 at (3,1,1)

Move 4: 125 loci,
Summary 1/512 at (4,4,4), 3 at (4,4,2), 48 at (4,2,2), 72 at (4,2,0), 27 at (4.0,0), 56 at (2,2,2), 120 at (2,2,0), 84 at (2,0,0) and 19/512 at origin.

Move 5 summary
1 out of 4096 at (5,5,5), 6 at (5,5,3), 3 at (5,5,1), 57 at (5,3,3), 246 at (5,3,1), 300 at (5,1,1), 108 at (3,3,3), 651 at (3,3,1), 1284 at (3,1,1), 632 at (1,1,1)

Move 6
632/32768 at origin, 3180 at (2,0,0), 5115 (2,2,0), 2675 (2,2,2), 1584 (4,0,0), 4716 (4,2,0), 3513 (4,2,2), 900 (4,4,0), 1344 (4,4,2), 172 (4,4,4), 300 (6,0,0), 846 (6,2,0), 603 (6,2,2), 252 (6,4,0), 378 (6,4,2), 72 (6,4,4), 3 (6,6,0), 9 (6,6,2), 9 (6,6,4), 1 (6,6,6)

move 7
10970/262144 at (1,1,1) Therefore move 8 will have 10970 out of 2097152 returning to origin, and the percentage within 2 steps of the origin has dropped to about 9%. So I guess the number reaching the origin will be very low after this point. I get a total return of 18.66% after 8 moves, and I suppose it might top out somewhere around 19 or 20%. So much for my theory that everybody goes home again.

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on May 24^th, 2003, 8:54am

Quote:

I should probably wait for TandB to respond, since he doesn't think this deserves medium difficulty...

tohuvabohu, I meant that I think it is a Hard puzzle. To analyse it exactly requires advanced mathematics.

Title: Re: Three Dimensional Random Walk
Post by tohuvabohu on May 24^th, 2003, 10:24am

I'm glad it's hard, because then I don't feel so bad about the mistakes I made at move 4 that make all the numbers after that incorrect. Here's the corrected version:

Move 4:
Summary 1/512 (4,4,4), 12 (4,4,2), 9 (4,4,0), 48 (4,2,2), 72 (4,2,0), 27 (4.0,0), 56 (2,2,2), 120 (2,2,0), 84 (2,0,0) and 19/512 at origin.

Move 5 summary
1 out of 4096 at (5,5,5), 15 at (5,5,3), 30 at (5,5,1), 75 at (5,3,3), 300 at (5,3,1), 300 at (5,1,1), 117 at (3,3,3), 678 at (3,3,1), 1284 at (3,1,1), 632 at (1,1,1)

Move 6
632/32768 at origin, 3180 (2,0,0), 5142 (2,2,0), 2711 (2,2,2), 1584 (4,0,0), 4824 (4,2,0), 3666 (4,2,2), 1008 (4,4,0), 1524 (4,4,2), 208 (4,4,4), 300 (6,0,0), 900 (6,2,0), 675 (6,2,2), 360 (6,4,0), 540 (6,4,2), 108 (6,4,4), 30 (6,6,0), 45 (6,6,2), 18 (6,6,4), 1 (6,6,6)

move 7
has 16175/262144 at (1,1,1) Therefore move 8 will have 16175 out of 2097152 returning to origin, and the percentage within 2 steps of the origin has dropped to about 16%. So I guess the number reaching the origin will be very low after this point. I get a total return of 18.91% after 8 moves, and I suppose it might top out somewhere around 19.5%.

Title: Re: Three Dimensional Random Walk
Post by towr on May 24^th, 2003, 3:49pm

so far I have
1 0.125
3 0.162109
5 0.181396
7 0.193658
9 0.202324
11 0.208864
13 0.214025
15 0.218231
17 0.221744
19 0.224736
21 0.227324
23 0.229592
25 0.2316

with some help from a little program.. (only each second move can be a return move)
I'll check the convergence tomorrow..

Title: Re: Three Dimensional Random Walk
Post by tohuvabohu on May 24^th, 2003, 4:50pm

Hmm, that's what happens when you're throwing that many numbers around. I had Move 6 correct, but my mind just stopped working when I figured move 7 without writing it all out. And that made me think the rate was dropping faster than it really was. Towr's figures are the same as I get when I finally do it right (although I only went to move 10, which he calls 9 ).

Title: Re: Three Dimensional Random Walk
Post by Leonid Broukhis on May 24^th, 2003, 5:27pm

I believe there is some overcomplication. Consider a one-dimensional random walk (starting at 0, +/-1 at every step equiprobably). What is the probability that after 2N moves we're back at origin? That's
A = C(N, 2N)/2**2N, right?
Now we have to be back at origin on all 3 axes; that's B = A**3.
And the result is X = sum(1, inf) B = 1/e.

I obtained the value of 1/e by observing the behavior of partial sums;
e.g. for
N = 100 X = .35742058588327320639
N = 150 X = .36395057008128140808
N = 200 X = .36785398757806507039
1 / e = .36787944117144232159

Title: Re: Three Dimensional Random Walk
Post by Leonid Broukhis on May 25^th, 2003, 12:37am

You're right, we're only interested in the number of paths that end at origin at 2N moves but not earlier to avoid counting some particles more than once.
First I thought that the number of paths is C(N,2N) - 2*sum(i=1,N-1)C(i, 2i), but it does not feel right.
And in this corrected case the third power will be wrong. Let's say the fraction of paths of length 2N that end at origin on the step 2N but not earlier is D(N), then for 3 dimensions the probability is 3*D(N)*A(N)**2 (for any of the 3 dimensions we come to the origin the first time, and for the other 2 we come to the origin somehow). Does this look better?

Title: Re: Three Dimensional Random Walk
Post by towr on May 25^th, 2003, 2:06am

The maximum for a really random discrete walk in 3d (one move in any direction) is about 34% (mathworld).
Here we are dealing with a more limited case, I think, because you make 3 moves in 3 orthogonal directions at every step.
So it should be less than 34%.

Title: Re: Three Dimensional Random Walk
Post by towr on May 25^th, 2003, 4:41am

Here are some plots of the fraction of particals that has returned for the first time at step i

http://tcw2.ppsw.rug.nl/~towr/3dwalk.png http://tcw2.ppsw.rug.nl/~towr/3dwalk2.png

and the total fraction of particals that has return at least once before or on step i

http://tcw2.ppsw.rug.nl/~towr/3dwalk_sum.png http://tcw2.ppsw.rug.nl/~towr/3dwalk_sum2.png

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on May 26^th, 2003, 9:24am

Quote:

...?because you make 3 moves in 3 orthogonal directions at every step.

Where in the question does it say that?

Nice plots, by the way.

Title: Re: Three Dimensional Random Walk
Post by wowbagger on May 26^th, 2003, 9:38am

I think towr refers to this part of the problem statement:

on 05/23/03 at 03:54:58, william wu wrote:

One move in this walk sends the particle with equal likelihood to one of the eight corners of the cube.

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on May 30^th, 2003, 10:10am

I believe required probability is that of finding the probability of 3 independent 1-D random walks arriving back at the origin simultaneously.

Chance of this happening after each have taken 2N steps

= (^2NC_N)³ * (1/2)^6N

00
So probability = SIGMA (^2NC_N)³ * (1/2)^6N
N=1

Title: Re: Three Dimensional Random Walk
Post by wowbagger on May 30^th, 2003, 10:26am

on 05/30/03 at 10:10:02, THUDandBLUNDER wrote:

00
So probability = SIGMA (^2NC_N)³ * (1/2)^6N
N=1

Isn't this the same answer Leonid posted (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1054069556;start=0#13) a few days ago?
Well, apart from the fact that he posted it only once. ::)

Title: Re: Three Dimensional Random Walk
Post by Leonid Broukhis on May 30^th, 2003, 12:43pm

As I admitted earlier, 1/e is wrong because I was counting a particle as many times as it returned to the origin, instead of once. For the correct answer we need to know the probability of returning at the origin after 2N steps [i]but not earlier[/b].

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on May 31^st, 2003, 12:05am

I get 0.3126526... for N = 1 to 1000

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Jun 11^th, 2003, 10:20am

I have come up with a formula for D(N), the number of particles that return to the origin at time 2N but not before (in one dimension). To do this, first I examined E(N), the number of particles at time 2N that have not yet returned to the origin. Surprisingly, E(N) = ^2NC_N. To find the number of particles that return to the origin at time 2N, we simply find the total number of particles that hadn't returned at 2N-2, multiply by 4, then subtract the number that still haven't returned by 2N.

D(N) = 4*E(N-1) - E(N)
= 4*^2N-2C_N-1 - ^2NC_N
= ^2NC_N(4N²/(2N*(2N-1)) - 1)
= ^2NC_N(2N/(2N-1) - 1)
= ^2NC_N/(2N-1)

Now it has been suggested that at time 2N, exactly 3D(N)A²(N) particles reach the origin for the first time. However, this formula double-counts the particles that reach the origin for the first time in more than one axis (e.g. for N=1, D(N)=A(N)=2, so it falsely gives Q(1)=24, which gives P(1)=0.375). To correct this, I use this formula for Q(N), the number of particles returning to the origin for the first time at time 2N:

Q(N) = 3D(N)A²(N) - 3D²(N)A(N) + D³(N).

Now we can find the probability P(N) that a particle returns to the origin by 2N steps, knowing that there are 2^3*2N possible particle paths after 2N steps:

P(N) = sum_i=1..NQ(i)/2⁶ⁱ

However, doing the sum on a spreadsheet, I find that P(500)=20.226%, which does not match the numbers other people are getting. So I'm wondering: how did you get your numbers? Am I on crack here? Do towr's numbers match T&B's?

Title: Re: Three Dimensional Random Walk
Post by towr on Jun 11^th, 2003, 10:41am

I only went to n = 200, so I'm not sure. But from my graph I would say I end up lower at N=1000 than Thud's 0.31..

I'll put my data-file on the web as well..

* newly returning particle fraction at each step (http://tcw2.ppsw.rug.nl/~towr/3dwalk.dat)
* accumulation of particles (http://tcw2.ppsw.rug.nl/~towr/3dwalk_sum.dat)

* C++ source for my simulation (http://tcw2.ppsw.rug.nl/~towr/3d.cc) (not the most efficient way, but simple)

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Jun 11^th, 2003, 11:59am

towr,

It seemed to me that you two predicted different answers at 1000.

The numbers you give definitely don't match mine, except for the first two values. Since you get yours through simulation, I would expect that yours are right, and tohuvabohu gets the same result.

I'll try to check my formula, but I really think I've got D(N) working properly...

Oh. I think I may have figured out why my formula doesn't work. It doesn't take into account that a particle returning to the origin for the first time may be not be returning to the origin for the first time in any of the three directions. Consider the following particle path:

0,0,0 -> 1,1,1 -> 0,2,2 -> 1,1,1 -> 2,0,2 -> 1,1,1 -> 2,2,0 -> 1,1,1 -> 0,0,0

This one returns to the origin in all three dimensions individually before returning to the origin in all three simultaneously. Yikes, this complicates things much more...

Title: Re: Three Dimensional Random Walk
Post by Leonid Broukhis on Jun 11^th, 2003, 5:48pm

I ran a simulation of 10000 points for 100000 steps four times and got 28.27%, 28.11%, 27.42%, and 28.57%.

Another run of 100000 points for 100000 steps ended with 28163 points returning.

JFYI: The same run in 2 dimensions results in 78024 points returning.

Title: Found Recurrance Relation! w0000007!
Post by James Fingas on Jun 12^th, 2003, 6:05am

Haha! I have found a way to make this problem mathematically tractable!

2) After two moves, exactly 1/8 of the particles have returned to the origin. This accounts for 8 out of 64 particles. This gives a fraction of 0.125.

4) After four moves, there are (⁴C₂)³=6³=216 particles at the origin. Some of these are returning from visiting the origin on move 2. But we know exactly how many are doing this: 8 for each particle that was at the origin on move 2, for 64 particles total. Therefore 216-64=152 particles are returning for the first time. This gives a fraction of ~0.03711.

6) After six moves, there are (⁶C₃)³=20³=8000 particles at the origin. Some of these first visited the origin on move 2, and some first visited the origin on move 4. But we know exactly how many: 8*216 first visited on the second move, and 152*8 first visited on the fourth move. This leaves 8000-8*216-152*8=8000-1728-1216=5056 particles returning for the first time. This gives a fraction of ~0.019287.

8) After eight moves, there are (⁸C₄)³=70³=343000 particles at the origin. Some of these first visited on moves 2,4, or 6. But again we know exactly how many: 8*8000=64000, 152*216=32832, and 5056*8=40448 respectively. This means 343000-64000-32832-40448=205720 particles total return to the origin for the first time. This gives a fraction of ~0.0122619.

This can be extended to an arbitrary number of steps, and takes O(N²) computational power. Working this out on a spreadsheet my numbers exactly match towr's! This method allows us to come up with a recurrance relation for the number of particles that eventually return to the origin.

Let us define M(N) = (^2NC_N)³. Now define the sequence Q(N) which gives the number of particles that return to the origin for the first time on step 2N:

Q(N) = M(N) - M(N-1)Q(1) - M(N-2)Q(2) - M(N-3)Q(3) - M(N-4)Q(4) - ... - M(1)Q(N-1)

It may be possible to solve the recurrance relation explicity for Q(N), or it may be possible to calculate the probability without doing that:

P = sum_n=1..inf Q(n)/64ⁿ

Title: Re: Three Dimensional Random Walk
Post by THUDandBLUNDER on Jun 13^th, 2003, 7:39pm

To further confuse things, if my (and Leonid's) answer includes not only points that arrive back simultaneously once from 3 independent 1-D walks, but also counts ones that arrive back together again 2, 3, 4, 5...... times, then don't we just have an infinite geometric series whose sum is mine and Leonid's answer?

That is, x/(1-x) = 0.3126526...

This gives x = 0.2381838... :-/

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Jun 16^th, 2003, 1:45pm

T&B,

Looking at towr's code, I'm pretty sure it gives correct numbers. I don't know about your simulation though. The problem with this one is that you need to remove those particle paths that return to the origin; otherwise, they'll return again and again and spoil your results.

This is easy to do in a simulation, but hard to do in the math. My method with Q and M works (or reproduces towr's results anyways). A straight geometric series can't do the trick because the particles can return once or twice or a thousand times, and the probabilities are all based on the lengths of time between the returns to zero. You can calculate the probabilities directly, but it's O(N³) and rather complex, versus O(N²) for my method. To see what I mean, expand my method in terms of just the Ms: it gets hairy pretty fast!

Title: Re: Three Dimensional Random Walk
Post by Leonid Broukhis on Jun 16^th, 2003, 2:51pm

on 06/13/03 at 19:39:29, THUDandBLUNDER wrote:

No, my simulation drops a point from the simulated set as soon as it reaches the origin.

Title: Re: Three Dimensional Random Walk
Post by Barukh on Aug 20^th, 2003, 5:09am

There are quite a few sites talking about this problem, for example: http://www.mathsoft.com/mathresources/constants/discretestructures/article/0,,2220,00.html.
It says that the sought probability is 0.340537...

Let P(D) be the probability for the particle to get back in D-dimensional space, and Q(D) = 1 - P(D). Let also p_N be the probability that the 1-dimensional walk gets to the origin after 2N steps (not necessarily for the first time!). Then, the particle does not get to the origin in the D-dimensional space if it doesn't get to the origin after any finite number of steps. The probability not to be at the origin after 2N steps is 1 - p_N^D, so

Q(D) = ₁PROD^oo (1 - p_N^D).

We know that p_N = ^2NC_N/2^2N. Thus, p_N+1/p_N = (2N-1)/2N. So, computationally, it takes O(N) time and constant space. The simulations show the following numbers:

N P(3)
-------------------
10^3 0.32487
10^4 0.33010
10^5 0.33174
10^6 0.33226
10^7 0.33243
10^8 0.33248
10^9 0.33249

Although the numbers are quite close to the theoretical value, the approaching rate is very slow... Or, there is an error in reasoning?..

That the Leonid's and THUDandBLUNDER's formula is not correct, is seen from the following considerations: the formula should work for any number of dimensions, only powers change. However, for D=1 and D=2 the infiinite sum diverges and cannot be a probability. But it is handy in the following approach (taken from a nice little Mosteller's book `Fifty Challenging Problems in Probability').

Let X_N be a random variable that takes value 1 if the particle is at the origin after 2N steps, and 0 otherwise, and let X = ₁SUM^oo X_N. The expected value E[X_N] = p_N^D, so E[X] is just the Leonid's and THUDandBLUNDER's formula!

It is easy to see that E[X] is an expected value of returns until particle is lost forever. Now, we may associate the random walk with flipping of the biased coin, where P(D) is the probability to get heads, Q(D) is the probability to get tails. Then, 1 + E[X] is an expected number of flips until the first tails. So, Q(D) = 1/(1 + E[X]). The simulation shows the following numbers:

N P(3)
-------------------
10^3 0.27633
10^4 0.28037
10^5 0.28164
10^6 0.28204
10^7 0.28217
10^8 0.28221
10^9 0.28222

Hmm, the numbers are much lower than the theoretical value. Is this because of the program bug? convergence rate? floating point errors? Whatever it is, I cannot see the flaw in the reasoning...

This approach also clearly shows why P(D) is 1 for D=1, 2 and <1 for higher dimensions. It is clear that P(D) = 1 iff E[X] = oo. Using Stirling's formula, one gets that E[X_N] ~ N^-D/2, and the sum diverges only for D=1, 2.

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Aug 20^th, 2003, 6:57am

Barukh,

I think the reason your formula

Q(D) = [prod]_N=1..[infty](1-p_N^D)

does not converge to the correct answer is that it assumes that the probability of a particle returning on step N is independent of the probability that it returned on step N-1. If a particle doesn't return by step N it is less likely than average to return by step N+1. However, I would have said that because of this, you would predict an answer lower than the actual answer...

Please note that the answer 0.340537... is probably not relevant to this question, because it assumes you move in one of six directions (+x, -x, +y, -y, +z, -z), while we are allowed to move in eight directions (+++, ++-, +-+, +--, -++, -+-, --+, ---). This was noted by TnB a few posts up the page. He supposed that our answer would be less than 0.340537 because of the larger 'branching factor'.

Our best guess at the probability is from simulation, giving at least 28%, but not likely as high as 34%.

Your criticism of Leonid's and TnB's answer could also be applied to your own. Although you predict that Q(1) = 0 and Q(2) = 0, I am quite confident that the number of particles that have never returned to the origin by step 2N for a 1D random walk is ^2NC_N, which is significantly larger than your answer.

Title: Re: Three Dimensional Random Walk
Post by Barukh on Aug 20^th, 2003, 10:44am

James,

on 08/20/03 at 06:57:55, James Fingas wrote:

You are right... I didn't think about this dependency...

on 08/20/03 at 06:57:55, James Fingas wrote:

Please note that the answer 0.340537... is probably not relevant to this question, because it assumes you move in one of six directions (+x, -x, +y, -y, +z, -z), while we are allowed to move in eight directions (+++, ++-, +-+, +--, -++, -+-, --+, ---). This was noted by TnB a few posts up the page. He supposed that our answer would be less than 0.340537 because of the larger 'branching factor'.

Agreed. I overlooked this.

on 08/20/03 at 06:57:55, James Fingas wrote:

Our best guess at the probability is from simulation, giving at least 28%, but not likely as high as 34%.

Still, I think the second approach is correct.

on 08/20/03 at 06:57:55, James Fingas wrote:

Your criticism of Leonid's and TnB's answer could also be applied to your own. Although you predict that Q(1) = 0 and Q(2) = 0, I am quite confident that the number of particles that have never returned to the origin by step 2N for a 1D random walk is ^2NC_N, which is significantly larger than your answer.

Sorry, I don't understand this.

Title: Re: Three Dimensional Random Walk
Post by towr on Aug 20^th, 2003, 10:55am

on 08/20/03 at 10:44:22, Barukh wrote:

Still, I think the second approach is correct.

That's the one which goes with the second table, right? which gives the +- 28% we expect. So I also think that's correct.
How did you simulate that? I tried to calculate all the probabilities and add them, but the rather large factorials just take too much time..

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Aug 20^th, 2003, 11:19am

towr,

You're talking about the problem with calculating p_N right? The simplest way to do this is with the recurrance relation p_N=p_N-1*(2N-1)/2N.

Title: Re: Three Dimensional Random Walk
Post by towr on Aug 20^th, 2003, 11:29am

hmm.. yes.. I should have read his post more carefully, it says so right there..

Title: Re: Three Dimensional Random Walk
Post by James Fingas on Aug 20^th, 2003, 12:59pm

on 08/20/03 at 05:09:28, Barukh wrote:

It is easy to see that E[X] is an expected value of returns until particle is lost forever. Now, we may associate the random walk with flipping of the biased coin, where P(D) is the probability to get heads, Q(D) is the probability to get tails. Then, 1 + E[X] is an expected number of flips until the first tails. So, Q(D) = 1/(1 + E[X]). The simulation shows the following numbers:

Essentially, we are saying there is a well-defined probability Q(D) that a particle currently at the origin will never return. Whenever a particle departs from the origin, we flip a coin calculating whether or not it will ever come back. In this way, we get a geometrically-decreasing percentage of particles that keep coming back.

Particles return with probability P(D).

0: 1
1: P(D)
2: P(D)²
3: P(D)³
...

But E[X] manages to count all of these (except for N=0), so we just need to add 1 to E[X] and work backwards to find P(D).

Hmm ... it seems valid ... good work!

Title: Re: Three Dimensional Random Walk
Post by Sjoerd Job Postmus on Mar 21^st, 2005, 6:54am

I'll try and trow myself at this question.

Let me first analyse the 1D situation.

When I make 2x moves, exactly x of those need to go left, and the other x to go right.

if (x%2) -> FALSE, can not be done
if (!(x%2) -> Maybe...

When I make 2n moves, I have [hide](2n)! / (n!)^2[/hide] ways to reach the center. (From 2n moves, I choose n rights) I have 2^(2n) different options. So the probability for n:
[hide](2n)! / ((n!)^2 * 2^(2n))[/hide]

Now, if I do this in 3D, I would just have to multiply the probabilities.
For n moves, the prob. would be:
[hide]((2n)! / ((n!)^2 * 2^(2n)))^3[/hide]

Title: Re: Three Dimensional Random Walk
Post by Deedlit on Mar 27^th, 2005, 3:39am

I haven't read through all the replies, but for what it's worth here is one answer:

The desired probability is the probability that three simple random walks return to the x-axis simultaneously. To return to the x-axis for the first time at y=2n+2, the walk goes in one direction at the first step, stays on the same side and returns to +/-1 at 2n+1, and goes to zero at 2n+2. The middle part is equivalent to a nonnegative walk that returns to zero at 2n, and there are Catalan(n) = C(2n,n)/(n+1) ways of doing so. So the probability of returning at 2n+2 is

P(2n+2) = 2 * [C(2n,n)/(n+1)] / 2²ⁿ⁺²

So the required answer is

Sum_n=0^inf P(2n+2)³ = Sum_n=0^inf C(2n,n)³/[(n+1)³ 2⁶ⁿ⁺³]

Title: Re: Three Dimensional Random Walk
Post by Barukh on Mar 27^th, 2005, 5:55am

Deedlit, I think there is a problem with your formula: P(n) gives the probability of 3 independent processes returning to the origin after n steps simultaneously for the first time.

While the correct answer will take into account the fact that the first return requires at least one dimension to return for the first time, while other directions may return an arbitrary number of times. This is the point that makes the computation of the probability so difficult.

You may consider looking at my post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1054069556;start=20#30) where the method using indicator random variables is presented. As far I know, there was a consensus that this method gives the correct answer.

Title: Re: Three Dimensional Random Walk
Post by Deedlit on Mar 28^th, 2005, 7:25pm

Whoops! You're right of course. Using the expected value to find the probability looks right - I'm amazed I didn't know this already. I probably learned it before and forgot about it. :P

Title: Re: Three Dimensional Random Walk
Post by rmsgrey on Apr 4^th, 2005, 6:22am

on 03/27/05 at 05:55:46, Barukh wrote:

While the correct answer will take into account the fact that the first return requires at least one dimension to return for the first time, while other directions may return an arbitrary number of times. This is the point that makes the computation of the probability so difficult.

Ummm... Why can't all 3 co-ordinates return to 0 multiple times before the first return to (0,0,0)?

Title: Re: Three Dimensional Random Walk
Post by SWF on Apr 5^th, 2005, 5:48pm

The condition that a jump be made in each of three direction for every time increment, makes this equivalent to random jumps to nearest neighbors on a body centered cubic lattice.

The probability is found to be 1 - [pi]²/(4*A²) where

A = the integral from 0 to [pi]/2 of dt/sqrt(1 - (1/2)*sin²t)

(The complete elliptic integral of the first kind for 1/sqrt(2)). The probability works out to be 0.282229989...

Title: Re: Three Dimensional Random Walk
Post by Deedlit on Apr 6^th, 2005, 4:58pm

Nice - could you fill in some more details?

Title: Re: Three Dimensional Random Walk
Post by SWF on Apr 12^th, 2005, 7:26pm

Here is a summary of the method I used, which should work with all sorts of random walks in various types of lattices of any dimension. The same approach can also be used to find resistance between points in an array of resistors. Start with an N by N by N array of points (assume N is an even number). Let p(m,n,q) be the probability that a random walk starting at point (m,n,q) eventually arrives at point (N/2,N/2,N/2).

A point already there is certain to reach that point, so p(N/2,N/2,N/2) = 1. For motion with the given rules:
8*p(m,n,q) - p(m[pm]1,n[pm]1,q[pm]1])=f(m,n,q). The term with [pm] means plus or minus and represents 8 different terms, and f(m,n,q) equals zero for every (m,n,q) except for (N/2,N/2,N/2) where it equals some constant, B.

Use discrete Fourier Transform: G(w)=sum(g(j)*exp(-2[pi]i*w*j/N), where sum is on j from 0 to N-1. Take discrete Fourier Transform of the expression for f(m,n,q) three times summing over m, n, and q. Some algebra leaves the transform of p(m,n,q):
P(a,b,c)= B*exp(-[pi]i(a+b+c))/8/(1-cos(2[pi]a/N)*cos(2[pi]b/N)*cos(2[pi]c/N)

The formula for an inverse discrete Fourier Transform is g(j)=(1/N)*sum(G(w)*exp(2[pi]i*w*j/N), where the sum is on w from 0 to N-1. To find p(m,n,q), take the inverse transform on the three parameters, a, b, and c. Take limit on the triple sum as N goes to infinity to get a triple integral.

Using the resulting formula gives p(N/2,N/2,N/2)= (B/64/[pi]³)*[int] dx*dy*dz/(1-cos(x)*cos(y)*cos(z)), where "[int]" means triple integral on x, y, and z from 0 to 2[pi]. Knowing that p(N/2,N/2,N/2) equals 1 and evaluating the integral, allows the constant B to be evaluated. Also by its definition, B = 8 - 8*p(N/2+1,N/2+1,N/2+1). This allows evaluation of p(N/2+1,N/2+1,N/2+1), the probability of a point one step away from the starting point to ever return.

Title: Re: Three Dimensional Random Walk
Post by Deedlit on Apr 13^th, 2005, 9:01pm

on 04/12/05 at 19:26:09, SWF wrote:

Use discrete Fourier Transform: G(w)=sum(g(j)*exp(-2[pi]i*w*j/N), where sum is on j from 0 to N-1. Take discrete Fourier Transform of the expression for f(m,n,q) three times summing over m, n, and q. Some algebra leaves the transform of p(m,n,q):
P(a,b,c)= B*exp(-[pi]i(a+b+c))/8/(1-cos(2[pi]a/N)*cos(2[pi]b/N)*cos(2[pi]c/N)

How did you get that? If (N/2, N/2, N/2) is the only nonzero value, then I only get one term from the fourier transorm, B*exp(-[pi]i(a+b+c)). Do the other terms come from boundary cases?

Quote:

The formula for an inverse discrete Fourier Transform is g(j)=(1/N)*sum(G(w)*exp(2[pi]i*w*j/N), where the sum is on w from 0 to N-1. To find p(m,n,q), take the inverse transform on the three parameters, a, b, and c. Take limit on the triple sum as N goes to infinity to get a triple integral.

I'm not there yet, but what is the rationale for taking the transform and then immediately the inverse transform?

Title: Re: Three Dimensional Random Walk
Post by SWF on Apr 14^th, 2005, 9:35pm

You do not take the transform and immediately invert it. Take the transform of the difference equation. The transform of f(m,n,q) is equal to B*exp(-[pi]i(a+b+c)) and that equals the transform of

8*p(m,n,q) - p(m-1,n-1,q-1) - p(m-1,n-1,q+1) - ... - p(m+1,n+1,q+1)

which is P(a,b,c)*8*(1-cos(2[pi]a/N)*cos(2[pi]b/N)*cos(2[pi]c/N)). Rearrage to get an expression for P(a,b,c) (the transform of p(m,n,q)) then take the inverse. The whole trick is that the transform of that difference equation leads to something which can be inverted to get p(m,n,q).

When transforming that difference equation to get the above result, you have to assume that p() is periodic with period N and manipulate the limits on the summations so that each of the 9 terms is clearly a multiple of P(a,b,c). That leads to a bunch of exp() of imaginary numbers, and use 2*cos(x)=exp(i*x)+exp(-i*x).

Title: Re: Three Dimensional Random Walk
Post by Deedlit on Apr 15^th, 2005, 3:40pm

Ah, I see. Just a couple more questions, if you don't mind: How did you evaluate the integral, and in what sort of situations do you use the Fourier transform?

Title: Re: Three Dimensional Random Walk
Post by SWF on Apr 20^th, 2005, 5:38pm

I don't remember the details, but here is a rough summary of how a value was found for that integral. The first of the triple integrals was done with residues, so that it becomes a double integral with an integrand of something like 2[pi]/sqrt(1-cos²(y)*cos²(z)). This is proportional to the integral of the complete elliptic integral of first kind of cos(y). Change of variable makes it proportional to integral from 0 to 1 of K(w)/sqrt(1-w²), where K(w) is complete elliptic integral of first kind of w. That last integral looked tough, but checking in a book of integral tables, it is found to equal K(1/sqrt(2))².

Fourier Transform is commonly used for spectral analysis of a signal. It transforms data into their frequency components. Electrical engineers, such as William Wu, can explain better than I can.

Fourier Transform is also useful for solving certain partial differential equations, such as Laplace Equation in rectangular coordinates, when the domain is -infinity to +infinity. Similarity to the difference equation in this problem to the Laplace equation is why I considered Fourier Transform. For solving a PDE an integral form of the FT is used, so I figured a discrete version could be used for a difference equation.

Title: Re: Three Dimensional Random Walk
Post by River Phoenix on May 22^nd, 2005, 1:47pm

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?

Title: Re: Three Dimensional Random Walk
Post by River Phoenix on May 22^nd, 2005, 1:52pm

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)

Title: Re: Three Dimensional Random Walk
Post by River Phoenix on May 22^nd, 2005, 2:25pm

I believe that the actual answer is 1, and that I incorrectly stated f(infinity)=0 when f(infinity)=1. Here's my reasoning:

[hideb]
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?
[/hideb]

Title: Re: Three Dimensional Random Walk
Post by River on May 22^nd, 2005, 2:38pm

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.

Title: Re: Three Dimensional Random Walk
Post by River Phoenix on May 22^nd, 2005, 5:08pm

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.

Title: Re: Three Dimensional Random Walk
Post by River Phoenix on May 22^nd, 2005, 5:13pm

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

Title: Re: Three Dimensional Random Walk
Post by Deedlit on May 23^rd, 2005, 1:18am

on 05/22/05 at 17:13:34, 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:

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!