The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Antrax
ESL Student

 Posted: Mon Jan 03, 2005 9:23 am    Post subject: 1 I'm working on my probaiblity homework now, and one of the questions deals with a "random walker" - imagine someone standing on 0 and stumbling left or right with equal probability. They're asking us what the expectation of the number of times he got to 4 before getting back to 0 is. I like checking my answers, so I wrote a simulation. It got "stuck", or so I thought, so I told it to output the "trips" the random walker takes, as a debug measure. Much to my surprise, out of 10 "random trips", one trip took like 30 steps. So I tinkered with it a bit, and now I asked it to also output what's the maximal X coordinate the random walker gets to, just out of curiousity. I expected around 20, maybe 100 tops. I got 17164 after 10000 simulated trips (I ran it 10 times more now, and the lowest was 2213). Anyone with an intuitive explanation of how the hell he can stray so far from the center? It seems completely illogical to me._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
Antrax
ESL Student

 Posted: Mon Jan 03, 2005 9:34 am    Post subject: 2 The expectation of the maximus for one trip: 232. WTF?_________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
CrystyB
Misunderstood Guy

Posted: Mon Jan 03, 2005 12:31 pm    Post subject: 3

Could you please give more details about your program? Its pseudocode, maybe? I ran a simulation myself, and got an average maxima of 4.42 (from -5.1316 and 3.7037; the two extremes were -4850 and 2066), so i wonder how did you come up with 232...

The average of the number of times of getting to 4 was in my case 1.0056 - what was your theoretical result?

Here's my VBA code:
 Code: Sub simulate_random_walk()   Randomize   For sim = 1 To 10000     x = 0     xMax = 0     xMin = 0     p4 = 0     n = 0     Do       n = n + 1       If Rnd() < 0.5 Then         x = x + 1       Else         x = x - 1       End If       If x > xMax Then xMax = x       If x < xMin Then xMin = x       If x = 4 Then p4 = p4 + 1     Loop While x <> 0     Cells(sim, 1) = p4     Cells(sim, 2) = xMin     Cells(sim, 3) = xMax     Cells(sim, 4) = n     Cells(sim + 1, 1).Select   Next sim End Sub
Hmmm... Rereading my code made me wonder if -4 should be counted too. I'm undecided on the matter.

Last edited by CrystyB on Mon Jan 03, 2005 2:18 pm; edited 1 time in total
Antrax
ESL Student

Posted: Mon Jan 03, 2005 2:04 pm    Post subject: 4

The expectation is 1, I have shown it statistically and it's what my program predicts.
 Code: #include #include using namespace std; int main() { unsigned int number=0; int pos; int max=0; unsigned int max_sum=0; srand( (unsigned)time( NULL ) ); for (unsigned int j=0;j<10000;j++)   {   pos=0;   pos += (2 * (rand() % 2)) -1;   while (pos>0)     {     pos += (2 * (rand() % 2)) -1;     if (pos>max)       max=pos;     if (pos==4)       number++;     }   max_sum+=max;   max=0;   } cout << (double)(number)/10000 << endl; cout << (double)(max_sum)/10000 << endl; return (0); }

_________________
After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
Antrax
ESL Student

 Posted: Mon Jan 03, 2005 2:10 pm    Post subject: 5 Hm... Now it predicts much more sensible values. I think the random function is screwed up _________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Tue Jan 04, 2005 2:05 am    Post subject: 6 I made an assumption that it means absolute 4 and did some different calculations. Therefore the first move would also be to the equivalent of 1. In 8192 trials (of equal probibility of moves), 2016 would reach 4 before they reach 0, 6112 would reach 0 before they reach 4, and 64 would reach neither._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
Antrax
ESL Student

 Posted: Tue Jan 04, 2005 7:33 am    Post subject: 7 You assumed wrong. They meant 4 _________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
+1

 Posted: Tue Jan 04, 2005 9:28 am    Post subject: 8 Well, then I think it's obvious what you should do with the figures._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
CrystyB
Misunderstood Guy

