Author 
Topic: Three Dimensional Random Walk (Read 10226 times) 

william wu
wu::riddles Administrator
Gender:
Posts: 1291


Three Dimensional Random Walk
« on: May 23^{rd}, 2003, 3:54am » 
Quote Modify

A particle starts at origin O in threespace. 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 5050 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.


IP Logged 
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com



tohuvabohu
Guest


Re: Three Dimensional Random Walk
« Reply #1 on: May 23^{rd}, 2003, 9:44am » 
Quote Modify
Remove

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


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13651


Re: Three Dimensional Random Walk
« Reply #2 on: May 23^{rd}, 2003, 1:52pm » 
Quote Modify

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


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Three Dimensional Random Walk
« Reply #3 on: May 23^{rd}, 2003, 1:57pm » 
Quote Modify

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.)

« Last Edit: May 23^{rd}, 2003, 10:22pm by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



phobos
Newbie
Gender:
Posts: 49


Re: Three Dimensional Random Walk
« Reply #4 on: May 23^{rd}, 2003, 8:16pm » 
Quote Modify

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.

« Last Edit: May 23^{rd}, 2003, 8:39pm by phobos » 
IP Logged 



tohuvabohu
Guest


Re: Three Dimensional Random Walk
« Reply #5 on: May 23^{rd}, 2003, 9:40pm » 
Quote Modify
Remove

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 sidecenter 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 sidecenter 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 , 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.


IP Logged 



phobos
Newbie
Gender:
Posts: 49


Re: Three Dimensional Random Walk
« Reply #6 on: May 23^{rd}, 2003, 10:07pm » 
Quote Modify

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


IP Logged 



tohuvabohu
Guest


Re: Three Dimensional Random Walk
« Reply #7 on: May 24^{th}, 2003, 7:57am » 
Quote Modify
Remove

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.


IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Three Dimensional Random Walk
« Reply #8 on: May 24^{th}, 2003, 8:54am » 
Quote Modify

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.

« Last Edit: May 24^{th}, 2003, 9:23am by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



tohuvabohu
Guest


Re: Three Dimensional Random Walk
« Reply #9 on: May 24^{th}, 2003, 10:24am » 
Quote Modify
Remove

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%.


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13651


Re: Three Dimensional Random Walk
« Reply #10 on: May 24^{th}, 2003, 3:49pm » 
Quote Modify

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..


IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



tohuvabohu
Guest


Re: Three Dimensional Random Walk
« Reply #11 on: May 24^{th}, 2003, 4:50pm » 
Quote Modify
Remove

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 ).


IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Three Dimensional Random Walk
« Reply #12 on: May 24^{th}, 2003, 5:27pm » 
Quote Modify

I believe there is some overcomplication. Consider a onedimensional 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

« Last Edit: May 24^{th}, 2003, 5:31pm by Leo Broukhis » 
IP Logged 



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Three Dimensional Random Walk
« Reply #13 on: May 25^{th}, 2003, 12:37am » 
Quote Modify

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,N1)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?


IP Logged 



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13651


Re: Three Dimensional Random Walk
« Reply #14 on: May 25^{th}, 2003, 2:06am » 
Quote Modify

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%.

« Last Edit: May 25^{th}, 2003, 2:12am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13651


Re: Three Dimensional Random Walk
« Reply #15 on: May 25^{th}, 2003, 4:41am » 
Quote Modify

Here are some plots of the fraction of particals that has returned for the first time at step i and the total fraction of particals that has return at least once before or on step i

« Last Edit: May 25^{th}, 2003, 4:45am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Three Dimensional Random Walk
« Reply #16 on: May 26^{th}, 2003, 9:24am » 
Quote Modify

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.

« Last Edit: May 26^{th}, 2003, 10:04am by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Three Dimensional Random Walk
« Reply #17 on: May 26^{th}, 2003, 9:38am » 
Quote Modify

I think towr refers to this part of the problem statement: on May 23^{rd}, 2003, 3:54am, william wu wrote:One move in this walk sends the particle with equal likelihood to one of the eight corners of the cube. 



IP Logged 
"You're a jerk, <your surname>!"



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Three Dimensional Random Walk
« Reply #18 on: May 30^{th}, 2003, 10:10am » 
Quote Modify

I believe required probability is that of finding the probability of 3 independent 1D random walks arriving back at the origin simultaneously. Chance of this happening after each have taken 2N steps = (^{2N}C_{N})^{3} * (1/2)^{6N} 00 So probability = SIGMA (^{2N}C_{N})^{3} * (1/2)^{6N} N=1

« Last Edit: May 30^{th}, 2003, 10:12am by ThudnBlunder » 
IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



wowbagger
Uberpuzzler
Gender:
Posts: 727


Re: Three Dimensional Random Walk
« Reply #19 on: May 30^{th}, 2003, 10:26am » 
Quote Modify

on May 30^{th}, 2003, 10:10am, THUDandBLUNDER wrote: 00 So probability = SIGMA (^{2N}C_{N})^{3} * (1/2)^{6N} N=1 
 Isn't this the same answer Leonid posted a few days ago? Well, apart from the fact that he posted it only once.

« Last Edit: May 30^{th}, 2003, 10:27am by wowbagger » 
IP Logged 
"You're a jerk, <your surname>!"



Leo Broukhis
Senior Riddler
Gender:
Posts: 459


Re: Three Dimensional Random Walk
« Reply #20 on: May 30^{th}, 2003, 12:43pm » 
Quote Modify

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].


IP Logged 



ThudnBlunder
wu::riddles Moderator Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489


Re: Three Dimensional Random Walk
« Reply #21 on: May 31^{st}, 2003, 12:05am » 
Quote Modify

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


IP Logged 
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Three Dimensional Random Walk
« Reply #22 on: Jun 11^{th}, 2003, 10:20am » 
Quote Modify

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) = ^{2N}C_{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 2N2, multiply by 4, then subtract the number that still haven't returned by 2N. D(N) = 4*E(N1)  E(N) = 4*^{2N2}C_{N1}  ^{2N}C_{N} = ^{2N}C_{N}(4N^{2}/(2N*(2N1))  1) = ^{2N}C_{N}(2N/(2N1)  1) = ^{2N}C_{N}/(2N1) Now it has been suggested that at time 2N, exactly 3D(N)A^{2}(N) particles reach the origin for the first time. However, this formula doublecounts 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^{2}(N)  3D^{2}(N)A(N) + D^{3}(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..N}Q(i)/2^{6i} 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?

« Last Edit: Jun 11^{th}, 2003, 10:24am by James Fingas » 
IP Logged 
Doc, I'm addicted to advice! What should I do?



towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13651


Re: Three Dimensional Random Walk
« Reply #23 on: Jun 11^{th}, 2003, 10:41am » 
Quote Modify

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 datafile on the web as well.. * newly returning particle fraction at each step * accumulation of particles * C++ source for my simulation (not the most efficient way, but simple)

« Last Edit: Jun 11^{th}, 2003, 10:56am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



James Fingas
Uberpuzzler
Gender:
Posts: 949


Re: Three Dimensional Random Walk
« Reply #24 on: Jun 11^{th}, 2003, 11:59am » 
Quote Modify

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...


IP Logged 
Doc, I'm addicted to advice! What should I do?



