Biased coin problem
Poll
 | 1 vote (12.5%) | ||
| | 1 vote (12.5%) | ||
| No votes (0%) | |||
| | 1 vote (12.5%) | ||
| No votes (0%) | |||
| | 1 vote (12.5%) | ||
| | 1 vote (12.5%) | ||
| | 1 vote (12.5%) | ||
| | 5 votes (62.5%) | ||
| | 5 votes (62.5%) |
8 members have voted
January 26th, 2019 at 10:42:28 AM
permalink
You have a biased coin with probability p of landing on heads. You flip it and observe the outcome. You then keep flipping it until that same outcome happens again. What is the expected total number of flips, including the first and last?
Beer to the first correct answer. However, I'm putting a 24-hour delay on Gordon, Don, and unJon. They may chime in before 24 hours if somebody else gets the correct answer and may explain why incorrect answers are wrong.
The question for the forum is which statements do you agree with?
Beer to the first correct answer. However, I'm putting a 24-hour delay on Gordon, Don, and unJon. They may chime in before 24 hours if somebody else gets the correct answer and may explain why incorrect answers are wrong.
The question for the forum is which statements do you agree with?
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 26th, 2019 at 10:52:52 AM
permalink
Regarding the poll, and speaking as a person who has no vested interest in either team, I don't feel sorry for the Saints. Bad calls (or non-calls) might not be in the rule book, but they are still a part of the game. I guess that you could just say that the Ram's victory sort of fell off of the back of a truck.
The best things in life are not free.
January 26th, 2019 at 11:12:06 AM
permalink
Assuming the previous approach works, the problem of finding the opposite flip seems to have a more complex answer. Then, it would be 1 + (p)/(1-p) + (1-p)/p = p(1-p) + p^2 + (1-p)^2/(p)(1-p) = (p^2 - p + 1)/(p - p^2) which is infinite at p = 0 and p = 1 and minimized at p = 1/2 for an expectation of 3, which matches the previous answer. It makes sense it's always higher, as we're more likely to have to search for the less likely side of the coin.
Edited to fix spoiler tag and fix "lower" -> "higher"
Edited to fix spoiler tag and fix "lower" -> "higher"
January 26th, 2019 at 12:06:07 PM
permalink
I scribbled some numbers on a paper, then put a few of them into a calculator and hit some buttons and came up with 2 and 5/22
January 26th, 2019 at 12:46:33 PM
permalink
Quote: djtehch34tLet the coin land on heads on the first flip. Then, the expected number of flips required to hit another heads is 1/p. Now, let the coin land on tails on the first flip. Then, the expected number of flips required to hit another tails is 1/(1-p). Summing these for the total expected number of flips is p/p + (1-p)/(1-p) = 2. Adding in the first flip yields 3 expected flips. This seems counterintuitive because for p = 0 or p = 1, we only get two flips, but it still seems to be right?
The reason you think you get 3 for p = 0 or 1 is, the expected number of flips after the first one, according to that formula, is 1/1 + 0/0. In reality, since p (or q) = 0, you disregard that case entirely, rather than bothering with the whole "what is 0/0?" problem.
January 26th, 2019 at 1:38:32 PM
permalink
I read it as “you flip it, it lands on tails, then you flip again until it lands on tails again”, right?
P percent of the time it’ll take 1/p more flips.
Q percent of the time it’ll take 1/q more flips.
1 +
P * (1/p) +
Q * (1/q)
=
1 + P + Q
=
2 final answer
P percent of the time it’ll take 1/p more flips.
Q percent of the time it’ll take 1/q more flips.
1 +
P * (1/p) +
Q * (1/q)
=
1 + P + Q
=
2 final answer
January 26th, 2019 at 1:50:41 PM
permalink
Quote: WizardYou have a biased coin with probability p of landing on heads. You flip it and observe the outcome. You then keep flipping it until that same outcome happens again. What is the expected total number of flips, including the first and last?
Can I assume the 'expected number' does not have to be an actual integer? Or do you mean if 2 is 40%, 3 is 30%, 4 is 15%, etc... the answer will be somewhere between 2 and 3, and not the mode which would be 2?
I am probably out of my league here, but also, can I assume that the answer might vary depending on p? Clearly, if the coin is biased enough that it will always land on heads the answer is obviously 2.
I"m guessing the answer is 1 +e/2. I would give my answer a .1% chance of being correct.
January 26th, 2019 at 2:22:52 PM
permalink
3
1+(p/p)+((1-p)/(1-p)) = 3
1+(p/p)+((1-p)/(1-p)) = 3
January 26th, 2019 at 3:36:46 PM
permalink
Quote: ThatDonGuyQuote: djtehch34tLet the coin land on heads on the first flip. Then, the expected number of flips required to hit another heads is 1/p. Now, let the coin land on tails on the first flip. Then, the expected number of flips required to hit another tails is 1/(1-p). Summing these for the total expected number of flips is p/p + (1-p)/(1-p) = 2. Adding in the first flip yields 3 expected flips. This seems counterintuitive because for p = 0 or p = 1, we only get two flips, but it still seems to be right?The reason you think you get 3 for p = 0 or 1 is, the expected number of flips after the first one, according to that formula, is 1/1 + 0/0. In reality, since p (or q) = 0, you disregard that case entirely, rather than bothering with the whole "what is 0/0?" problem.
I didn't mean to say we get 3 for p = 0 or 1. I was just pointing out that there's a discontinuity at p = 0, 1. My (wrong) intuition was that it would be a smooth function from 2 at 0 up to 3 at p = 1/2.
January 26th, 2019 at 9:50:48 PM
permalink
One of your has the right answer, which I'll announce tomorrow. However, I'll let you guys debate it a bit further.
I would like to remind you the question is the expected number of all flips, including the first one that determines the side of the last flip.
I would like to remind you the question is the expected number of all flips, including the first one that determines the side of the last flip.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 26th, 2019 at 9:54:08 PM
permalink
Quote: ThatDonGuyQuote: djtehch34tLet the coin land on heads on the first flip. Then, the expected number of flips required to hit another heads is 1/p. Now, let the coin land on tails on the first flip. Then, the expected number of flips required to hit another tails is 1/(1-p). Summing these for the total expected number of flips is p/p + (1-p)/(1-p) = 2. Adding in the first flip yields 3 expected flips. This seems counterintuitive because for p = 0 or p = 1, we only get two flips, but it still seems to be right?The reason you think you get 3 for p = 0 or 1 is, the expected number of flips after the first one, according to that formula, is 1/1 + 0/0. In reality, since p (or q) = 0, you disregard that case entirely, rather than bothering with the whole "what is 0/0?" problem.
Sounds like this calls for some “renormalization.”
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 26th, 2019 at 10:25:40 PM
permalink
I’m sticking to my answer. Your facts can’t change my opinion!
But for real, can someone explain what’s wrong with my math? It surely can’t be that easy.
Actually my answer might be wrong. And I have an idea how to fix it. But tbh it’s just too much work (it involves division).
But for real, can someone explain what’s wrong with my math? It surely can’t be that easy.
Actually my answer might be wrong. And I have an idea how to fix it. But tbh it’s just too much work (it involves division).
January 27th, 2019 at 6:12:24 AM
permalink
Quote: RSI read it as “you flip it, it lands on tails, then you flip again until it lands on tails again”, right?
P percent of the time it’ll take 1/p more flips.
Q percent of the time it’ll take 1/q more flips.
1 +
P * (1/p) +
Q * (1/q)
=
1 + P + Q
=
2 final answer
Remember, the question is asking for the expected number of all flips. You need one flip to determine the side. There is the last flip that ends it. Plus possible flips in the middle. So shouldn't the answer be more than 2? For example, THHHT would be five flips.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 27th, 2019 at 8:10:34 AM
permalink
Quote: RSI’m sticking to my answer. Your facts can’t change my opinion!
But for real, can someone explain what’s wrong with my math? It surely can’t be that easy.
And it's not as if I haven't done the same thing on WoV more than once...
"P percent of the time it’ll take 1/p more flips.
Q percent of the time it’ll take 1/q more flips."
1 + P * (1/p) + Q * (1/q)" is correct, if you replace P and Q with p and q.
However, both p * (1/p) and q * (1/q) equal 1, so the solution is 1 + 1 + 1 = 3, instead of 1 + p + q = 2.
January 27th, 2019 at 10:29:38 AM
permalink
Quote: ThatDonGuyQuote: djtehch34tLet the coin land on heads on the first flip. Then, the expected number of flips required to hit another heads is 1/p. Now, let the coin land on tails on the first flip. Then, the expected number of flips required to hit another tails is 1/(1-p). Summing these for the total expected number of flips is p/p + (1-p)/(1-p) = 2. Adding in the first flip yields 3 expected flips. This seems counterintuitive because for p = 0 or p = 1, we only get two flips, but it still seems to be right?
The problem implies that the answer is the same for all values of p but we have inconsistent answers for p=p, p=0, and p=1. For more inconsistency try p = 1/2 (fair coin) there the answer is 6. This has been developed in another thread.
This inconsistency suggests that the answer is a function of p and since p is continuous it could be one heck of a function!Last edited by: netzer on Jan 27, 2019OnceDear is a Dear!
January 27th, 2019 at 1:02:01 PM
permalink
I knew the answer I put couldn’t be right, since it’s too low. But I messed up and converted p/p to be p, not 1. And every time I re-read my answer, I didn’t realize the issue there. But at the same time, I couldn’t see how my logic there could be wrong.
Formula & logic = correct
Converting fractions = incorrect
I’ll take half a beer, thank you very much!
Formula & logic = correct
Converting fractions = incorrect
I’ll take half a beer, thank you very much!
January 27th, 2019 at 1:37:47 PM
permalink
djtehch34t was the first one to say "3," so he wins the beer. Congratulations!
Quote: RSI’ll take half a beer, thank you very much!
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 27th, 2019 at 2:30:20 PM
permalink
Quote: Wizarddjtehch34t was the first one to say "3," so he wins the beer. Congratulations!...
That's a good math problem!
I now see it's the black socks/white socks problem in disguise.
See https://en.wikibooks.org/wiki/Puzzles/Logic_puzzles/Pair_of_Socks
January 27th, 2019 at 4:32:48 PM
permalink
Quote: Wizarddjtehch34t was the first one to say "3," so he wins the beer. Congratulations!
While the Wizard is usually right, it is easy to see that the expected number of tosses is 2 for p = 0 and p = 1.
It was established in another thread the the expected number of tosses is 6 for p = 1/2 (fair coin). The Wizard himself gave a derivation of this.
I have derived a solution as a function of p. What will the Wizard give me if I'm right? I hate to think!
let e be the expected no. of tosses, q = 1-p
Case 1: first flip is H
1a. second flip is H HH reached in 2 flips with probability p
likewise:
HTH: goal reached in 3 flips with Pr pq
HTTH: goal reached in 4 flips with Pr pq^2
HTTTH: goal reached in 5 flips with Pr pq^3
HTTTTH: goal reached in 6 flips with Pr pq^4
H.n.H: goal reached in n+2 flips with Pr pq^n so
goal reached in p(SUM n=0 to inf)(n+2)q^n flips, call this eH
The sum may be calculated by using the emathhelp online series calculator and resolves to
(-q+2)/(q^2-2q+1) with the interval of convergence being for q between q = +1 and -1. Multiply this by p to get eH.
To get eT merely swap p and q then e = peH + qeT
e = p(-q+2)/(q^2-2q+1) + q(-p+2)/(p^2-2p+1)
checking against known values 2 for p = 0 and p = 1 and 6 for p = 1/2. IT CHECKS!
So the answer is a bit more complicated than was previously thought!
OnceDear is a Dear!
January 27th, 2019 at 5:09:39 PM
permalink
Quote: netzerWhile the Wizard is usually right, it is easy to see that the expected number of tosses is 2 for p = 0 and p = 1.
Yes, I should have said 0<p<1.
Let me get back to you on the rest of this.
"For with much wisdom comes much sorrow." -- Ecclesiastes 1:18 (NIV)
January 27th, 2019 at 6:07:02 PM
permalink
Quote: netzerWhile the Wizard is usually right, it is easy to see that the expected number of tosses is 2 for p = 0 and p = 1.
It was established in another thread the the expected number of tosses is 6 for p = 1/2 (fair coin). The Wizard himself gave a derivation of this.
I have derived a solution as a function of p. What will the Wizard give me if I'm right? I hate to think!
let e be the expected no. of tosses, q = 1-p
Case 1: first flip is H
1a. second flip is H HH reached in 2 flips with probability p
likewise:
HTH: goal reached in 3 flips with Pr pq
HTTH: goal reached in 4 flips with Pr pq^2
HTTTH: goal reached in 5 flips with Pr pq^3
HTTTTH: goal reached in 6 flips with Pr pq^4
H.n.H: goal reached in n+2 flips with Pr pq^n so
goal reached in p(SUM n=0 to inf)(n+2)q^n flips, call this eH
The sum may be calculated by using the emathhelp online series calculator and resolves to
(-q+2)/(q^2-2q+1) with the interval of convergence being for q between q = +1 and -1. Multiply this by p to get eH.
To get eT merely swap p and q then e = peH + qeT
e = p(-q+2)/(q^2-2q+1) + q(-p+2)/(p^2-2p+1)
checking against known values 2 for p = 0 and p = 1 and 6 for p = 1/2. IT CHECKS!
So the answer is a bit more complicated than was previously thought!
You think 6 is the answer when p=0.5?
I’d bet that all day long.
Forget the initial flip. Since p=q=0.5 it doesn’t matter if it is H or T. So now we have five flips left to get one more of H or T. And you think that’s expectation? Just step back and think about it. You think half the time won’t get any H in the next 5 flips? When p=0.5.
This is another detour.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 27th, 2019 at 6:20:49 PM
permalink
Quote: unJonQuote: netzerWhile the Wizard is usually right, it is easy to see that the expected number of tosses is 2 for p = 0 and p = 1.
It was established in another thread the the expected number of tosses is 6 for p = 1/2 (fair coin). The Wizard himself gave a derivation of this.
I have derived a solution as a function of p. What will the Wizard give me if I'm right? I hate to think!
let e be the expected no. of tosses, q = 1-p
Case 1: first flip is H
1a. second flip is H HH reached in 2 flips with probability p
likewise:
HTH: goal reached in 3 flips with Pr pq
HTTH: goal reached in 4 flips with Pr pq^2
HTTTH: goal reached in 5 flips with Pr pq^3
HTTTTH: goal reached in 6 flips with Pr pq^4
H.n.H: goal reached in n+2 flips with Pr pq^n so
goal reached in p(SUM n=0 to inf)(n+2)q^n flips, call this eH
The sum may be calculated by using the emathhelp online series calculator and resolves to
(-q+2)/(q^2-2q+1) with the interval of convergence being for q between q = +1 and -1. Multiply this by p to get eH.
To get eT merely swap p and q then e = peH + qeT
e = p(-q+2)/(q^2-2q+1) + q(-p+2)/(p^2-2p+1)
checking against known values 2 for p = 0 and p = 1 and 6 for p = 1/2. IT CHECKS!
So the answer is a bit more complicated than was previously thought!
You think 6 is the answer when p=0.5?
I’d bet that all day long.
Forget the initial flip. Since p=q=0.5 it doesn’t matter if it is H or T. So now we have five flips left to get one more of H or T. And you think that’s expectation? Just step back and think about it. You think half the time won’t get any H in the next 5 flips? When p=0.5.
This is another detour.
I don't see how it could be 6 if p=0.5.
Half the time it's 2.
Quarter the time it's 3.
Eighth of the time it's 4.
Sixteenth of the time it's 5.
Etc.
2/2 + 3/4 + 4/8 + 5/16 + 6/32 + .... = 3
January 27th, 2019 at 8:44:13 PM
permalink
Quote: netzer
(-q+2)/(q^2-2q+1) with the interval of convergence being for q between q = +1 and -1. Multiply this by p to get eH.
To get eT merely swap p and q then e = peH + qeT
e = p(-q+2)/(q^2-2q+1) + q(-p+2)/(p^2-2p+1)
The error here is that eH=p(-q+2)/(q^2-2q+1) and you must multiply by p again when you calculate e.
So, e = p^2(-q+2)/(q^2-2q+1) + q^2(-p+2)/(p^2-2p+1)
This simplifies to e = p^2(-q+2)/(1-q)^2 + q^2(-p+2)/(1-p)^2
e = p^2(-q+2)/p^2 + q^2(-p+2)/q^2
e = (-q+2) + (-p+2)
e = 4-q-p
e = 3
I heart Crystal Math.
January 27th, 2019 at 10:14:36 PM
permalink
6 is the expected number of of flips for 2 consecutive heads. 2^(2+1) - 2 = 6Quote: netzer
It was established in another thread the the expected number of tosses is 6 for p = 1/2 (fair coin). The Wizard himself gave a derivation of this.
2 is the expected number of of flips for 1 head. x = 1 + (1-p)x + p*0. So x = 1/p = 2.
It’s all about making that GTA
January 28th, 2019 at 6:12:49 AM
permalink
Quote: unJonYou think 6 is the answer when p=0.5?
This was discussed in a thread titled "Expected Number of Tosses of a Fair Coin." Part of the problem was to calculate the expected number of tosses to get HH. Of course it would be the same number to get TT. You will find the thread here.
Several members submitted answers.
ThatDonGuy gave 6
I gave 6
The Wizard gave 4
You corrected the Wizard with the remarks "I think your labeling is off. The HH case should be 6 not 4. And the HT case should be 4 not 6" and the Wizard acknowledged your correction. You seemed to understand this once, so go back to that thread and maybe you will understand it again.
7craps gave 6
There is a formula 2(2^n - 1) at Stackexchange for the expected number of flips for n consecutive heads (or tails). This evaluates to 6 for n = 2.
Presh Talwarkar, a mathematician who makes YouTube videos, gives 6.
I envision my function as a symmetric convex curve having values 2 at p = 0 and p = 1 and a maximum of 6 at p = 0.5. There are two values of p that give e = 3 but I haven't tried to calculate them.
OnceDear is a Dear!
January 28th, 2019 at 6:20:03 AM
permalink
See Ace2 post above yours. These are different problems with different solutions.Quote: netzerThis was discussed in a thread titled "Expected Number of Tosses of a Fair Coin." Part of the problem was to calculate the expected number of tosses to get HH. Of course it would be the same number to get TT. You will find the thread here.
Several members submitted answers.
ThatDonGuy gave 6
I gave 6
The Wizard gave 4
You corrected the Wizard with the remarks "I think your labeling is off. The HH case should be 6 not 4. And the HT case should be 4 not 6" and the Wizard acknowledged your correction. You seemed to understand this once, so go back to that thread and maybe you will understand it again.
7craps gave 6
There is a formula 2(2^n - 1) at Stackexchange for the expected number of flips for n consecutive heads (or tails). This evaluates to 6 for n = 2.
Presh Talwarkar, a mathematician who makes YouTube videos, gives 6.
I envision my function as a symmetric convex curve having values 2 at p = 0 and p = 1 and a maximum of 6 at p = 0.5. There are two values of p that give e = 3 but I haven't tried to calculate them.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 28th, 2019 at 6:42:50 AM
permalink
Netzer,
I propose a wager, since that got you to see your error in the Ask Marilyn thread.
We will bet as much as you like per trial at even odds.
You provide a selection of fair coins. I don’t particularly care how fair they are, which is why I will let you provide.
I pick one of the coins and flip it. That will be flip #1. We record the result. I continue flipping the coin (flip #2, 3, etc.) until I once again have it land the with the same result as flip #1.
The over/Under is set at 4.5 (midway between your belief of 6 and my belief of 3).
If by flip #4 I have matched flip#1, I win. Otherwise you win.
We can repeat the game until you want to quit.
For clarity, the following sequence of flips in this game will be winners for me:
HH
HTH
HTTH
TT
THT
THHT
All other sequences will be winners for you.
Do we have a wager?
I propose a wager, since that got you to see your error in the Ask Marilyn thread.
We will bet as much as you like per trial at even odds.
You provide a selection of fair coins. I don’t particularly care how fair they are, which is why I will let you provide.
I pick one of the coins and flip it. That will be flip #1. We record the result. I continue flipping the coin (flip #2, 3, etc.) until I once again have it land the with the same result as flip #1.
The over/Under is set at 4.5 (midway between your belief of 6 and my belief of 3).
If by flip #4 I have matched flip#1, I win. Otherwise you win.
We can repeat the game until you want to quit.
For clarity, the following sequence of flips in this game will be winners for me:
HH
HTH
HTTH
TT
THT
THHT
All other sequences will be winners for you.
Do we have a wager?
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 28th, 2019 at 7:33:04 AM
permalink
I have been asked to make a post explaining that netzer has reached her new member posting limit. So netzer will be delayed before returning to this or any other thread.
The race is not always to the swift, nor the battle to the strong; but that is the way to bet.
January 28th, 2019 at 8:39:19 AM
permalink
-deleted-
Last edited by: ssho88 on Jan 28, 2019
January 28th, 2019 at 6:09:27 PM
permalink
Quote: CrystalMathQuote: netzer
(-q+2)/(q^2-2q+1) with the interval of convergence being for q between q = +1 and -1. Multiply this by p to get eH.
To get eT merely swap p and q then e = peH + qeT
e = p(-q+2)/(q^2-2q+1) + q(-p+2)/(p^2-2p+1)
The error here is that eH=p(-q+2)/(q^2-2q+1) and you must multiply by p again when you calculate e.
So, e = p^2(-q+2)/(q^2-2q+1) + q^2(-p+2)/(p^2-2p+1)
This simplifies to e = p^2(-q+2)/(1-q)^2 + q^2(-p+2)/(1-p)^2
e = p^2(-q+2)/p^2 + q^2(-p+2)/q^2
e = (-q+2) + (-p+2)
e = 4-q-p
e = 3
You are absolutely correct !
My not so "recognised" method(100 million trials simulation) shown that the answer, aveflips = 3.00000824, for any p value( 0<p<1).
Does it worth quarter cup of beer ? LOL
For s = 1 To t Step 1
probh = UniformRand(0, 1)
prob1 = UniformRand(0, 1)
n = 1
Do
probn = UniformRand(0, 1)
n = n + 1
Loop Until prob1 <= probh And probn <= probh Or prob1 > probh And probn > probh
flipnos = flipnos + n
Next
aveflips = flipnos / t
Any comments are welcome
January 28th, 2019 at 6:43:06 PM
permalink
Quote: ssho88
Any comments are welcome
What is the probability that ssho88=shoshone=netzer=statman ?
I heart Crystal Math.
January 28th, 2019 at 11:12:19 PM
permalink
Quote: CrystalMathWhat is the probability that ssho88=shoshone=netzer=statman ?
If ssho88 = netzer, then I(ssho88) should aware of what netzer posted here, but in reality, I am totally not aware I have posted something what netzer have posted, so ssho88 <> netzer.
Therefore, probability that ssho88=shoshone=netzer=statman = 0 ! LOL
