# Expected number of frog jumps

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.

-

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

-
A small typo: actually $P(\tau>n)=P(D_n<d).$ – Byron Schmuland Sep 18 '12 at 19:43
@Byron: whoops! Thanks! – Alex 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

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.

-
 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

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.

-
 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

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:

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.

-
 @DownVoter, care to comment? – KeithS Sep 18 '12 at 18:52