Pathologically Eclectic Rubbish Lister | |
PerlMonks |
Re: Runs and Sequencesby tlm (Prior) |
on Sep 09, 2005 at 17:54 UTC ( [id://490681]=note: print w/replies, xml ) | Need Help?? |
If you know the expectation value of the number of flips sn required to first obtain a run of length n, then sn+1 is given by sn+1 = 2 sn + 1That'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, s1 = 1. Therefore, s2 = 3, s3 = 7. In fact it is easy to show by induction that sn = 2n − 1because it's true for n = 1, and, by the recurrence above 2 (2n − 1) + 1 = 2n+1 − 1 Therefore, on average, to get a run of length 16 you'll need 216 − 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 2 (n + 1). (Usually the added 1 is omitted, since n is assumed to be large.) the lowliest monk
In Section
Seekers of Perl Wisdom
|
|