Posted: Tue Jan 04, 2005 11:09 am    Post subject: 9

 Samadhi wrote: Therefore the first move would also be to the equivalent of 1. In 8192 trials (of equal probibility of moves), 2016 would reach 4 before they reach 0, 6112 would reach 0 before they reach 4, and 64 would reach neither.
Neither, as in it staggered between 1 and 3 for the duration of the 13 moves considered? And also there's another thing that matters: how many times have the 2016 trials reached 4? Out of 1 through 6 - i'd guess 6 once, 5 about three times, and so on.
Antrax
ESL Student

 Posted: Tue Jan 04, 2005 3:44 pm    Post subject: 10 Apparently there's a problem with the random function in Visual Studio. The second time I compiled it on my own computer, using g++, and that's why I got the reasonable figure _________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
i_h8_evil_stuff
Daedalian Member

Posted: Tue Jan 04, 2005 5:41 pm    Post subject: 11

 Samadhi wrote: I made an assumption that it means absolute 4 and did some different calculations. Therefore the first move would also be to the equivalent of 1. In 8192 trials (of equal probibility of moves), 2016 would reach 4 before they reach 0, 6112 would reach 0 before they reach 4, and 64 would reach neither.

 Antrax wrote: You assumed wrong. They meant 4

Alright... 16384 (8192*2) trials, same data (2016 would reach 4 before they reach 0, 6112 would reach 0 before they reach 4, and 64 would reach neither), and the other 8192 of them go negative first and would therefore be forced to reach zero first. That totals it to:
2016 reach 4 first,
14304 reach 0 first, and
64 reach neither.

Or we can go with my good friend Colin's logic:
It will either reach 4 or it won't reach 4. Therefore, there are two possibilities. 50%.
_________________
Space for sale. PM i_h8_evil_stuff for details.
Antrax
ESL Student

 Posted: Tue Jan 04, 2005 6:02 pm    Post subject: 12 uh, why are you complicating it so much? If you want to know the probability a random walker that starts on 0 will get to 4 ONCE before getting back to 0, it's like this: 1/2 he'll go left, and then won't reach 4. Otherwise (1/2) he's on 1 and now we can just use a simple formula to see what the odds are he'll make it to 4 before returning to 0 - 1/4. Multiply by the 1/2 you needed to get to this point, and huzzah, you got 1/8._________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
Bicho the Inhaler
Daedalian Member

 Posted: Tue Jan 04, 2005 6:17 pm    Post subject: 13 Or: If the walker is to reach 4 before returning to 0, then the first move must be +1, since otherwise it's impossible to get to 4 without crossing 0. This puts the walker at 1. The second move must be +1, since otherwise the walker has already returned to 0 before reaching 4. This puts the walker at 2. The walker is now equidistant from 0 and 4, so by symmetry, the probabilities of reaching 0 first and reaching 4 first are equal from this point: both 1/2. Put it together: P(1st move is +1) * P(2nd move is +1) * P(reaching 4 before 0, starting at 2) = 1/2 * 1/2 * 1/2 = 1/8. (Similar to what you said, but each step is elementary.)
+1

 Posted: Tue Jan 04, 2005 10:13 pm    Post subject: 14 Missed the reach 0 again part._________________And he lived happily ever after. Except for the dieing at the end and the heartbreak in between.
extro...
Guest

Posted: Wed Jan 05, 2005 1:13 am    Post subject: 15

 Antrax wrote: Apparently there's a problem with the random function in Visual Studio.

There's a problem with all random functions, some more than others.

One interesting result about random walks is that if you extend it to two dimensions, where the walker starts at 0,0 and randomly moves either +X, -X, +Y or -Y one unit at each step, then the result still holds that the walker will return to the starting point with probability 1, but that this is not the case when extended to three or more dimensions.
Bicho the Inhaler
Daedalian Member

Posted: Wed Jan 05, 2005 4:15 am    Post subject: 16

