Expected value of a probabilistic counter Motivation
A computer with $b$ bits can only count up to $2^{b-1}$ but we want a scheme where we will be able to probabilistically count up to much bigger numbers. We do this by creating an increasing list of way-points $n_i$ and the counter will now specify which way-point we have reached. Progression through the way-points is probabilistic, but defined in such a way that in expectation, the counter will have the correct value.
This is Problem 5-1 in CLRS' Introduction to Algorithms
Details
Suppose I have a positive increasing sequence of integers $n_0, n_1, ..., n_N$ and $n_0 = 0$ (these are the way-points)
Let $w_0 = 0$ and let the markov chain $w_i$ be defined recursively: $w_{i+1} = w_i + 1$ with probability $\frac{1}{n_{w_{i+1}} - n_{w_i}}$ and $w_{i+1} = w_{i}$ otherwise. ($w_i$ tells us, on the $i^{th}$ "pressing-the-button" of the probabilistic counter, which way-point we have reached) And after the last way-point is reached, the counter becomes a standard counter with a 100% probability of transitioning on every press.
Let $C_k  \equiv  n_{w_k }$ be the value of the counter on the $k^{th}$ press. What is the expected value $\equiv E [C_k ]$? (It's $k$ but how can it be easily computed?)
 A: Let $C_m$ be the value of the counter after $j$ presses. Use induction on number of way-points in the counter.
$E[C_m] = E[C_m | \text{1st way-point is never reached}] P(\text { 1st way-point is never reached}) + \sum_{k=1}^m E[C_m | \text{1st way-point in k presses}] P(\text{1st way-point in k presses}) =  \sum_{k=1}^m E[C_m | \text{1st way-point in k presses}] P(\text{1st way-point in k presses})$
Then use and the inductive hypothesis to express the expectation after the first way-point is reached:  
$= \sum_{k=1}^m (m - k + n_1) P(\text{1st way-point in k presses}) $
$= \sum_{k=1}^m (m - k + n_1) (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1} $
I will show this sum is $=m$  ... 
$= [\sum_{k=1}^{m-1} (1 + m-1  - k + n_1) (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1}] + n_1 (1/n_1)(1-1/n_1)^{m-1}$
 $= [\sum_{k=1}^{m-1} (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1}] + [\sum_{k=1}^{m-1}( m-1  - k + n_1) (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1}] + (1-1/n_1)^{m-1}$
Now do a second induction on $m$, i.e. that $\sum_{k=1}^{m'} (m' - k + n_1) (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1} = m'$ for $m' \lt m$:  
$= [\sum_{k=1}^{m-1} (\frac{1}{n_1})(1 - \frac{1}{n_1})^{k-1}] + m-1 + (1-1/n_1)^{m-1}$
Recognize the first term as the CDF of a geometric random variable with parameter $\frac{1}{n_1}$ evaluated at $m-1$
 $= 1 -  (1-1/n_1)^{m-1} + m-1 + (1-1/n_1)^{m-1}$
$= m $  
You can verify base case $m=1$ 
And for the outer induction, the base case of no way-points is trivial since we have a standard counter.
