5
$\begingroup$

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.

4 Answers 4

5

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

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

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

  • 0
    @Sam: Please fix the typo. This will also change the lower bound of the sum from 1 to 0. Please fix it everywhere.2012-09-18
3

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.

  • 0
    Thanks for digging up this related article (+1ed it). Unfortunately your answer doesn't work for arbitrary distributions, so I can't accept it.2012-09-21
0

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.

  • 0
    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....2012-09-18
-1

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.

  • 0
    @DownVoter, care to co$m$me$n$t?2012-09-18