Author |
Topic: Three Dimensional Random Walk (Read 11838 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Three Dimensional Random Walk
« on: May 23rd, 2003, 3:54am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
tohuvabohu
Guest
|
|
Re: Three Dimensional Random Walk
« Reply #1 on: May 23rd, 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: 13730
|
|
Re: Three Dimensional Random Walk
« Reply #2 on: May 23rd, 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 23rd, 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 23rd, 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 23rd, 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 23rd, 2003, 8:39pm by phobos » |
IP Logged |
|
|
|
tohuvabohu
Guest
|
|
Re: Three Dimensional Random Walk
« Reply #5 on: May 23rd, 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 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  , 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 23rd, 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 24th, 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 24th, 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 24th, 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 24th, 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: 13730
|
|
Re: Three Dimensional Random Walk
« Reply #10 on: May 24th, 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 24th, 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 24th, 2003, 5:27pm » |
Quote Modify
|
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
|
| « Last Edit: May 24th, 2003, 5:31pm by Leo Broukhis » |
IP Logged |
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Three Dimensional Random Walk
« Reply #13 on: May 25th, 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,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?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Three Dimensional Random Walk
« Reply #14 on: May 25th, 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 25th, 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: 13730
|
|
Re: Three Dimensional Random Walk
« Reply #15 on: May 25th, 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 25th, 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 26th, 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 26th, 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 26th, 2003, 9:38am » |
Quote Modify
|
I think towr refers to this part of the problem statement:
on May 23rd, 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 30th, 2003, 10:10am » |
Quote Modify
|
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
= (2NCN)3 * (1/2)6N
00
So probability = SIGMA (2NCN)3 * (1/2)6N
N=1
|
| « Last Edit: May 30th, 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 30th, 2003, 10:26am » |
Quote Modify
|
on May 30th, 2003, 10:10am, THUDandBLUNDER wrote:
00
So probability = SIGMA (2NCN)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 30th, 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 30th, 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 31st, 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 11th, 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) = 2NCN. 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-2CN-1 - 2NCN
= 2NCN(4N2/(2N*(2N-1)) - 1)
= 2NCN(2N/(2N-1) - 1)
= 2NCN/(2N-1)
Now it has been suggested that at time 2N, exactly 3D(N)A2(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)A2(N) - 3D2(N)A(N) + D3(N).
Now we can find the probability P(N) that a particle returns to the origin by 2N steps, knowing that there are 23*2N possible particle paths after 2N steps:
P(N) = sumi=1..NQ(i)/26i
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 11th, 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: 13730
|
|
Re: Three Dimensional Random Walk
« Reply #23 on: Jun 11th, 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 data-file 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 11th, 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 11th, 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?
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print