A jumping frog is currently at $x=0$ and $t=0$(time). With each second, the frog jumps to the right to its target, by randomly choosing the leap length from $\{0, 1, \dots, n\}$.
We want to find the time it takes the frog to get out of the region $[0, n-1]$. Let $X$ be a random variable denoting the number of seconds it took the frog to reach at least $n$.
Find $E[X]$ (the expectation of $X$).
So, first of all I know that $$E[X] = \sum_{i=0}^\infty P(X\ge i)$$
$$P(X\ge i) = 1 – P(X<i)$$
Is this true?
We can loot at the total number of steps as the sum of steps at each second $i$.
So we use elementary combinatorics and it leads us to this:
$$X_1 + X_2 + … + X_{i-1} \le n-1$$
$$P(X\ge i) = \frac{n+i-2 \choose n-1}{(i-1)^{n+1}} $$
I also tried calculating the sum but it didn't go anywhere.
Thanks in advance 🙂
Best Answer
For $j\in\{0,1,\ldots,n-1\}$ let $E_j$ denote the expected time it takes for the spider to reach at least $n$ given the spider resides at position $j$. You're trying to find $E_0$. Using the total law of expectation with recursion we get $$E_j=1+\frac{1}{n+1}\sum_{k=j}^{n-1}E_k$$ This system of $n$ equations boils down to $$E_j=\Bigg(\frac{n}{n+1}\Bigg)^jE_0$$ $$E_{n-1}=\frac{n+1}{n}$$ Combining the two gives us an expression for $E_0$: $$E_0=\Bigg(\frac{n+1}{n}\Bigg)^n \longrightarrow e$$ as $n\longrightarrow \infty$.