Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

There is frog jumping forward on a line. Each jump distance is random with a known cumulative distribution function $F$. What is the expected number of jumps to reach (or go beyond) distance $d$ from the origin?

If there is a Wikipedia or other web page describing the formula in terms of $F$, just give a (deep) link. I'd prefer to have the proof as well.

share|improve this question
add comment

4 Answers

up vote 4 down vote accepted

Let $X_i$ denote the distance of jump $i$ of the frog. Each $X_i$ is independent of one-another. The total distance at jump $n$ is then $D_n=X_1+\cdots+X_n$. Define $\tau$ for $D_\tau$, where $\tau$ is the first time such that $D_\tau\geq d$. You are interested in $E(\tau)$. The distribution of $D_n$ is the $n$-fold convolution of $F$'s: $F_n = (F\star)^n:=F\star F\star\cdots \star F$.

$P(\tau> n) = P(D_n<d)$

Now use $E(\tau)=\sum_{n=0}^\infty P(\tau> n)=\sum_{n=0}^\infty P(D_n<d)$

Which we can simplify when $F$ is continuous by noting $P(D_n<d)=P(D_n\leq d)=F_n(d)$. I'm not sure if there's any more simplification you can do without an explicit form for $F$.

share|improve this answer
1  
A small typo: actually $P(\tau>n)=P(D_n<d).$ –  Byron Schmuland Sep 18 '12 at 19:43
    
@Byron: whoops! Thanks! –  Alex R. Sep 18 '12 at 20:49
    
@Sam: Please fix the typo. This will also change the lower bound of the sum from 1 to 0. Please fix it everywhere. –  pts Sep 18 '12 at 23:44
add comment

Reference: This problem has been worked out thoroughly if the random walk steps are uniform and continuous. See, for example,

Russell, K. G. On the number of uniform random variables which must be added to exceed a given level. J. Appl. Probab. 20 (1983), no. 1, 172–177.

It is a well-known puzzle to show that the expected number of uniform(0,1) steps to exceed level 1 is $\exp(1)$. I was sure that this appears somewhere on this site, but I can't find it.

share|improve this answer
    
Thanks for digging up this related article (+1ed it). Unfortunately your answer doesn't work for arbitrary distributions, so I can't accept it. –  pts Sep 21 '12 at 11:44
add comment

Since the frog is jumping forward, the random variable $X$ denoting the distance per jump will always be nonnegative. So we can use the result for expectations of nonnegative random variables, shown and proved here: Wikipedia's entry on expected values. The result gives us that $$E(X) = \int_0^{\infty} \text{Pr}(X \ge x) \; dx = \int_0^{\infty} (1-F(x)) \; dx $$

Now that we have the expected distance per jump, all we have to do is divide the given distance $d$ by $E(X)$ and round appropriately to give us the expected number of jumps.

share|improve this answer
    
Why is it true that if $d/E(x)$ is the expected number of jumps? It's not intuitive to me. Can you please justify? –  pts Sep 18 '12 at 18:14
    
Why do I have to round $d/E(x)$ at all? The result can be a non-integer. –  pts Sep 18 '12 at 18:15
    
Hey there - you would have to round $d/E(X)$ if you agree with me that the frog can only take integral jumps, and not half-jumps or anything like that. Otherwise, rounding would not be necessary. –  Chase Uyeda Sep 18 '12 at 18:30
    
Yes, the frog can only take an integer number of jumps (and the distance of each jump can be any nonnegative real, with the distribution $F$). I'm looking for the expected value of the number of jumps the frog has to take. I fail to see why this has to be an integer, and why rounding is necessary. –  pts Sep 18 '12 at 18:32
    
My thinking was this: $d/E(X)$ is the distance divided by the expected distance per jump. You could think about it by dividing a line segment of length $d$ into subsegments of length $E(X)$ -- then the expected number of jumps would be the number of those subsegments, i.e. $d/E(X)$. However, I think Sam's answer above is better, and doesn't use my assumption that $F$ is continuous.... –  Chase Uyeda Sep 18 '12 at 19:00
add comment

The distribution function defines the probability that the random variable is less than or equal to a given x: $P(n\leq x) = F(x)$. In this case, x is the distance of a single jump.

What we need is the expected value V of the distribution function. To get this, we want the derivative of the distribution function, $f(x) = F'(x)$, which produces a function known as the "probability density function" of x. This function will tell us how likely any given jump is to be x units.

Now, given that, the "expected value" of the random variable is equal to:

enter image description here

This "expected value", much like the term states, is the long-term average value of X given a sufficiently large number of trials. For a normal distribution, it is usually the point at which $f(x)$ is at its peak; however many probability functions are not normal (for instance, the probability of an n-sided die rolled once showing a particular face x is 1/n regardless of x). Now, that equation is the general form. We know that the frog always jumps forward, and thus the jump distance is never negative; therefore, we should actually solve the integral for a lower bound of 0:

$$E[x] = \int_0^\infty xf(x)dx$$

$E[x]$ will be the length of the average jump; it has a roughly 50-50 shot to be higher or lower, and thus given enough jumps, the sum of any n jumps should be $E[x] * n$. Now it's arithmetic; solve $E[x] * n >= d$ for n.

share|improve this answer
    
@DownVoter, care to comment? –  KeithS Sep 18 '12 at 18:52
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.