Consider a sequence of coin tosses recorded on a long paper "ticker tape" as tththhhtt... Starting with the outcome of the first toss, count total #heads and #tails. You should find #heads$\sim$#tails, sometimes more heads, sometimes more tails. As soon as you first notice #heads=#tails+1, snip the ticker tape at that point, and start new counts from that point forwards. Since coin-toss trials are independent/Markov, your new counts should again be #heads$\sim$#tails. So snip again as soon as #heads=#tails+1 again. Continue.

So your long ticker tape tththhhtt... sequence has been partitioned into snipped subsequences, each with an extra head. Just keep snipping, and you can accumulate as many extra heads as you like. Even worse, you can start again, this time snipping whenever #tails=#heads+1, and thus accumulating as many extra tails as you like from exactly the same original tththhhtt... sequence.

Okay, so this must be wrong. But the only possibly wrong thing I see is the assumption that you must eventually count more heads than tails (or vice versa) after some finite number of tosses.

After more algebra than I thought would be needed, the cumulative probability $P_n$ to toss an extra head on or before the $(2n+1)^{\mbox{th}}$ toss is $$P_n = 0.5 + \sum_{k=1}^n \frac{1}{2k}\frac{1}{2^{2k}}\left({2k}\atop{k+1}\right)$$ A table for a few $n$'s is $$\begin{array}{r||c|c} n\ & P_n & 1-P_n \\ \hline \hline 0 & .50000000 & .50000 \\ 1 & .62500000 & .37500 \\ 2 & .68750000 & .31250 \\ \vdots & \vdots & \vdots \\ 4999 & .99202135 & .00798 \\ 9999 & .99435817 & .00564 \\ 19999 & .99601060 & .00399 \\ \end{array}$$ which exhibits very slow convergence to unity, e.g., there's still a .004 probability of never tossing an extra head after 39999 tosses.

So, as far as I can tell, the "paradox" is avoided by slow convergence of $P_n$. But how do you formalize that, and exactly what's "slow enough"?

• I don't agree with the premise. Once you have fixed a sequence of coin tosses, you can no longer say things like "you should find #heads~#tails". This is only a probabilistic statement. But then if you take a sequence of coin tosses at random (using the fair-coin distribution), there are as many coin tosses that will give a extra 100 heads at the end as there are coin tosses that will give a extra 100 tails at the end. So in the long run everything balances out. – zarathustra Dec 11 '15 at 13:26
• I agree that in a "canonical ensemble" of many very long coin-toss-sequences, the tails of the distribution (where #heads$\gg$#tails and vice versa) balance out. But now consider this: pull a coin out of your pocket and start tossing. Record your tosses on a sheet of paper. As soon as #heads=#tails+1 on that sheet, start a new sheet. Continue. Each sheet has an extra head. Same problem as before. Except now, I arguably can't ask you to go back and recount, getting sheets with an extra tail each. But the procedure described still seems to get extra heads for >>every<< sequence you toss. – John Forkosh Dec 11 '15 at 14:02
• The easy solution is to not call this simple fact a paradox. – André Nicolas Dec 11 '15 at 14:17
• The expected time to hit a new $Heads=Tails+1$ is infinite - even though it happens with probability one. So proportion-wise, these extra heads don't matter and you'll have to wait infinitely long (on average) to actually see that happen. There is no paradox. – A.S. Dec 11 '15 at 14:43
• By reflection principle $P(T_1>2n)=\frac 1{2^{2n}}\binom {2n}n\sim \sqrt{\frac 1{{\pi n}}}$. Since $E(T_1)=\sum_{n=0}^\infty P(T_1>n)$ diverges (and rather quickly at that), $E(T_1)=\infty$ and this resolves the paradox and tells you the necessary and sufficient condition to resolve such paradoxes. – A.S. Dec 11 '15 at 15:06

Consider the following binary sequence:

0110001111000001111110000000...

Where each block of identical bits is longer than the previous one.

We can split it as follows:

0 11000 111100000 1111110000000 ...

Where each block has more zeros than ones.

But you can split it another way:

011 0001111 00000111111 ...

Where each block has more ones than zeros.

$1 - 2 + 3 - 4 + 5 - 6 ...$