wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Jumping Frog on Ladder (Stopping Time "e")
        
(Message started by: william wu on Jul 14^th, 2004, 1:20pm)

Title: Jumping Frog on Ladder (Stopping Time "e")
Post by william wu on Jul 14^th, 2004, 1:20pm

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 X₁,X₂, ...., where the X_i 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.

Title: Re: Stopping Time "e"
Post by Leonid Broukhis on Jul 14^th, 2004, 4:12pm

This looks like the "choosing the prettiest bride" puzzle put sideways.

Title: Re: Stopping Time "e"
Post by towr on Jul 15^th, 2004, 12:00am

Interesting, that was my first thought as well..

Title: Re: Stopping Time "e"
Post by Eigenray on Jul 15^th, 2004, 5:42am

This may not be the most elegant, but it works:
[hide]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+jC_j such paths, and j choices for the (k+2)th number. So we may write the expected value as:
[sum]_k=0^oo (k+2) [sum]_j=1^n-1 _k+jC_k*j/n^k+2
= [sum]_k=0^oo (k+2)/n^k+2 n(n-1)*_n+kC_k/(k+2)
= (1-1/n)[sum]_k=0^oo _n+kC_k/n^k
= (1-1/n)^-n,[/hide]
and we all know where that goes.

Title: Re: Stopping Time "e"
Post by Eigenray on Jul 16^th, 2004, 11:17am

Here's a simpler way:[hide]
Let e_r be the number of additional throws, given that we just picked r (and the one before was ~~at least~~ no more than r). Then
e_r = 1 + 1/n [sum]_k=rⁿe_k
The number we wish to find is e₁, since we can imagine an extra 1 at the beginning of the sequence.
One can show inductively that e_r = (n/(n-1))^n-r+1, and this gives e₁ = (n/(n-1))ⁿ,[/hide] as before.

Title: Re: Stopping Time "e"
Post by Eigenray on Jul 16^th, 2004, 11:57am

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:[hide]
As for the base case, note that e_n = 1/n(1+e_n) + (n-1)/n*1, because with probability 1/n, we keep going, otherwise we stop. So e_n = n/(n-1).
Now let's find e_r in terms of e_r+1.
Suppose we've just picked r. Then e_r is almost e_r+1, except in the case that the next number is also r. e_r+1 would count this as length 1, because he'd stop there, whereas e_r should count this as length (1+e_r), because we keep going. Therefore
e_r = e_r+1 + 1/n [(1+e_r)-1]
e_r = e_r+1*n/(n-1).
And this easily gives e₁ = (n/(n-1))ⁿ[/hide].

Title: Re: Jumping Frog on Ladder (Stopping Time "e")
Post by william wu on Jul 17^th, 2004, 4:05am

Nice Eigenray. I think I like the recurrence proof better than mine. I didn't quite follow the explanation of the e_r = e_r+1 + (1/n) [ 1 + e_r - 1] line, but writing out the expressions

e_r = 1 + 1/n [sum]_{k=r to n} e_k
e_r+1 = 1 + 1/n [sum]_{k=r+1 to n} e_k

easily allows us to conclude that e_r+1 = e_r - (1/n) e_r.

Here's my solution:

[hide]
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-1^th point. Thus, we can express the event T = k as the intersection of two events

Pr(T = k) = Pr( E_A AND E_B )

where    E_A = {X₁ < X₂ < ... < X_k-2},
and    E_B = {X_k-1 = max(X₁,...,X_k) }.

These are independent events. The probability of E_A is 1/((k-2)!), since there are (k-2)! ways of permuting k-2 distinct values. The probability of E_B is 1/k, since that is the probability that the k-1^th slot contains the maximal point. Thus the expectation of T is given by

E[T]    = sum_{k=2 to [infty]} ( k * Pr(T = k))
= sum_{k=2 to [infty]} ( k * 1/k * 1/((k-2)!) )
= sum_{k=2 to [infty]} ( 1/((k-2)!) )

After a change of variables, we see this is just the Maclaurin expansion for e¹.

* 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 X_n-1 and X_n, where X_n-1 > X_n, 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.
[/hide]

Title: Re: Jumping Frog on Ladder (Stopping Time "e")
Post by Eigenray on Jul 17^th, 2004, 1:48pm

Ah, now I see the connection to choosing the bride. Nice.

As for why e_r = e_r+1 + e_r/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+e_r, 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 e_r greater.
So e_r = e_r+1 + 1/n e_r.
Actually, this argument is equivalent to subtracting the expression for e_r+1 from e_r; it's just an explanation of the extra term.

Title: Re: Jumping Frog on Ladder (Stopping Time "e")
Post by william wu on Jul 17^th, 2004, 2:29pm

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

Title: Re: Jumping Frog on Ladder (Stopping Time "e")
Post by william wu on Jul 27^th, 2004, 5:20am

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