Getting n heads in a row requires 2^(n+1)-2 flips, as follows: First, you will need to get n-1 consecutive heads: this will take f(n-1) flips. Then, there is a 1/2 chance that your next flip will end the sequence There is also a 1/2 chance the next flip will "restart" the sequence, meaning you will have to flip another f(n) times. Putting this together, f(n)=f(n-1) + 1/2(1) + 1/2(1+f(n)) f(n)=2f(n-1)+2 and f(1)=2 so f(n)=2^(n+1)-2

In general, for a random outcome generator with mutually exclusive outcomes {O1, O2, ..., On} and assigned probabilities {P1, P2, ... Pn} to flip a sequence constructed out of a string of outcomes will be equal to the product of the reciprocals of each of the individual probabilities in the string, plus the expected number of times that it takes to obtain the "overlapping portion" of the string - that is, the proper substring that occurs at both the beginnin of end of the original string. I haven't proven that yet, but I think it's true ._.

four times for the two heads in a row

ReplyDeleteand... 2n for n heads in a row

wahhhhhhh

so ur at stanford?? u miss out on concessions... MOOO

Yeah, I'm at Stanford right now. And both of your answers are wrong =P.

ReplyDeleteXuan, those answers are correct for n heads total, but it takes a lot more effort to get them all in a row.

ReplyDeleteAnyway, the recursion for n looks really ugly...

ReplyDeleteAnother Day, Another Post[...] I highly recommend that you check out this blog, I found it quite fascinating [...]

Getting n heads in a row requires 2^(n+1)-2 flips, as follows:

ReplyDeleteFirst, you will need to get n-1 consecutive heads: this will take f(n-1) flips.

Then, there is a 1/2 chance that your next flip will end the sequence

There is also a 1/2 chance the next flip will "restart" the sequence, meaning you will have to flip another f(n) times. Putting this together,

f(n)=f(n-1) + 1/2(1) + 1/2(1+f(n))

f(n)=2f(n-1)+2

and f(1)=2 so f(n)=2^(n+1)-2

In general, for a random outcome generator with mutually exclusive outcomes {O1, O2, ..., On} and assigned probabilities {P1, P2, ... Pn} to flip a sequence constructed out of a string of outcomes will be equal to the product of the reciprocals of each of the individual probabilities in the string, plus the expected number of times that it takes to obtain the "overlapping portion" of the string - that is, the proper substring that occurs at both the beginnin of end of the original string. I haven't proven that yet, but I think it's true ._.