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!
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%"
@@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.
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 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.
@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)
@@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
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.
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.
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
3 หลายเดือนก่อน +3
is this the Monte Carlo method? (sorry if it's a dumb question, I'm new to statistics and English)
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.
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 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.
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.
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.
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!
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!
I think on that game they play "first goal wins" (so whoever's sequence comes up first immediately wins and the game is over), whereas this version is "most points in 100 flips"
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.
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.
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.
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.
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.
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"
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.
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.
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
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!
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.
I wrote a simple program to simulate a million games and print out the percentage that Bob and Alice won, and your math was correct! I just generate a single 128-bit random number, such that every bit in the number will be a random 0 or 1, and then loop over the integer 100 times, bit-shifting it by i each iteration and "and"ing that with 0b11 to get the first two bits. If the value in the new integer storing the first two bits is 0, that means that Alice won, and if it is 1, that means Bob won. Pretty efficient and the math checks out!
For anyone that wants to try a similar problem that is a bit more guided can try:"15-S2-Q12 step problem". This is question 12 of step 2 at 2015. Step is Cambridge maths entrance exam.
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!
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.
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 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
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!
If you run a simulation with 3 flips: 000 - 00 wins 001 - tie between 01 and 00 010 - tie between 10 and 01 and 011 - tie between 01 and 11 100 - tie 101 - tie 110 - tie 111 - 11 wins. If you add one more digit, the win percentage for 00 and 11 only increase, each going to 2 wins, while the 01 and 10 only gain 1 win each. so I suspect in the 4 player game, 00 & 11 will have more wins, and 01 & 10 will have less wins.
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.
You can use the fact that Bob wins more often when he scores on HT (HT rules) to show that he wins more often on TH (TH rules). Just notice that for any game, you can flip the game, I.e. take the game HHTTHHT and flip it to get THHTTHH, then Bob wins the original game with HT rules iff Bob wins the flipped game with TH rules. Since for every game there is exactly one flipped version of that game, then the number of wins for the HT rules and TH rules are the same.
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)
i just did two thought experiments - if there's two flips, they're both equal, if there's three flips, then Alice scores 3 and Bob scores four, so I'd guess Bob wins because the length of the sequence shouldnt make a difference after 3 flips. that doesn't give much of an intuition for *why*, though
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.
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.
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.)
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.
I'm an amateur soccer player My takeaway from this video is that we should let a dog into the field every time we score a goal and that will increase our chances of winning Thanks!
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!
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
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
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.
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.
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?
Without having watched it, HH feels a but more likely to happen, because you can chain them so easily. For 3 coin tosses, HHH gives 2 points for Alice, while Bob has no way to get 2. with infinite throws this light equal out though Because looking at the chain of events in every state it’s either 50/50 who gets a point (after an H), or noone gets a point (after T)
After watching the video it seems I had the right idea and came to the wrong conclusion. I should have counted all victories instead of just looking at points HHH - Alice wins 2:0 HHT - Tie 1:1 HTH Bob wins 0:1 HTT - Bob wins 0:1 THH - Alice wins 1:0 THT - Bob wins 0:1 TTH - Tie 0:0 TTT - Tie 0:0 If we sum them all up it’s 4:4 tie, but Alice „wastes“ an extra point by winning harder. Funny how intuition fools you
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 :((
Naive answer before watching the video: I think Bob will win, because he always gets "the last word", so to speak. He's the only player who scores when a tail is landed. When a coin lands H, the next coin has a 50% chance to give a point for Alice or for Bob, but when a coin lands T, neither player can score a point until the next H. Any scoring opportunity for Alice is also a scoring opportunity for Bob, but only Bob can shut out the game by scoring the last point before a long sequence of Ts, thereby giving him a slight advantage over Alice.
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.
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%)
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
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.
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.
Just paused at 0:45 - shouldn't it be obvious the answer is Alice? HT only appears in one direction so-to-speak, meaning HTH is only 1 win for Bob. Meanwhile, the equally likely HHH gives Alice 2 points. That alone should immediately answer that Alice is more likely to win. If it were instead a question of same vs switch the question would be different and answer would be equal likelihood
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.
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?
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).
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
H Draw T Draw HH A HT B TH D TT D THH A THT B TTH D TTT D HHH A HHT D HTH B HTT B When adding a T (to the start of the chain), the result would be the same has the previous chain. When adding a H (to the start of the chain), Alice is wasting 1 H on a chain she’s already winning while Bob has not wasted any yet. Adding a T gives Bob the previously advantageous scenario while adding a H would grant both sides an equal amount of extra points. However, Bob is more likely to gain points in the scenarios with more T (more likely to go from Draw to Bob), while Alice is more likely to gain points in the scenarios with more H (Alice gains less overall wins). Therefore, Bob would win more than Alice.
Another intuitive way to show Bob has an advantage without using a lot calculation: We can first find that the expected values of coinflips are equal for Alice and Bob. Then we see that there are some outcomes when Alice wins by a big margin like HHHHH.... 99 for Alice 0 for Bob, but if we try HTHTHT... it's 0 for Alice and only 50 for Bob. That means that Alice's distribution is more spread out and for each outcome when Alice wins by a lot of points there are multiple outcomes when Bob wins by a little, so overall more wins for Bob
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
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.
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
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
Can’t you reverse Bob’s prediction to “TH” to make this more intuitive? If Bob scores on “TH” then he will score the first point 75% of the time. Every time that a “tails” is the result of either of the first two tosses he will score first. That gives him a small advantage even though the chance of scoring thereafter is the same.
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).
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.
Haven't watched the video yet, don't know the answer. I would guess Alice wins narrowly just because a sequence of Bob points takes more space than a sequence of Alice points.
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
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.
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.
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.
Wow, I have said Alice would win, and it wouldn't even be close. I'd expect her to get something like 50% more points than Bob on average. The result is extremely counterintuitive to me.
My not deep analyse approach would be: Alice have much more chances of scoring. After every H if it is followed by a H Alice gets a point. Alice Max points is 99. Bob has much fewer chances at scoring. After a H it should be a T and after it should be a Head again then a Tail. As I understand Bob max pointing is 50?
Yep, when Alice wins, her advantage will generally be higher than her disadvantage when Bob wins. However, given that their expected numbers of points are the same, this actually wins that overall Bob will score more game-victories (a.k.a. end with an advantage more often).
Wait, HOW DID YOU APPROXIMATE LINES INTO FORMULAS?! Is there a simple way to convert line of unknown formula back to approximate formula? Im referring to this: 5:06
No there is no way that always works. For this particular problem there is a cool trick that lets you do it. That will be the subject of the next video!
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*.
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 be honest, in the sports analogy, I don't feel like I intuitively get why the dog would be better for Bob. Here's my intuition for why Bob wins: they have same expected value and Alice can hit higher highs, which must mean Bob wins more often to compensate.
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 :)
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.
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)
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
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.
the intuition with the dog makes total sense. thanks, very interesting problem.
I'm glad it made sense to you :)
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
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.
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.
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!
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!
Mihai: I'm gonna describe a situation that we're more familiar with, a Soccer game.
Me: Oops, I'm in the wrong classroom.
This is literally the Humble-Nishiyama randomness game that Vsauce2 covered before. This is such a nice, technical perspective!
I think on that game they play "first goal wins" (so whoever's sequence comes up first immediately wins and the game is over), whereas this version is "most points in 100 flips"
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.
i hope Dr Litt sees this, honestly the only intuition to proof that ive seen proposed
He saw and retweeted :)
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!
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.
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
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.
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.
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"
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!
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.
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
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!
So it’s the finite length of the game that gives advantage to Bob. Makes sense.
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.
I wrote a simple program to simulate a million games and print out the percentage that Bob and Alice won, and your math was correct! I just generate a single 128-bit random number, such that every bit in the number will be a random 0 or 1, and then loop over the integer 100 times, bit-shifting it by i each iteration and "and"ing that with 0b11 to get the first two bits. If the value in the new integer storing the first two bits is 0, that means that Alice won, and if it is 1, that means Bob won. Pretty efficient and the math checks out!
Dog on the field, very nice analogy, immediately understood the whole thing intuitively. Nice vid.
For anyone that wants to try a similar problem that is a bit more guided can try:"15-S2-Q12 step problem". This is question 12 of step 2 at 2015. Step is Cambridge maths entrance exam.
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
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!
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.
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 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
There’s a very interesting connection between this principle and why the stats behind the “hot hand fallacy” were wrong.
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!
If you run a simulation with 3 flips:
000 - 00 wins
001 - tie between 01 and 00
010 - tie between 10 and 01 and
011 - tie between 01 and 11
100 - tie
101 - tie
110 - tie
111 - 11 wins.
If you add one more digit, the win percentage for 00 and 11 only increase, each going to 2 wins, while the 01 and 10 only gain 1 win each.
so I suspect in the 4 player game, 00 & 11 will have more wins, and 01 & 10 will have less wins.
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.
You can use the fact that Bob wins more often when he scores on HT (HT rules) to show that he wins more often on TH (TH rules). Just notice that for any game, you can flip the game, I.e. take the game HHTTHHT and flip it to get THHTTHH, then Bob wins the original game with HT rules iff Bob wins the flipped game with TH rules. Since for every game there is exactly one flipped version of that game, then the number of wins for the HT rules and TH rules are the same.
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)
Really intuitive explanation! Great vid
Thanks!
i just did two thought experiments - if there's two flips, they're both equal, if there's three flips, then Alice scores 3 and Bob scores four, so I'd guess Bob wins because the length of the sequence shouldnt make a difference after 3 flips. that doesn't give much of an intuition for *why*, though
Lovely analogy that instantly made it intuitive, nice!
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.
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.
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
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.)
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.
I'm an amateur soccer player
My takeaway from this video is that we should let a dog into the field every time we score a goal and that will increase our chances of winning
Thanks!
I wish that is the case, but look at Manchester United now, yeah...... Painful.
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!
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
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
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.
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.
This is really well laid out. Thanks for a great vid!
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?
Without having watched it, HH feels a but more likely to happen, because you can chain them so easily. For 3 coin tosses, HHH gives 2 points for Alice, while Bob has no way to get 2. with infinite throws this light equal out though
Because looking at the chain of events in every state it’s either 50/50 who gets a point (after an H), or noone gets a point (after T)
After watching the video it seems I had the right idea and came to the wrong conclusion. I should have counted all victories instead of just looking at points
HHH - Alice wins 2:0
HHT - Tie 1:1
HTH Bob wins 0:1
HTT - Bob wins 0:1
THH - Alice wins 1:0
THT - Bob wins 0:1
TTH - Tie 0:0
TTT - Tie 0:0
If we sum them all up it’s 4:4 tie, but Alice „wastes“ an extra point by winning harder.
Funny how intuition fools you
Looking back it seems I looked at 3 cases only, HHH, HHT and HTx and did not consider that the HTx case is actually 2 cases
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 :((
Who made the music is playing in the background? Great video btw
Naive answer before watching the video: I think Bob will win, because he always gets "the last word", so to speak. He's the only player who scores when a tail is landed. When a coin lands H, the next coin has a 50% chance to give a point for Alice or for Bob, but when a coin lands T, neither player can score a point until the next H. Any scoring opportunity for Alice is also a scoring opportunity for Bob, but only Bob can shut out the game by scoring the last point before a long sequence of Ts, thereby giving him a slight advantage over Alice.
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.
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%)
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
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?
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.
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.
Just paused at 0:45 - shouldn't it be obvious the answer is Alice? HT only appears in one direction so-to-speak, meaning HTH is only 1 win for Bob. Meanwhile, the equally likely HHH gives Alice 2 points. That alone should immediately answer that Alice is more likely to win.
If it were instead a question of same vs switch the question would be different and answer would be equal likelihood
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.
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
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?
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).
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
H Draw
T Draw
HH A
HT B
TH D
TT D
THH A
THT B
TTH D
TTT D
HHH A
HHT D
HTH B
HTT B
When adding a T (to the start of the chain), the result would be the same has the previous chain.
When adding a H (to the start of the chain), Alice is wasting 1 H on a chain she’s already winning while Bob has not wasted any yet.
Adding a T gives Bob the previously advantageous scenario while adding a H would grant both sides an equal amount of extra points. However, Bob is more likely to gain points in the scenarios with more T (more likely to go from Draw to Bob), while Alice is more likely to gain points in the scenarios with more H (Alice gains less overall wins).
Therefore, Bob would win more than Alice.
Interesting! I thought Alice would have a higher probability of winning because her scoring condition is symmetric whereas Bob is order dependent.
Another intuitive way to show Bob has an advantage without using a lot calculation: We can first find that the expected values of coinflips are equal for Alice and Bob. Then we see that there are some outcomes when Alice wins by a big margin like HHHHH.... 99 for Alice 0 for Bob, but if we try HTHTHT... it's 0 for Alice and only 50 for Bob. That means that Alice's distribution is more spread out and for each outcome when Alice wins by a lot of points there are multiple outcomes when Bob wins by a little, so overall more wins for Bob
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
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.
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
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
Can’t you reverse Bob’s prediction to “TH” to make this more intuitive? If Bob scores on “TH” then he will score the first point 75% of the time. Every time that a “tails” is the result of either of the first two tosses he will score first. That gives him a small advantage even though the chance of scoring thereafter is the same.
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).
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.
Haven't watched the video yet, don't know the answer. I would guess Alice wins narrowly just because a sequence of Bob points takes more space than a sequence of Alice points.
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
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.
This is a nice way to approximate pi :)
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 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.
Wow, I have said Alice would win, and it wouldn't even be close. I'd expect her to get something like 50% more points than Bob on average. The result is extremely counterintuitive to me.
My not deep analyse approach would be: Alice have much more chances of scoring.
After every H if it is followed by a H Alice gets a point. Alice Max points is 99.
Bob has much fewer chances at scoring. After a H it should be a T and after it should be a Head again then a Tail.
As I understand Bob max pointing is 50?
Yep, when Alice wins, her advantage will generally be higher than her disadvantage when Bob wins. However, given that their expected numbers of points are the same, this actually wins that overall Bob will score more game-victories (a.k.a. end with an advantage more often).
How is it scored if we get HHHHHT 4 points for Alice and 1 for bob?
Yes that's right
Wait, HOW DID YOU APPROXIMATE LINES INTO FORMULAS?! Is there a simple way to convert line of unknown formula back to approximate formula? Im referring to this: 5:06
No there is no way that always works. For this particular problem there is a cool trick that lets you do it. That will be the subject of the next video!
@@mcnica89 aw man 🥺
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*.
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 be honest, in the sports analogy, I don't feel like I intuitively get why the dog would be better for Bob.
Here's my intuition for why Bob wins: they have same expected value and Alice can hit higher highs, which must mean Bob wins more often to compensate.