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...
Another Day, Another Post
ReplyDelete[...] 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 ._.