Curiously, if you replace 4 with N, an arbitrary nonzero integer, then the expected number of times the walker visits N before returning to 0 is still 1. (I think I did it correctly: draw a weighted directed graph with nodes "0" and "N" and edge weights as follows:

0->0: (2N-1)/(2N)
0->N: 1/(2N)
N->0: 1/(2N)
N->N: (2N-1)/(2N)

This graph simplifies the random walk by abstracting away all numbers except 0 and N, since the thing we care about is what order these 2 numbers are visited in, starting at 0. The weights represent transition probabilities and can be justified by induction (proof omitted). The probability of visiting N k times before returning to 0 is P(0->N->...->N->0), where there are k N's between the parentheses, so for k > 0, the probability is

P(0->N)*P(N->N)*...*P(N->N)*P(N->0),

where there are k-1 P(N->N)'s. The expected number is thus

P(0->N)*P(N->0)*Summation from k=1 to infinity of {k*P(N->N)^(k-1)}.

The summation evaluates to 1/(1-P(N->N))^2 (well-known formula; proof omitted). Expand everything out to get

1/(2N)^2 * 1/(1-(2N-1)/(2N))^2
= 1.)

I don't have a good intuition for this: for every integer N, the walker is expected to visit that integer exactly once before returning to 0, no matter what that integer is? Of course, there is no actual path that crosses each integer exactly once before returning to 0, unless you allow the following very curious trajectories:

0->1->2->3->4->5->...->-5->-4->-3->-2->-1->0
0->-1->-2->-3->-4->-5->...->5->4->3->2->1->0

which wrap around the number line. Weird, huh?

 ih8 wrote: Or we can go with my good friend Colin's logic: It will either reach 4 or it won't reach 4. Therefore, there are two possibilities. 50%.

I won't go off on a tangent, but I think this is a perfectly sound way to assign probabilities, provided Colin is unable to do the math earlier in this thread That's for another discussion, though.
Antrax
ESL Student

 Posted: Wed Jan 05, 2005 7:46 am    Post subject: 17 extro, I'm aware that all random functions in a PC generate psuedo-random numbers based on a seed, but if you initialize it with the system timer (as often done), is it still not random enough for statistical purposes? And yes, we've been taught the multiple dimension random walker thing. I found it just as surprising _________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
extro...
Guest

 Posted: Wed Jan 05, 2005 1:25 pm    Post subject: 18 The initialization doesn't do anything to make the sequence random - it just helps make different sequences distinct. For some bad generators, (rand() % 2)) will be significantly (statistically) different than 50/50, no matter what the seed. ... or other bad behavior.
CrystyB
Misunderstood Guy

 Posted: Wed Jan 05, 2005 1:31 pm    Post subject: 19 Hmm, this raises the question: if knowing (an estimate of) the bias of rand()%2, say 12:8, how can we get a 50/50? I myself am unable to answer at this time, although if i spent a little while thinking about the matter i think i might come up with a "patch".
extro...
Guest

 Posted: Wed Jan 05, 2005 6:05 pm    Post subject: 20 That's an old one: If the random bits are independent, then when taken in pairs, 01 and 10 are equally likely.
kevinatilusa
Daedalian Member

 Posted: Thu Jan 06, 2005 12:15 pm    Post subject: 21 Neat result! I guess a way to (sort of) intuit that the # of times we're expected to visit n is independent of n is we have two competing factors here. The larger n is, the less likely we are to hit n at all. The larger n is, the more times we're likely to bounce around n before getting to 0, assuming we reach n in the first place. Once we do hit n, we're looking at the whole problem in reverse (trying to reach 0 from n is exactly the same as trying to reach n from 0), so it's not entirely surprising these two factors cancel each other out. (I think it you examine your calculations, you didn't even need to explicitly compute P(0->0) or anything like that...they all cancelled). The result has a nice corollary too: If you're visiting each number on average once, the expected number of visits before returning to 0 is infinite. Therefore the expected time to return to 0 is infinity, even though with probability 1 the walker will do so!
Antrax
ESL Student

 Posted: Thu Jan 06, 2005 12:54 pm    Post subject: 22 This we did in class, too _________________After years of disappointment with get rich quick schemes, I know I'm gonna get rich with this scheme. And quick!
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersAnonymousAntraxBicho the InhalerCrystyBi_h8_evil_stuffkevinatilusaSamadhi Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum