Consider the standard setup for the Gambler's ruin problem:
Consider a game that gives a probability 1/2 of winning 1 dollar and a probability 1/2 of losing 1 dollar. If a player begins with k dollars, and intends to play the game repeatedly until he either goes broke or increases his holdings to N dollars, what is his probability of reaching his desired goal before going broke?
What is wrong with the following reasoning ?
Suppose I try a direct approach and enumerate the winning paths, then the players wins when :
- the path has (N-k) ups and 0 downs overall [probability $(1/2)^{N-k}$] or
- the path has (N-k+1) ups and 1 down overall [probability $(1/2)^{N-k+1} \times (1/2)$] or
- the path has (N-k+2) ups and 2 downs overall [probability $(1/2)^{N-k+2} \times (1/2)^2$]
...
or
- the path has (N-k+k-1) ups and k-1 downs overall [probability $(1/2)^{N-k+k-1} \times (1/2)^{k-1}$]
Each of these probabilities can be added up since the possibilities are mutually exclusive, so we get:
P (good path)
= $(1/2)^{N-k}$ + $(1/2)^{N-k+1} \times (1/2)$ + $(1/2)^{N-k+2} \times (1/2)^2$ + ... + $(1/2)^{N-k+k-1} \times (1/2)^{k-1}$
= $(1/2)^{N-k}$ $(1 + (1/2)^2 + (1/2)^4 + ... + (1/2)^{2(k-1)}) $ $= {\frac{1}{2}}^{(N-k)} \frac {1-\frac{1}{4}^{k}} {1-\frac{1}{4}}$
which is different from the right solution $1-k/N$ obtained via recurrence relations etc
Where did I go wrong ?
Where is the case that there are $N^2 k^2$ alternations of up and down before any of the listed cases occurs?
There is no global upper bound on the number of downs in a path. There is a local bound on the number of consecutive downs after "now". But there is always a continuation of alternating ups and downs of arbitrarily long length.