Author |
Topic: Coin flip game (Read 1449 times) |
|
Deedlit
Senior Riddler
Posts: 476
|
 |
Coin flip game
« on: May 21st, 2005, 2:54am » |
 Quote  Modify
|
Based on the current discussion in "hidden signaling", I was wondering about the following problem:
Suppose there are two players, and each player picks a sequence of coin flips. A coin is flipped until one sequence or the other shows up, and the player who picked that sequence is declared the winner.
1. What are the chances of each player winning, based on the sequences chosen?
2. What is the expected number of coin flips until the game is ended?
3. How about if there are n players, each picking a different sequence?
|
| « Last Edit: May 21st, 2005, 8:33am by Deedlit » |
 IP Logged |
|
|
|
rmsgrey
Uberpuzzler
    
Gender: 
Posts: 2872
|
|
Re: Coin flip game
« Reply #1 on: May 21st, 2005, 9:04am » |
Quote Modify
|
Does either player get to know what the other player's sequence is before choosing his own?
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Coin flip game
« Reply #2 on: May 21st, 2005, 11:35am » |
Quote Modify
|
Hmmm... I wasn't thinking in terms of strategy; I was just asking for the probabilities of winning and expected length given two arbitrary sequences. But, it's an interesting question: If player 1 picks a sequence of length d, and then player 2 picks a sequence of length d knowing player 1's sequence, what's the best strategy? Obviously player 2 has a huge advantage. I can think of a strategy for player 2 that should be close to optimal, but a full solution probably requires computing the probabilities first.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Coin flip game
« Reply #3 on: May 21st, 2005, 1:16pm » |
Quote Modify
|
There is a thread on that somewhere, I think William started it.
Unfortunately I don't have time to look for it now 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Coin flip game
« Reply #4 on: May 23rd, 2005, 12:37am » |
Quote Modify
|
on May 21st, 2005, 11:35am, Deedlit wrote:| But, it's an interesting question: If player 1 picks a sequence of length d, and then player 2 picks a sequence of length d knowing player 1's sequence, what's the best strategy? Obviously player 2 has a huge advantage. I can think of a strategy for player 2 that should be close to optimal, but a full solution probably requires computing the probabilities first. |
|
If player 1 picks a sequence S1, then player’s 2 optimal strategy is to remove the last flip from S1 and prefix it by H or T (the two choices are never equally good).
on May 21st, 2005, 11:35am, Deedlit wrote:| Hmmm... I wasn't thinking in terms of strategy; I was just asking for the probabilities of winning and expected length given two arbitrary sequences. |
|
There is a nice approach to calculate the expected values; I will try to reproduce it later. One of the consequences of this is the following strange result:
Call the sequence “self-overlapping” if it’s copy may be shifted so that the 2 strings perfectly match on overlapping section. For instance, the sequence HTHTH is self-overlapping, as is shown by the following shift:
HTHTH
HTHTH
The result proved in 1966 states that no self-overlapping sequences occur in average sooner than self-overlapping sequences.
|
|
IP Logged |
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Coin flip game
« Reply #5 on: May 23rd, 2005, 1:30am » |
Quote Modify
|
on May 23rd, 2005, 12:37am, Barukh wrote:
If player 1 picks a sequence S1, then player’s 2 optimal strategy is to remove the last flip from S1 and prefix it by H or T (the two choices are never equally good).
|
|
Yeah, that was the strategy I was thinking of. I haven't gotten around to proving it for all sequences, though.
Perhaps the more interesting question is what player 1 should pick. I have what seems like a reasonable strategy, but it seems less likely to work in all cases.
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Coin flip game
« Reply #6 on: May 23rd, 2005, 3:50am » |
Quote Modify
|
on May 23rd, 2005, 1:30am, Deedlit wrote:| Perhaps the more interesting question is what player 1 should pick. I have what seems like a reasonable strategy, but it seems less likely to work in all cases. |
|
Do you still refer to the case when player 2 knows player's 1 sequence? If yes, the answer is known, and still the changes of player 2 to win are almost 2:1.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Coin flip game
« Reply #7 on: May 23rd, 2005, 4:29am » |
Quote Modify
|
William once suggested using Martingale's theorem. I never really understood it (and it seems i never did find any good online reference either). However, william did mention that Martingale's theorem can be used to show why one sequence is more likely to occur than the other.
Ofcourse if we are looking for strategies, then the players are best choosing the shortest possible sequence which is of 1 and each with a probability of 0.5 to win 
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Coin flip game
« Reply #8 on: May 23rd, 2005, 8:08am » |
Quote Modify
|
I don't think martingale is a person - the name comes from the gambling strategy of doubling your bet when you lose, until you win your initial bet back. This is called "the martingale", although I don't know how that name came about.
Yes, if you allow aribtrary sequence lengths the game is trivial, so for the "strategic portion" I specified that both sequences had to be a fixed length d. (for the original question you can include all sequence lengths)
Martingales are really fairly intuitive; it's just a sequence of random variables {Xn} in which the expected value of the Xn+1 is precisely Xn. The classic example is letting Xn be the amount of money a gambler has after n plays, when he plays a completely fair game. The key result is, no matter what strategy the gambler employs, the expected amount of money he leaves with is exactly the same as the amount of money he started with. (It follows that for a strict supermartingale, where the game favors the house, your expected net winnings is always negative, unless you don't bet at all.) Note that there are some issues with infinity that have to be dealt with; if you are allowed to play arbitrarily long, with an infinite line of credit, you really do win money with "the martingale"!
While martingales are simple, the martingale proof is somewhat complicated - I can try to explain any questions you might have about it. Once you grok that proof, you can use it to solve the questions in this thread.
|
|
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Coin flip game
« Reply #9 on: May 23rd, 2005, 10:39am » |
Quote Modify
|
Some observations:
=================
- It seems like a good idea is to just choose a sequence that minimizes the expected time till it appears. Those are sequences with no "left-sided overlapping structure" as the sequence is shifted to the right. This is not a real term, I just made it up for lack of better words. I will explain with an example:
HTHTH
HTHTH
HTHTH
HTHTH
HTHTH
We take a length-d sequence, and write repeated copies of the sequence below it, each one shifted one more unit to the right. Then we look at those sequences S which exactly match the original sequence as far as the original sequence extends. Count up the lengths Li of each such matching sequence. Assuming the coin bias is 1/2, the expected time till this sequence shows up is then
2d + sumi 2Li
so in this case we have 25 + 23 + 21, since d=5, and the lengths of the matching shifted sequences are 3 and 1.
Note the expectation is then minimized if the set { Li } is empty, in which case the expected time is just 2d.
=================
- Why it works (martingale method for computing expected time till sequence is hit):
I gave an argument for why this works at reply #19 on http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_eas y;action=display;num=1085949618;start=9#9 ; hopefully it will be easier to understand with the crucial diagram above in mind. I will try again to explain it:
> Gamblers are entering a casino at each time step with one dollar in their pockets, each betting on the exact same sequence with fair odds. Thus a shifted sequence corresponds to a gambler who has entered the casino at a later time.
> Whenever a letter is matched, a gambler doubles his money. When a letter is not matched, a gambler loses all his money and leaves. This corresponds to simply losing 1 dollar, since that's all the gambler came in with.
> When a lucky gambler matches all the letters in the sequence, the casino shuts down. At this shut-down point, the lucky gambler gets 2d dollars.
> Every gambler who entered the casino before the lucky gambler must have lost all their money, since otherwise, the casino would have shut down earlier.
> Also, some gamblers who entered after the lucky gambler will leave with positive earnings, since they matched some beginning parts of the sequence before the casino closed.
> Finally, using martingale theory, the expected amount of money going into the casino must equal the expected money going out, since the odds are fair. (Modulo some details, if we have a stopping time that is finite with probability 1 has finite expectation, the expected return of the stopped martingale is the same as the expected return from the start.) So we know how much money will be leaving the casino -- we just computed that. All money entering the casino came from gamblers prior to the lucky gambler, and each contributed one dollar over a different time step (actually not necessarily different, but amortized over all time, these losses can be thought of happening at different time steps). Hence, the chain of logic is like this:
expected money going into casino = expected number of losing gamblers = expected time till the casino closed = expected amount of money leaving casino
=================
- There can be several such sequences that minimize the expected time of appearance. Then we may want to minimize the variance of the time of appearance, resulting in another optimization problem. However this is a bit of a double edged sword -- if the variation about the mean is symmetric, a large variance could result in an early match if we're lucky, or a very late match if we're unlucky.
=================
- It seems more interesting to me when the coin is biased. Then not every sequence is equally likely. In fact, if the coin is biased toward heads, the most likely length-d sequence is simply a straight of d heads. But this sequence also could have considerably higher expected time of arrival than the rest due to all the overlapping structure. (It's not just sum i = 1 to d 2i due to the bias, but still.) Maybe I'll compute this later ... I guess it still makes sense to minimize the expected time, even if the resulting sequences are not the most likely? Because the likelihood argument only looks at one snippet of length d, whereas the expected time criterion is closer to the game's objective, and repeated coin flipping.
=================
- It's not clear to me that the proposed optimal strategy for player 2 is really optimal, particularly if player 1 chooses a poor sequence.
=================
- What if the players can choose a set of d-length sequences? I haven't thought much about it, but might the asymptotic equipartition property come into play ... ? (if you flip a N coins, then as N tends to infinity, all the probability mass is concentrated amongst sequences whose heads/tails ratio is close to the coin biases. hence if coin bias is 1/10, all probability mass is concentrated amongst sequences where 1/10 of the flips are heads. in other words, the empirical entropy matches the true entropy.)
|
| « Last Edit: May 23rd, 2005, 5:39pm by william wu » |
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Coin flip game
« Reply #10 on: May 23rd, 2005, 12:38pm » |
Quote Modify
|
Thank you, William, for the well thought out post, and for explaining the martingale method.
Quote:| - It seems a good idea is to just choose a sequence that minimizes the expected time till it appears. Those are sequences with no "left-sided overlapping structure" as the sequence is shifted to the right. |
|
It seems to me that minimizing the expected time is not as important as co-opting your opponent's sequence. It seems to really reduce your opponent's probability of winning when you can snag victory with him just one flip away from victory himself. But there are several competing factors, and it's probably not the case that any one factor explains everything.
Quote:| Finally, using martingale theory, the expected amount of money going into the casino must equal the expected money going out, since the odds are fair. (Modulo some details, if we have a stopping time that is finite with probability 1, the expected return of the stopped martingale is the same as the expected return from the start.) |
|
I don't think that's a good characterization. I know it's just an approximation, but many common counterexamples, like the martingale, have a finite stopping time with probability one.
We do know that for a random stopping time N and a fixed number n, E(Xmin (N,n)) = E(X0). So we would like to show that E(XN) - E(Xmin (N,n)) goes to 0 as n goes to infinity. Fortunately, that is the case here. Basically, we use the fact that the probability of the game lasting more than n turns decreases exponentially (for a chosen sequence of length d, we have an upper bound of (1 - 1 / 2d)n/d), while the amount of money is bounded above and below be linear functions (we have between -n and c-n dollars, for some constant c).
Quote:| - There can be several such sequences that minimize the expected time of appearance. Then we may want to minimize the variance of the time of appearance, resulting in another optimization problem. However this is a bit of a double edged sword -- if the variation about the mean is symmetric, a large variance could result in an early match if we're lucky, or a very late match if we're unlucky. |
|
Yeah, I don't really see the advantage of minimizing variance.
Quote:| - It seems more interesting to me when the coin is biased. Then not every sequence is equally likely. In fact, if the coin is biased toward heads, the most likely length-d sequence is simply a straight of d heads. But this sequence also could have considerably higher expected time of arrival than the rest due to all the overlapping structure. (It's not just sum i = 1 to d 2i due to the bias, but still.) |
|
In fact, you can generalize to a possibly infinite set of letters li occuring with probabilities pi, and apply the same martingale argument. For two letters, there are basically two cases - I'll hold my tongue for now.
Quote:| - It's not clear to me that the proposed optimal strategy for player 2 is really optimal, particularly if player 1 chooses a poor sequence. |
|
If player 1 chooses a really poor sequence (HH...H or TT...T) then the strategy is clearly the best possible. But I agree that it's not obvious in general.
Quote:| - What if the players can choose a set of d-length sequences? haven't thought much about it, but might the asymptotic equipartition property come into play ... ? (if you flip a N coins, then as N tends to infinity, all the probability mass is concentrated amongst sequences whose heads/tails ratio is close to the coin biases. hence if coin bias is 1/10, all probability mass is concentrated amongst sequences where 1/10 of the flips are heads. in other words, the empirical entropy matches the true entropy.) |
|
The solution seems to require a rather complicated system of linear equations, but there is probably some asymptotic reasoning that can be brought to bear here. I'll have to think about it.
|
| « Last Edit: May 23rd, 2005, 12:38pm by Deedlit » |
IP Logged |
|
|
|
william wu
wu::riddles Administrator
Gender:
Posts: 1291
|
|
Re: Coin flip game
« Reply #11 on: May 23rd, 2005, 5:36pm » |
Quote Modify
|
on May 23rd, 2005, 12:38pm, Deedlit wrote:I don't think that's a good characterization. I know it's just an approximation, but many common counterexamples, like the martingale, have a finite stopping time with probability one.
|
|
Yes you're totally correct ... I meant to say, when the expectation of the stopping time is finite. Corrected in original post.
Not sure which martingale you are referring to in "like the martingale", but in case any curious readers wish to know, the classic example is flipping fair coins, earning one dollar when you get heads, and losing one dollar when you get tails. You start with 0 dollars. The expected time till you hit +1 is infinite. If we design a stopping time T = min { n : Sn = +1}, where Sn is the running sum of +1/-1 increments, then if we simply stop once we've hit +1, this is a strategy that is guaranteed to give us a gain of 1 dollar, which is more than the 0 dollars we started with. However, the expected time till we get there is infinite. Thus, although it is possible to come out of a fair game with more than you started with without having to invoke clairvoyance, the expected time till the strategy finishes is infinite -- you may have to incur arbitrarily large amounts of debt in the process.
Hence, casinos will place limits on the amount of money you can bet on a game. If you are playing roulette, a surefire winning strategy is to always double your bets on the same number. Eventually that number will be hit, and you'll finish with positive net income. To avoid losing money, the casino may terminate your play prematurely if the bets are getting too large.
|
|
IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Deedlit
Senior Riddler
Posts: 476
|
|
Re: Coin flip game
« Reply #12 on: May 23rd, 2005, 9:12pm » |
Quote Modify
|
"The martingale" is exactly the double or nothing strategy you describe. However, the expected stopping time is finite. (it's two, in fact) So that condition doesn't work either.
|
|
IP Logged |
|
|
|
TenaliRaman
Uberpuzzler
I am no special. I am only passionately curious.
Gender:
Posts: 1001
|
|
Re: Coin flip game
« Reply #13 on: May 27th, 2005, 9:36am » |
Quote Modify
|
on May 23rd, 2005, 8:08am, Deedlit wrote:| While martingales are simple, the martingale proof is somewhat complicated - I can try to explain any questions you might have about it. Once you grok that proof, you can use it to solve the questions in this thread. |
|
Thanks for the generous offer! I, now, after reading yours and william's post do get an idea what a martingale is. I definitely have a lot of questions about martingales and ofcourse i need to grok down its proof as you say. But i think i will ask it in a separate thread after a few weeks (as i have to contend with my final semester exams starting may 30). I just hope you do keep your offer open for atleast 3 weeks .
-- AI
|
|
IP Logged |
Self discovery comes when a man measures himself against an obstacle - Antoine de Saint Exupery
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print