The Coin Flip Game that Stumped Twitter: Alice HH vs Bob HT
Вставка
- Опубліковано 29 чер 2024
- Who is more likely to win after 100 flips? Alice, who scores for every Heads-Heads, or Bob who scores for every Heads-Tails? An intuitive answer involving a dog on a soccer field is presented. Links below.
Link to python code:
colab.research.google.com/dri...
Link to written version of proof:
publish.obsidian.md/nicam/Fun...
0:00 Twitter’s Alice Heads-Heads vs Bob Heads-Tails coin flip problem
1:06 Histograms for individual scores
2:12 Extra points for TT makes them indistinguishable
3:17 The answer
5:12 Intuition by Soccer Game and Dog Analogy
7:38 Why is the coin flip game like the soccer analogy
9:40 Markov chain for the game Score Difference X_t and Last Coin C_t
13:28 The Victory Point Function
14:38 Value Functions
16:05 Recursion Relation Update Rules for the Value Function
18:35 Computer plot of value functions
23:47 Why Bob has an advantage explained with value functions
28:30 Conclusion
This is awesome! There's a nice analogy, there's Math theory, there's code and a good visual representation. Your explanation is insightful and clear. Anything one could hope for watching the solution to a puzzle. Really inspiring stuff, man!
Thank you so much for the kind words! I'm glad people seem to be appreciating it :)
Interstingly, the expected value for the score difference is 0, and it doesn't contradict this result! Alice's less frequent victories simply have a larger score difference on average than Bob's more consistent victories, and it all cancels out!
This is easier to see when you look at just 3 flips. Bob wins by 1 in three of the games. Alice only wins twice, but wins by 2 in one of the games.
This is actually how I came to the answer. Their average result is the same, so the average score difference must be 0. Alice can win by larger margins (potentially 99-0, while Bob's best win is 0-50), so the distribution must be skewed. Therefore, bob wins more.
@@cadekachelmeier7251 It's basically probability gerrymandering.
You dump a bunch of points from one side into rounds that don't matter to increase the number of rounds that the other side wins by a small margin.
@@cristoferwolz-romberger3835 Damn this is an amazing insight. Thanks
@cristofer, It’s true that Alice can win by higher margins, but I believe you’re reasoning is still inconclusive.
Even though she COULD win by higher margins, a more precise argument should show THAT if she wins, it is more often by higher margins (and therefore less frequently, because as you say the expected difference of their scores is 0)
Statisticians after doing 4 continuous hours of complex math:
yeah this may or may not happen
At one point when I was actually working on part of this, there is a certain probability that is exactly 50% and I was trying to prove why. My brain goes: "well it either happens or it doesnt. 50%"
@@mcnica89 which part was that?
@@charliefranklin8523 If for any number n, you play until Bob scores exactly n points, then the probability of Bob winning is exactly 50%. From knowing this, you can fix it up to calculate the probability Bob wins after 100 flips.
new Monty Hall problem just dropped
Would make for a great casino game with a very non-obvious house edge
My first reaction: it only takes 3 flips for Alice to get 2 points, whereas it requires 4 for Bob
In the best case scenario, yes
Best case being for A: HHH and best case being for B: HTHT.
But the moment it’s a T it’s back to 2 flips for either to get a point.
@@timtjtimBut if we look at all 16 four flip permutations, it gets worse for Bob. 3 permutations give him 1 point and 1 gives him 2 points for 4 ways to score and 5 points. For Alice 3 permutations give her 1 point, 2 give her 2 points, and 1 gives her 3 points. 6 ways to score and 9 points. She has both more chances and a higher average. (I should watch the video now!)
Another way of looking at it: it is more difficult for Alice to catch up to Bob when he's ahead, than it is for Bob to catch up when Alice is ahead. This is neatly shown when you reason it from position 97 or 98
@@northgrave I really like this approach using permutations
As soon as you suggested the dog running onto the field when Bob scores, preventing both teams from scoring, I very quickly realized why that's applicable in the coin flip scenario. Excellent analogy.
A cool use case of this occurred when the “hot hand fallacy” (the belief that basketball players who score a shot are not more likely to score the next shot) was reviewed. Originally statisticians found that it is indeed a fallacy and people aren’t more likely to score based on whether their previous shot was a made one, but it was found that a major statistical flaw was present in their workings. For any finite sequence of iid coin flips the expected proportion of HT will always be higher than HH (converging to equivalent as sequence length approaches infinity, but getting further apart from the ‘naive’ expectation the longer the chain of H’s). This means when analysing a series of misses and makes you expect there to be more makes followed by misses than makes followed by makes. Highly recommend reading miller and sanjurjo’s paper for those intrigued.
I briefly looked at this...it looks really interesting! Thanks for sharing
Isn't the "hot hand fallacy" the belief that they ARE more likely to make the next shot after a make?
Thanks for sharing this this sounds like an interesting paper.
In order to test the hot-hand hypothesis, wouldn't it suffice to estimate P(X_n=1|X_{n-1}=1), where X=1 is a made shot, and compare it to P(X_n=1|X_{n-1}=0)? Naively, I don't see why one would care about the joint distribution of two subsequent shots.
Btw, according to the distributions displayed at the beginning of this video, I don't think that the expected proportion of HT is higher than the expected proportion of HH. What is true is that the expected difference in the proportions is greater than zero. I.e. it is the expectation of the differences, not the difference in the expectations.
[Edit] as Max correctly points out in his reply my last paragraph is a little non-sensical due to the linearity of expectation. What I should have said is that "it is not the difference in the expectations, it is the expectation of the indication function that the difference in the proportions is positive.
Trying to clear up a few things: First, by linearity of expectation, the expectation of the difference in points equals the difference in expectations, and both are equal to 0. It is just the distribution that changes: For example, you can in principle get up to 99 HH in a row, but you can only get a maximum of 50 HT. So Alice can win by a larger margin than Bob can. To make up for this (in expectation they have the same number of points), Alice wins a bit more often.
I had a look at the paper. There is no question that the hot hands fallacy, i.e. the belief that one event makes another independent event more likely, is a fallacy. The question was rather how to analyze a specific sports dataset to evaluate if there is a hot hand effect in this dataset. The authors argue that the statistical estimators used by a previous set of researchers was not appropriate to test for the effect because of a related phenomenon to the Alice-Bob phenomenon.
@@JanischMaximilianthanks, you are right of course, I edited my comment
Creating a program for this, and running the same simulation 10,000,000 times, the following values appeared:
Alice won 4,576,558 times
Bob won 4,859,705 times
They drew 563,737 times
So it's pretty spot on compared to the probabilities at 3:22
is this the Monte Carlo method?
(sorry if it's a dumb question, I'm new to statistics and English)
Looking at the definition given on Wikipedia, yes, it seems to be
yes
Beautifull! I ran a montecarlo sim to check the results and thought I did something wrong when I saw that Bob had the advantage.your explanation made everything clear. Thanks for the content man!
Every time a head comes up there is an equal opportunity to score on the next throw, so if you enumerate all possible results they score the same number of points. Alice can get a higher score than Bob in a single game. With six throws Bob's best win is 3-0 (HTHTHT) but Alice can win 5-0 (HHHHHH). Alice has more decisive victories but they score the same number of points across all possible games so Bob must win more often.
Good anlogy regarding wasting time in the game only after Bob scores. 🎉
I caught on when you started talking about it.
Glad it made sense for you! Someone on twitter called what I was describing a "cooldown", which is a good word to describe it.
I like thinking about the "end game". Tie game, two turns left, Heads was last flipped... what could happen next?
If it's tails, Bob takes the lead, and indeed the game, as he has victory locked up; there's not enough coin flips for Alice to mount a comeback.
If it's heads, Alice takes the lead, and *could* even grow her lead (but a win is just a win, no matter by how much), while Bob could also come back and score a tie.
That situation seems straightforward to work out mentally, clearly demonstrating an advantage for Bob. From there, it doesn't seem hard to extrapolate that even if it's 50-50 up until that endgame, there will always be some advantage for Bob.
Good puzzle!
the intuition with the dog makes total sense. thanks, very interesting problem.
I'm glad it made sense to you :)
simple answer: while HT is just as likely as HH for a two-coin pairing, HH combinations can overlap while HT combinations cannot. After scoring a point, there is a 50% chance that Alice will score again. Bob gets no such equivalent chance. Therefore Alice has a higher chance to win.
Another way of noting it is that while each pair's individual odds to score are equal to both side, Alice's theoretical maximum is 99 points to Bob's 50. Therefore she is getting more chances to score.
Edit: Well shit my answer is wrong.
I love this kind of reasoning! Thank you for posting :) The correct answer is Bob: can you figure out where you went wrong in your thinking?
I think there's an answer to be found by going down the path by making a modified geometric series out of how many H's in a row are likely to happen.
Intuitively, Alice loses 1 point for a single H, breaks even for a double H, and benefits from any multiple larger than 2. But the first two terms of the 1/2 geometric series are 75% of the asymptotic value. So it's some combination of 0/2 + 1/4 + 2/8 + 3/16 ... - 1.
@@dojelnotmyrealname4018 This is related to what is going to be in the follow up video to prove the 1/2sqrt(pi t) formula!
I had the exact same thought, until I watched more video. I think the conclusion that you can rightfully draw from this line of reasoning, though, is that when Alice wins, she's likely to win by more? Does that seem right? So, if the total number of Alice points equals the total number of Bob points over many many games, then the number of Bob wins - the number of games when the margin of victory is narrower - has to be greater... maybe? Don't rightly know if this stands up to rigor.
@@hughobyrne2588 I think there's a simple case of pigeonhole principle. She's in the lead less often, but overall her average lead matches Bob's, so the same amount over a smaller set of options means each option would need to be more filled.
Come to think of it, that's basically one of the principles behind gerrymandering.
Somehow when this was going around Twitter, it never occurred to me think of it as a Markov chain. But then I opened this video and was like "obviously you can solve this with a Markov chain" and then felt validated that that's what you did.
Ya! It makes it a polynomial time algorithm to solve all the exact probabilities, and then it fits on the computer nicely
Mihai: I'm gonna describe a situation that we're more familiar with, a Soccer game.
Me: Oops, I'm in the wrong classroom.
Stunning video: fascinating topic and explanation allows for even me to understand where you're coming from on each step.
Thank you! Glad you enjoyed it!
That analogy is so smart… you are an amazing teacher
Amazing video! I'm not the biggest fan of probability but something about the way you shared intuition for this seemingly simple problem is absolutely beautiful.
Thank you so much for saying that! Hope to get you hooked on probability too :)
I intuitively guessed the correct answer, but getting my head around why took a bit of effort. It helped me to look at just a 3 coin toss. I found that the expected number of points for Bob and Alice were the same, but two of Alice's points come from a single win when the result is HHH. The only other winning outcome for her is THH. Bob has three winning outcomes: HTH,HTT and THT.
Easy explanation: The difference (Alice - Bob) is a random walk with mean zero. Every time after it goes up (HH) it immediately takes another step, while after it goes down (HT) it could hit a dry sequence of tails before taking another step. So the walk has the tendency to stay low and that's the advantage for Bob.
THAT is the exactly the explanation I needed to intuitively "get" why the "dog" is an advantage for Bob!
This is really well laid out. Thanks for a great vid!
Dog on the field, very nice analogy, immediately understood the whole thing intuitively. Nice vid.
i hope Dr Litt sees this, honestly the only intuition to proof that ive seen proposed
He saw and retweeted :)
Knew it was Bob from the initial question. It's the same problem you get from modelling the value of the ability to pause the clock with timeouts toward the end of a sporting event. But I'm quite surprised by the magnitude of the effect.
My guess would have been closer to 0.3% than the 3% it turned out to be. That's over half a point worth of value.
Lovely analogy that instantly made it intuitive, nice!
Really intuitive explanation! Great vid
Thanks!
The explanation that felt the most intuitive to me emerges from this short series of observations:
- There are only points on the line when the previous result is H
- If the previous result is H, both players have a 50% chance of scoring (therefore, for an infinite game, the odds are even)
- A win for alice is always followed by either another win or a win for bob (i.e. the sequence produced by adding H or T to a sequence ending with HH will always end with HH or HT)
- Therefore, if the last pair of heads is anything other than HH, we know that the last point of the game went to Bob, which is a 3/4 chance.
Ergo, in a game in which x points are scored, Point 1 through Point x-1 have a 50/50 chance of going either way, but Point x has a 75% chance of going to bob, which gives him the slightest edge.
Now that i spell it out i guess it still isnt that intuitive, but it basically comes back around to "the game is more likely to end after a Bob win than an Alice win, giving him a slight edge"
I couldn't wrap my head around this until I saw the distributions themselves:
Points Distribution:
HHHHH = Alice + 4
HHHHT = Alice +3, Bob +1
HHHTH = Alice +2, Bob +1
HHHTT = Alice +2, Bob +1
HHTHH = Alice +2, Bob +1
HHTHT = Alice +1, Bob +2
HHTTH = Alice +1, Bob +1
HHTTT = Alice +1, Bob +1
HTTHH = Alice +1, Bob +1
HTTHT = Bob +2
HTTTH = Bob +1
HTTTT = Bob +1
HTHHH = Alice +2, Bob +1
HTHHT = Alice +1, Bob +2
HTHTH = Bob +2
HTHTT = Bob +2
I realized that Alice and Bob's total scores if every combination happened was equal for sets of 2, 3, 4, 5, etc. BUT!!!
Advantage distribution:
Alice +4 = 1
Alice +2 = 1
Alice +1 = 4
Equal = 3
Bob +1 = 4
Bob +2 = 3
Alice loses the number game because she is reliant on getting that single +4 string while Bob is more flexible and thus more likely to have a win.
Thank you, professor, for this stimulant problem. I thought of a simplest way to prove that Bob wins in the most of case. This is my reasoning: I represent all issues as a binary tree going from the level 0 to the level 100. When in a node (H or T), I toss the coin and have H or T for the next level, then mark the node with +1 if Alice wins, and -1 if Bob wins and 0 otherwise. When all my tree is full, I have certainly 0 as sum of all the nodes (because on each node I have +1, I have a node with -1 just at the same stage). Now I go to the leaves at the level 100 (I have 2 power 100 leaves). For each leaf (i), I sum the points from the root to the leaf, call it S(i), the Alice wins if S(i) is positive, Bob wins if it is negative, and no one wins at 0. The I must count the number of win leaves for each player. A player wins the game if it wins in more leaves. Or the sum of all S(i) must be 0 (because a each level the some of points is 0), so the sum of S(i such Alice wins) is the opposite of S(I such Bob wins). But when Alice wins, she wins with a major score (because of the possibility of succession of H, example Alice can win with score 100, and the best score for Bob is 50, and more precisely for ever branch where Bob wins we can find a branch where Alice wins with best score, so the mean for Bob is less then Alice), then in the count of leaves Bob must wins.
I hope that my reasoning was clear. And my English understandable.
Thank you very much.
Thanks for the detailed comment! Your English is very good and I can understand what you've written perfectly well. Actually, this is exactly how I originally was thinking about the problem!
Unfortunately, I was not able to see how to make this argument rigorous and I suspect that it actually is not easy to make it work this way. One way to see that the argument will be difficult to make rigorous is that if you give Alice a point for HH or TT and Bob a point for HT or TT (like in the video at 2:12), then its still Bob who is more likely to win (who wins the game is identical to the original problem), but Alice is no longer "more streaky" than Bob: they both have the same identical distribution now (namely a Binomial(99,1/2) ). This is why I wanted to show this in the video: the problem is actually I think more subtle than is thought of at first thought.
@@mcnica89 thank you professor. I will try to keep it clearer, and send it to you by mail if it is possible.
This is a great argument.
Very cool! Thank you. I have seen value functions in the context of MDPs / RL but nice to think of them in context of more classic problems in probability. Any recommended reference / books on the topic?
A great book for this is "Probability with Martingales" by Williams. It is mentioned in this video ua-cam.com/video/t8xqMxlZz9Y/v-deo.html where a really nice problem is solved (again by essentially using value functions!)
Possibly the easier way to intuit it is to ask how much Alice or Bob can win by. The average score difference is 0, but when you get 100 heads in a row Alice wins by 99. Optimal for bob is only 50. We can then ask the question, given the games that Bob won, what was the average score difference? Likewise with Alice, we can ask what the score difference when Alice wins? Lets annotate then S|B as average score given Bob won, S|A as average score given Alice won, and score given a tie, S|T, which is zero. P(A) is the probability that Alice wins, and so on. The average score is P(B)*S|B + P(A)*S|A + P(T)*S|A. The score given a tie is zero, so that disappears. We can see by analysing the game that the average score difference is zero. This means that P(B)*S|B = -P(A)*S|A.
The fact that Alice can win by more implies that she will win less frequently. Not strictly rigorous, as we cannot always get from looking at the peak win to the average win, but a useful estimation trick in my experience.
Yes I was never able to make this rigourous....the fact that if when you give Alice points for HH or TT and Bob points for HT or TT makes their individual point distributions the same but doesn't change the chances of whose winning I think makes it quite tricky to reason around in my view. It would be cool to see an argument based off this though if possible!
What's equal is the probability of both having score the same goals after large enough N matches. But scoring equally goals does not mean matches are won equally since 1-0 is a win, but so does 5-0.
Alice is then more likely to win by a greater difference of goals, because a sequence of HH is intuitively easier, at the cost of loosing more matches.
Great video! Thanks Mihai
Thank you!
I would explain this by invoking dependent vs independent probability. Because the game is written up as a single chain of 100 rolls where the pairs are dependent, the probability can deviate from the obvious answer assuming independent samples that they should be even. In other words if you played the game such that you rolled 50 independent pairs, then the chances of winning would be 50/50. But since the rolls are dependent, the H assumed for the first roll in either scoring scenario influences the rest of possible scores
So it’s the finite length of the game that gives advantage to Bob. Makes sense.
How would a 4 player variant of the game go?
Naïvely, I'm thinking the analysis presented here doesn't interfere with itself. So the HH/HT and TT/TH can be analyzed separately to get expected points, giving us a double tie between the alternating options winning, then the constant options 1/2sqrt(nt) behind.
Is that valid, or is there some part of the reasoning I've caught on?
Great idea! I haven't thought about this....my hunch is it becomes quite a bit more complicated since keeping track of who is winning is no longer 1 dimensional (i.e. you need to keep track of at least two numbers instead of one). Would be interesting for sure though!
Thanks for this! Was looking for a proof that I was satisfied with. When I first saw the problem, my intuition was that for any finite N flips, E[score difference at time: N-(time of last win - 1)] = 0. At the next flip either Alice or Bob wins with equal probability, whoever wins would now have a higher chance of winning. If Bob wins, Alice has to “wait” for the next heads so Bob is effectively time wasting meaning Alice has less time than Bob to catch up compared to how much time Bob has to catch up if Alice wins.
Ya this is the right idea!
Markov chains is a nice cameo. Is there a generalization that would allow to solve a similar problem with combinations of length three instead of two?
Amazing video! 👏
Thank you!
Once Bon wins a point, the probability of either of them winning a point the next flip goes to 0, when Alice wins, it goes back to 50\50
Lovely... I'm gonna have some fun with this one
You can see the phenomenon early on with just 3 flips. Of the 8 scenarios, 2 have Alice winning (HHH, THH), 3 have Bob winning (HTH, HTT, THT) and 3 have a tie (HHT, TTH, TTT)
Who made the music is playing in the background? Great video btw
it's very fitting that the dog runs out on the field every time "tails" comes up! XD
In my head the dog is called Tails
Before I watch the vid:
- reminds me on Penney's paradox
- by linearity of expectation, both are expected to get 99/4 = 24.75
Let's go case by case:
- Start (State 1)
T or H?
- If T, same as start (State 1)
- If H, both just need 1 more (State 2)
- T or H?
- If T, Bob gets points, go back to state 1
- If H, Alice gets points, back to state 2.
So essentially we're asking to look at all the heads and see if there's more tails or heads afterwards.
I think that would slightly favor Bob since if we look at a heads, that removes 1 possible heads (i.e. let's assume there's 50 heads and 50 tails, looking after a heads, means the next is 49.49% to be heads vs 50.51% to be tails).
As a quick example, let's look at the case were there's only 3 flips.
HHH - Alice wins 2-0
HHT - tied 1-1
HTH - Bob wins 1-0
THH - Alice wins 1-0
HTT - Bob wins 1-0
THT - Bob wins 1-0
TTH - Tied 0-0
TTT - Tied 0-0
So Bob won 3x, Alice won 2x and 3 ties. As we expected both are expected to get 2/4 = 0.5 per game, but the key insight is that when Alice wins, she wins by a bigger margin on average, so Bobs will win more often by a smaller margin
This issue is what kind of messes up research into the hot hand effects since looking after a score creates a sampling bias that reduces the chance of scoring (only in hindsight, not going forward)
24:00
Also reminds me about going for 2 in the NFL, you only need to win by 1 (kick XP), but if down 2, the 2PAT could save you.
Iterating this to it's extreme, down 42 with 6 TDs, using the optimal 2PAT strategy gives a 72.66% win% despite the expected score diff being 0
If a heads just occurred, they're both equally likely to score. So every time alice scores, bob could also score next round. But if a tails just occurred, they're both two away from potentially scoring. So when bob scores, alice is locked out for a turn. Alice's sequence may be able to self-intersect, but on a fair coin a run of heads is going to show up less often than alternation. I think any advantage she might have had from that is engulfed by her requiring (at least) a triple heads to ever benefit from it, which is going to be less likely than a sequence of three flips containing at least one tails. To contrast, I think if alice scored on "HTHT" and bob scored on "HHTT", the situation would match people's general intuition.
I intuitively picked Bob, by a hand-wavy sort of version of your proof. I asked, "Who is more likely to have scored last at any given point?" The answer to this question is Bob, because Bob scored last in every sequence that ends in a tails, but he also scored last in sequences that end in exactly one heads. This reasoning holds at every point in the game going right back to the beginning, so it seemed sensible that Bob maintains a small advantage.
This is a nice way to approximate pi :)
The part about adding the TT points to both is crazy to me. I think I understand that that makes their distribution of points identical, but my brain refuses to accept that they can have identical distributions of points with Bob still having an advantage to win. Really great video! Super well done! Bob scoring and then stalling makes sense as a "strategy". Alice being able to rally a bunch of points also feels like an effective "strategy" but for winning more decisively not necessarily more consistently. It feels like Bob is playing defensively while Alice is playing offensively and the old adage "offense wins games, defense wins championships" comes to mind. Thanks again!
Very interesting. What if we consider a modified version of the game “Alice HH vs Bob TH”, so Bob now score for every “TH” instead of “HT”.
Intuitively it seems that the answer should be the same: Bob is more likely to win (I checked, it is indeed the case). However, I do not know how to apply your argument with the dog now.
I guess here we should just say: if C=H, both are as likely to earn a point, but if C=T, only Bob can score on the next time step. So instead of the dog, I would say that “special rule” is that a brick wall randomly appears in front of Bob’s goals and it stays there until Bob scores. Once Bob scores, wall is removed and both players are equally likely to score again.
Great video! This averaging feels like convolution, which feels like diffusion. The limiting process of a discrete random walk is Brownian motion. What would be the limiting process (continuous time, continuous space) for this more complicated Markov chain?
I like the music you chose
Since they have the same expected score, but Bob is expected to win, it is reasonable to assume that Bob is more likely to lead by a small margin if he wins, while Alice is more likely to lead by a larger margin if she wins. This also meshes well with Alice's ability to score points several throws in a row, while Bob can't: It is easier for Alice to get extremely good scores, while Bob's scores are usually more moderate. Which again is what we see in the probability distribution plot at the start.
Assume any divisible by 4 flip count. Consider all 16 length 4 subsequences. Now all subsequences are equally likely (this is key). We take a look and see half start with H, half end with H. So half the sequences end in H and from there have a 50% of point for Bob or Point for Alice. QED.
Awesome video
Thanks!
The way I concluded Bob would come out on top is absolutely not rigorous, but I wondered if it could be improved upon.
I considered any chain of flips beginning with a head. Using Alice scoring as +1 and Bob as -1 you would have the expected value of the chain as
1/2*(-1) + 1/4*0 + 1/8*1 + 1/16*2 + 1/32*3 +...
I didn't care to calculate this limit but I figured it had to be negative due to how quickly the terms decrease, and as such you only have to consider how big of an effect the potential for the 100 flips to end on a sequence of Heads is and if that is strong enough to outweigh the expected value of the individual sequences
great vid!
I knew this result from the same game played with a choice of triplet results, as originally invented by Walter Penney back in 1969 (10 years before I was born, but I read a lot of mathematics books and journals as a kid for fun).
Of course you publish this proof and video AFTER my stats class is over so I can't show this to them.
When I saw this I did expected value after a Head comes up till the next Tails
Bob *ALWAYS* 1 point when the next Tails comes up
Alice scores 0 points 1/2 the time (next flip is Tails 1/2 the time), 1 point 1/4 the time (HT), 2 points 1/8 the time (HHT), etc
thus Alice's Expected value after a Heads till the next tails is SUM_{n>0} \dfrac{n}{2^{n+1}} which choose your method to find that sum (differeicent 1/x^n and plug in 2 etc) which comes out to 1 as well
HOWEVER this realizes on going on forever as if you aren't going past say 128 flips after a heads you are missing the tail of the sum for Alice thus cutting it off always gives an Edge to Bob.
so basically they both have the same chance to score but after Bob scores his coach lets the timer run down while Alice's uses a time-out
I went with Bob after some thinking, but mostly inuition -- I pretty immediately suspected they wouldn't be equal. I am very familiar with a 3-value version of this (where you score if a specific set of 3 values shows up), that game has a much more drastic difference between the players for certain combinations. (HHH / THH - the most extreme example, where the first pattern "HHH" can only ever "win" if it shows up as the first 3 coinflips of the game, otherwise, once a single tails is shown, the second player always scores first, as the first player cannot score without the second player getting a point first -- this version of the game was only "who gets the first showing", rather than who had the most, too)
In your game, it made sense to me that any time alice has a run, bob automatically gets a point at the end of the run. This means that alice's most common two runs: "HHT" and "HHHT" are automatically going to result in a draw for the former, and a lead of just +1 for the latter, meanwhile bob's run can score without alice getting points.
Alice getting "luckier" runs that go longer are just as likely as bob getting repeat scores of his own too, hence why bob wins in this scenario. -- not a formal proof, but it was enough for me to vote relatively confidently in the poll at least.
I find myself having a hard time interpreting the charts of the victory function that are on screen from minute 19 onwards.
Can someone break it down for me? If I try to explain it, I think I'm just going to confuse myself more.
I feel like that missing "this is how you interpret this visual information" is the one big flaw in this video.
Thanks for the feedback, this is helpful to know! The y axis (and the y values bring plotted) are the expected VP for the *end of the* game (where Alice gets +1 VP for winning and it's -1 VP if Bob wins). For example if this is 0, they are equally likely to win; if it's positive Alice is more likely to win than Bob. The x-axis is the *current* goal difference. So for example x=1 on the plot where t=99 means this is the result when Alice is *winning by 1* at time *t=99*.
How is it scored if we get HHHHHT 4 points for Alice and 1 for bob?
Yes that's right
Fun follow up question: If we had an infinite sequence of score differences, and randomly checked some element of the sequence if Bob or Alice is winning, would the probabilities of them winning in that step be equal?
Interesting! I thought Alice would have a higher probability of winning because her scoring condition is symmetric whereas Bob is order dependent.
im not good at math so i just calculated by hand every outcome for just 2 steps from point (0,H). kinda obvious there is an advantage and how it occurs.
I think the thing that breaks intuition here is that the results depend on the game having a fixed length. If the game stopped after one player reached a certain number of points, it would be different!
(If I'm not mistaken, that case really IS 50/50.)
I havent seen this video yet but I found them to have tied.
imagine grouping every THHH...HHT into chunks (ignoring consecutive tails completely)
the expected value of every chunk for Bob is 1
the expected value of every chunk for Alice is 1/4 + 2/8 + 3/16 + 4/32... = 1
Since the expected values are both 1, they should tie in the long run, no? unless this question doesn't ask for a long run
Both Alice and Bob have the same expected value (namely 99/4), but the chance of Bob winning is slightly higher than Alice winning. (Its also true that Bob's advantage goes to zero in the "long-run")
Yes this is correct, and this is roughly how I would prove that as the length of the game approaches infinity, the outcome approaches 50/50. However, this logic doesn't hold for a finite game.
awesome
Is Bob still in the advantage if he needs a "TH"?
Best intuition I have for this problem.
We know that any given flip has an expected point value of 0.5
Heads results => that the next flip, regardless of what it is, will result in a point. So the next flip is worth more than an average flip.
Tails results => that the next flip, regardless of what it is, will result in no points. So the next flip is worth less than an average flip.
Alice only scores on Heads. Bob only scores on Tails.
So the +1 point advantage Alice gains from a Heads result means less than the +1 advantage Bob gets on a Tails result because there are more points to be had in a game with a Heads result.
The longer the game goes on, the less this advantage matters because a longer game also means more points to be had, diluting the effect.
Whenever Alice gets a point Bob has an equal chanve to get a point on the next flip as Alice, but when Bob gets a point neither of them have a chance to get another point on the next flip. So over time i think Bob eeks it out
Interesting, the limited amount of rounds is what driving bobs advantage. What are the odds if it was the first to 100 points?
Bob has an even bigger advantage in that case! This is actually how the analysis goes to prove the 1/2sqrt(pi t) formula
That makes sense because Alice would need to get 3 heads or more in a row to gain a lead while bob can maintain his lead if there's a tail in the first 2 flips after the first head. In another view point, bob is close to guaranteed to gain a 1 point after the first head while alice is not.
I wonder what application this has in the real world outside of sports?
@@mcnica89That doesn't seem right. If it's the first to 100 points, with potentially unlimited rounds, Bob loses his advantage and the odds revert to 50:50. I ran a simulation of 10 million trials to check, and Alice came out very slightly ahead.
@@simonrorton Yes I think you are right: the scenario I was talking about before was (incorrectly) the scenario where you end when *Bob* has 100 points. (The difference being is that ties are possible now).
My hand-wavey argument was: In the infinite case, on the transition to heads, alice has a 1/2 chance of scoring once, a 1/4 chance of scoring twice, so on and so forth. Bob will score exactly once. Summing up alice's infinite series gives an expected value of 1, and bob of 1 as well. However, since we're truncating the game, the tail end of alice's infinite series is cut off, giving bob a slight advantage.
It feels like a good argument, but it's wrong, sadly, I think because if alice wins on a streak, then bob doesn't get a point :((
What is the math accounting for Alice able to score 2 with 3 flips "HHH" vs Bob needing 4 flips "HTHT"?
My intuition told me that gave Alice an advantage, but was not addressed in the video from my novice understanding.
Thank you for the video and increased understanding!
I don't know about the math - but the intuition is that it's not actually that good for you to score 2. What you want is stay 1 point ahead of your opponent and hang on until the game ends. "Using up your luck" to win by more than 1 point is actually suboptimal.
Even at 3 flips bob is more likely to win. While Alice can win 2-0 in one scenario, of the 8 possible scenarios Alice wins 2, Bob wins 3, and 3 are tied.
I'll note that you get the same probabilities of Bob winning if he scores a point on TH instead of HT. I guess the corresponding soccer intuition would be that every so often a dog runs on the field, and only Bob can score immediately after the dog runs onto the field?
I don't know if there is a nice intuition for this one! However, if you simply reverse the sequence of counflips, youll see that TH vs HH is the same as HT vs HH
@@mcnica89 Side note - I just ran 100k simulations on different 4 length sequences, and the biggest difference comes from a sequence of HHHH vs HHHT (or the similar analogues of it). The HHHT wins around 49% of the time, while the HHHH only wins 39% of the time. I imagine that if I extend it to a sequence longer than 100 flips, that number may change some, but I was surprised at how big of a difference it already hits at a sequence length of only 4.
Another matchup that I don't know if I have the intuition for which would beat which and what I got from it:
THHT (41%) vs TTHH (43%)
And then you get ones where the difference between them is the same, but they have a different rate of ties - it's very surprising to me that these two have a different rate of ties.
HHTT (46.3%) vs HTHT (43.5%) vs tie (10.2%)
HHHT (45.7%) vs HTHT (42.9%) vs tie (11.4%)
Particularly surprising that they're different given that if I make the other matchup there, it's even:
HHTT (41.8%) vs HHHT (41.8%) vs tie (16.4%)
I almost wonder if it’s even more important to outline that that any time there is an H, there will be a T at some point, so bob always has the assurance that he will gain one point, while alice does not get any sort of assurance when an H shows up.
That's not true, though - there may be a string of H until the end of the game.
I like to try these things myself, and as i usually do with these i started with the simplest case and did it manually. At n = 2, it's equal. At n = 2, bob already wins 3 of possible 8 games and Alice only 2. I also noticed Alice can score 2, but bob doesn't. At n = 4, the pattern continued: Alice has higher maximum scores, but bob is more likely to score in a game. Their average score is the same. The key is that you only need to win by one, so Alice wastes a lot of points, e.g., HHHH Alice beats Bob by 3 points, essentially wasting 2 points. This actually kinda reminds me of FPTP voting. It's better to win a smaller minority in more ridings than a big majority in just a few ridings.
Let me see if I can summarize the video:
1. When Bob is ahead in the score, it is tails, which means it takes up 2 whole turns.
2. When Bob is losing, Alice does not waste any time, as Bob is just as likely to score.
To answer - When Bob is ahead, they are more likely to stay ahead slightly longer at the end of the game, increasing the chance of victory
Some quick guessing:
1. Obviously both A and B has the same expected score of 99/4
2. A *could* get large scores as high as 99, while B can only get at most 50
3. Tian Ji’s Horse Racing Strategy comes into my mind so I'm guessing B will win more.
en.wikipedia.org/wiki/Tian_Ji
Flip it 3 times. Alice wins 2/8, Bob wins 3/8 and Nobody wins 3/8. It's kind of obvious to stick with Bob.
It would be equal odds if the question is who would have the max points at the end.
The E(' who wins eventually') is significantly impacted by the the choice of "HH, TH" combination. Now on to the video!
I have noticed that the case n=3 flips is bad for Team HH, and I suspect an induction might work. But I'm not sure yet.
T start reduces to n=2, with 1W 2D 1L outcomes. But HT is a loss, and HH only wins half and draws half.
Key idea is to not conflate...
Probability with expected value.
For every H that comes up, it increases total H count, so Alice should be slightly favored I think. Another ay to say it is that Alice can string together wins but Bob cant.
Oops im wrong because I was thinking too long term. This is why I also simulate before answering if the answer matters
So if Bob instead scored with TH would Alice and Bob be equally likely to win?
I swear I’ve heard that background music before.
Both need H, which happens .5 of the time. Then Alice needs H, which can happen, but if it does, we can assume fewer H in the future, because the total portion of H in the game remains .5. Bob needs T, which is as likely as H and equally likely over the course of the game. Therefore, Bob has slightly more opportunities to win.
Another way: Bob can score right after every of Alice's scores. Alice can't score after Bob's.
This reminded me of a problem I saw long ago that was similar. Instead of discussing the person who got more overall, it was who would get it first, TH or HH. And TH is more common there, since once a tails comes up, you're guaranteed to get a point because for it to switch over to HH you would need to have it go through TH first. I think these happen for the same reason - this behavior is the dog stalling behavior in reverse, and I would conjecture that given any series of coin flips, whoever's coin flip is more likely to come up first is also more likely to win the game when counted over a long series of flips.
edit: that verison is called Penney's Game en.wikipedia.org/wiki/Penney%27s_game
I honestly thought bob was intuitive and obvious, as every chain of points alice can get will terminate with a point for bob, and the probability of alice getting at least one ahead of bob is slim.
A great way of understanding the 100-flip game is to play the 3-flip game:
HHH - A
HHT - tie
HTH - B
HTT - B
THH - A
THT - B*
TTH - tie
TTT - tie
*this one is sorta the one throwing off the tie if you think of a certain parity of HH and HT. It’s the ends of each sequence (or the ends in between sequences of TTs) that have the most impact on the score difference, and Bob wins those slightly more than Alice as seen here.
I assume that as length of game t tends to infinity, that Bob's advantage tends to 0? But I'm surprised that it goes down so slowly in the graph at 9:40. At first glance, it looks like it might have an asymptotic at like 2% or something
It goes down like 1/sqrt(t), which isn't too surprising as this is the kind of thing that happens for things governed by the Central Limit Theorem-type behaviour.
We hereby decree and had had profusely proven that indeed the individual named BOB has the ´dawg´ on hes personhood
don't know if this works but i simply tried the simplest case, a case for 3 and noticed that bob has a high probability of winning. i don't really understand induction proofs but i think since we know that the last coin flip has a 50/50 chance of being heads or tails and the same is for the next flip we can say that alices and bobs number of points increase at the same rate and thus by induction we conclude that Alice's probability of winning will never increase past bobs or something
I just threw it into a spreadsheet up to 6 flips and then scored every permutation. Alice: 21, Bob: 28, Tie: 15.
At first I said equal because I tallied up their total points across all permutations, then when I saw equal was wrong, I scored each individual permutation and got 'Bob' before the reveal.
%s still seem interesting since at n=6 it's Alice 32.81%, Bob 43.75%, and Tie 23.44%. I'd assume %s will normalize to certain values if we let n->inf
Now the question is, how do I get onto the “interesting math problems” side of Twitter?
My intuition is that Alice is more likely to win because he has the possibility of scoring multiple points in a row and Bob doesn't.
Take a similar game: Alice combi is THH, Bob Combo is HHH. Game ends as soon as either combo gets flipped. In this case it's easy to see, thaz Alice almost always wins.
Surprised that only 10% of people chose Bob.
I don't understand the intuitive proof, why is the dog coming on the field after bob scores an advantage? both bob and alice are equally likely to score, so it still seems random who would benefit. I guess the only use case is when bob is ahead, and it's the almost the end of the game, ohh i get it now.