Author |
Topic: Jumping Frog on Ladder (Stopping Time "e") (Read 2637 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Jumping Frog on Ladder (Stopping Time "e")
« on: Jul 14th, 2004, 1:20pm » |
 Quote  Modify
|
Rewritten problem statement (so it's more appealing/understandable):
Imagine a upright ladder with n rungs. At each time step, a frog jumps to one of the n rungs uniformly at random. (The frog could jump in place.) Assume time starts counting from 1, and the initial rung position is also chosen uniformly at random.
As the number of rungs tends to infinity, what is the expected time till the frog first jumps downwards? Prove it.
Author: William Wu
Old problem statement:
I stumbled on something pretty neat yesterday while playing with my computer.
Let n be a positive integer. Now consider the infinite sequence of random variables X1,X2, ...., where the Xi are iid, uniformly chosen from the integers between 1 to n inclusive.
Let T denote the time at which the sequence first moves downwards. I wanted to find what T is on average.
For example, for n = 7, the first 10 elements of a simulated sequence might be:
1 6 4 7 4 3 6 4 2 5
in which case T = 3, since index 3 is the first time the sequence moves downwards.
We can estimate the expectation of T by simulating the sequence many times, and taking the average. So for n = 10, I ran a couple thousand simulations, and took the average T; I got around 2.868.
Then I tried n=1000. I got about 2.74.
Then n=100,000. I get 2.718. Look familiar?! 
Problem: Prove that as n[to][infty], the expected time till the aformentioned sequence first moves downwards is e.
I have a simple proof, but I'm curious to see if others come up with different approaches.
|
| « Last Edit: Jul 17th, 2004, 2:40pm by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Leo Broukhis
Senior Riddler
Gender:
Posts: 459
|
|
Re: Stopping Time "e"
« Reply #1 on: Jul 14th, 2004, 4:12pm » |
Quote Modify
|
This looks like the "choosing the prettiest bride" puzzle put sideways.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Stopping Time "e"
« Reply #3 on: Jul 15th, 2004, 5:42am » |
Quote Modify
|
This may not be the most elegant, but it works:
For the first downwards movement to be at k+2, we can represent the first k+1 numbers as a path on a (k+1)xn lattice, where at each step we move right or up. If the (k+1)th number is j+1, then there are k+jCj such paths, and j choices for the (k+2)th number. So we may write the expected value as:
[sum]k=0oo (k+2) [sum]j=1n-1 k+jCk*j/nk+2
= [sum]k=0oo (k+2)/nk+2 n(n-1)*n+kCk/(k+2)
= (1-1/n)[sum]k=0oo n+kCk/nk
= (1-1/n)-n,
and we all know where that goes.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Stopping Time "e"
« Reply #4 on: Jul 16th, 2004, 11:17am » |
Quote Modify
|
Here's a simpler way:
Let er be the number of additional throws, given that we just picked r (and the one before was at least no more than r). Then
er = 1 + 1/n [sum]k=rnek
The number we wish to find is e1, since we can imagine an extra 1 at the beginning of the sequence.
One can show inductively that er = (n/(n-1))n-r+1, and this gives e1 = (n/(n-1))n, as before.
|
| « Last Edit: Jul 17th, 2004, 2:24pm by Eigenray » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Stopping Time "e"
« Reply #5 on: Jul 16th, 2004, 11:57am » |
Quote Modify
|
I didn't know how to solve that recurrence directly, but computing the values for n=3 made it obvious what the pattern was, so I could prove it inductively. But here's a direct approach:
As for the base case, note that en = 1/n(1+en) + (n-1)/n*1, because with probability 1/n, we keep going, otherwise we stop. So en = n/(n-1).
Now let's find er in terms of er+1.
Suppose we've just picked r. Then er is almost er+1, except in the case that the next number is also r. er+1 would count this as length 1, because he'd stop there, whereas er should count this as length (1+er), because we keep going. Therefore
er = er+1 + 1/n [(1+er)-1]
er = er+1*n/(n-1).
And this easily gives e1 = (n/(n-1))n.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Jumping Frog on Ladder (Stopping Time "e")
« Reply #6 on: Jul 17th, 2004, 4:05am » |
Quote Modify
|
Nice Eigenray. I think I like the recurrence proof better than mine. I didn't quite follow the explanation of the er = er+1 + (1/n) [ 1 + er - 1] line, but writing out the expressions
er = 1 + 1/n [sum]k=r to n ek
er+1 = 1 + 1/n [sum]k=r+1 to n ek
easily allows us to conclude that er+1 = er - (1/n) er.
Here's my solution:
Consider the following alternative experiment: each X_i is drawn from a uniform distribution on the continuous interval [0,1]. Then we wish to find the expectation of the time T till the first downward move.
Solving this problem is equivalent to solving the original problem. If not convinced, see the footnote argument at the end. This version of the problem has the advantage of avoiding combinatorial complications. Namely, given n points uniformly drawn from [0,1], we can assume that all n points are distinct.
Pr(T = 1) = 0. We can't have evidence of a descent with only one data point available.
Now let's compute Pr(T = k). If T = k, then the first k-1 points must be monotonically increasing, and the last point must simply be less than the k-1th point. Thus, we can express the event T = k as the intersection of two events
Pr(T = k) = Pr( EA AND EB )
where EA = {X1 < X2 < ... < Xk-2},
and EB = {Xk-1 = max(X1,...,Xk) }.
These are independent events. The probability of EA is 1/((k-2)!), since there are (k-2)! ways of permuting k-2 distinct values. The probability of EB is 1/k, since that is the probability that the k-1th slot contains the maximal point. Thus the expectation of T is given by
E[T] = sumk=2 to [infty] ( k * Pr(T = k))
= sumk=2 to [infty] ( k * 1/k * 1/((k-2)!) )
= sumk=2 to [infty] ( 1/((k-2)!) )
After a change of variables, we see this is just the Maclaurin expansion for e1.
* I argue that solving this problem is equivalent to solving the original. Argument: We can use this alternative experiment to do the original, discretized experiment by simply multiplying every X_i by n, and taking the ceiling of those products. Thus, the difference between these two experiments is this: In the continuous case, the time of first descent may be due to two adjacent points Xn-1 and Xn, where Xn-1 > Xn, and both points fall in the same subinterval of length 1/n. However, in the discrete case, the time of first descent must occur later, since those two points are equivalent after multiplying by n and rounding. However, in the limiting case where n[to][infty], the subintervals of length 1/n have zero measure, so there is no opportunity for discrepancy between the two experiments.
|
| « Last Edit: Jul 17th, 2004, 2:35pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Jumping Frog on Ladder (Stopping Time "e")
« Reply #7 on: Jul 17th, 2004, 1:48pm » |
Quote Modify
|
Ah, now I see the connection to choosing the bride. Nice.
As for why er = er+1 + er/n:
For each sequence S starting with r, let S' start with r+1, but be the same as S for all the other numbers. If the second number S(2) of S is anything other than r, then S and S' have the same "value", i.e., length up to and including the first time it goes down. If S(2)=r, however, then S has, on average, value 2+er, while S' has value 2.
So of all sequences S starting with r, (1-1/n) of them have the same value as S', but 1/n of them have an average value of er greater.
So er = er+1 + 1/n er.
Actually, this argument is equivalent to subtracting the expression for er+1 from er; it's just an explanation of the extra term.
|
| « Last Edit: Jul 17th, 2004, 1:54pm by Eigenray » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Jumping Frog on Ladder (Stopping Time "e")
« Reply #8 on: Jul 17th, 2004, 2:29pm » |
Quote Modify
|
Nice. I see the reasoning behind what you were saying earlier now.
Here's an even faster proof:
Again I argue that in the limiting case where n[to][infty], the experiment is equivalent to drawing each Xi from a uniform distribution over [0,1]. Then we wish to find the expectation of the time T till the first downward move.
Note that T is a non-negative integer-valued random variable. For such variables, we have the theorem
E[T] = [sum]k >= 1 Pr(T >= k)
T >= k only if the first k-1 samples are monotonically increasing. This occurs with probability 1/((k-1)!), since there is only one way of permuting k-1 distinct values such that they are strictly increasing. Substituting this into the formula above yields e.
|
| « Last Edit: Jul 17th, 2004, 2:31pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Jumping Frog on Ladder (Stopping Time "e")
« Reply #9 on: Jul 27th, 2004, 5:20am » |
Quote Modify
|
In case anyone was wondering where that identity in my previous post came from, here's a quick proof:
Let T be an integer valued non-negative random variable. Then we have
T = [sum]k=1 to inf 1(T >= k)
where "1(T >= k)" is the indicator random variable that is 1 if T >= k, and 0 otherwise.
The expectation of an indicator random variable is simply the probability of the variable being 1.
By linearity of expectation, we then have
E[T] = [sum]k >= 1 Pr(T >= k).
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print