Re: Runs and Sequences

[tlm]

If you know the expectation value of the number of flips s_n required to first obtain a run of length n, then s_n+1 is given by

s_n+1 = 2 s_n + 1

That's because once you hit a run of length n the next flip has a 50% probability of extending the run by one. So on average you'll need twice as many flips for a run of length n+1 than for a run of length n, plus an extra one (the n+1st flip in the run).

Clearly, s₁ = 1. Therefore, s₂ = 3, s₃ = 7. In fact it is easy to show by induction that

s_n = 2ⁿ − 1

because it's true for n = 1, and, by the recurrence above

2 (2ⁿ − 1) + 1 = 2ⁿ⁺¹ − 1

Therefore, on average, to get a run of length 16 you'll need 2¹⁶ − 1 = 65535 flips.

The question of what is the expectation value of the longest run in a fixed number s of flips is a harder one. I don't know of an exact expression for it, but the naive idea of solving for n gets one pretty close: log ₂ (n + 1). (Usually the added 1 is omitted, since n is assumed to be large.)