Oh wow (probability)

[Antrax]

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]

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]

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:

[Antrax]

The expectation is 1, I have shown it statistically and it's what my program predicts.

[Antrax]

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!

[Samadhi]

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]

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!

[Samadhi]

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]

[Antrax]

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]

[Antrax]

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]

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

[Samadhi]

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

[Bicho the Inhaler]

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?

[Antrax]

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

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]

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

That's an old one: If the random bits are independent, then when taken in pairs, 01 and 10 are equally likely.

[kevinatilusa]

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]

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!