Coin flipping game:
an exercise in probability and infinite series
[good exercise in calc class,
 in the "series" section]

N players play a game:
player 1 flips a coin; if heads, he wins,
else play moves to player 2, etc.

Let $P_{k,N}$ be the odds that player $k$ wins in the $N$-player game.

Note that if one player plays the game, he wins with probability 1,
which doesn't mean he -always- wins: he might flip infinitely many
tails. This happens with probability zero though.

- given 2 players, compute
  odds via series

Note that this is a very -natural- way of doing it:
H, TTH, TTTTH are the ways to win,
and their probabilities are exactly the terms in the series.

- given $N$ players, compute odds via series
answer:
$$P_{k,N} = 2^{1-k} \frac{2^{N-1}}{2^N - 1} = \frac{1}{2^{k-1}} P_{1,N}$$

- note that player $k+1$ wins exactly half as often as player $k$
  Prove this directly
  [Write this out using series, show that the series
   exactly mimics your intuition:
   you're just taking (k-1) tails on the front,
   IE, mult by $1/2^{k-1}$]

- using this, compute the odds w/o using series
[so 2/3, 1/3; 4/7, 2/7, 1/7, etc.]
(b/c must have ratios $2^{k-1}:2^{k-2}:\dots:2:1$;
 sum these up)

- compute $P_{k,\infty}$

Note that $P_{k,\infty} = \lim_{N \to \infty} P_{k,N}$:
that is, as the number of players gets large, the finite game
approaches the infinite game.
This is pretty plausible, but how can you -prove- it?

- prove this w/o using the computation for $P_{k,N}$;
  how rigorous do you need to be?

Rigorous proof:
consider cycling:
if, after you get past player $N$, you just stop (and no-one wins, say),
then we see that $P_{k,N} \geq P_{k,\infty}$:
going around gives you a higher shot.
However, the odds that it goes around at least once are $2^{-N}$
$P_{k,N} \leq P_{k,\infty} + 2^{-N}$
(if it goes around, you win automatically)

So as $N \to \infty$, the odds of a particular person winning the
finite game approximates the infinite game, and geometrically quickly.
[This is analysis: we -estimate- -how quickly-]
