A drunkard is zigzagging home. At every steps forward (or backward) he is making, he also moves \(1\) step to the left with probability \(p\) and \(1\) step to the right otherwise. He starts \(i\) steps to the right of a river. What is the expected number of steps forward before he falls into the river?

Theorem

Let \(a \in \mathbb{N} \), \(t < a \in \mathbb{N} \), and \(b \in \mathbb{R}\). Defining \(A_t\)to be some real number and

$$ A_N = (1 - \frac{a}{N}) A_{N-1} + b, N > t \in \mathbb{N}, $$

then

$$ A_N = \frac{b}{1+a} (N+1), N \ge a \in \mathbb{N}. $$

The Fibonacci numbers are defined as \(f_0 = 0,\ f_1 = 1\) and, for \(i \ge 2,\ f_i = f_{i-1} + f_{i-2}\). Here is the beginning of the Fibonacci sequence:

\(0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots\)

We generalize the definition above by changing the two initial values, for example with \(f_0 = 4,\ f_1 = 6\) we obtain

\(4, 6, 10, 16, 26, 42, \ldots\)