wu :: forums « wu :: forums - Three Dimensional Random Walk » Welcome, Guest. Please Login or Register. Dec 16th, 2018, 8:59pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, Eigenray, ThudnBlunder, william wu, towr, SMQ, Grimbal)    Three Dimensional Random Walk « Previous topic | Next topic »
 Pages: 1 2 3 Reply Notify of replies Send Topic Print
 Author Topic: Three Dimensional Random Walk  (Read 10226 times)
william wu

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: 13651
 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 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: 13651
 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: 13651
 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: 13651
 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

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

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

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