Author 
Topic: Coin flip game (Read 1479 times) 

Deedlit
Senior Riddler
Posts: 476


Coin flip game
« on: May 21^{st}, 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 21^{st}, 2005, 8:33am by Deedlit » 
IP Logged 



rmsgrey
Uberpuzzler
Gender:
Posts: 2873


Re: Coin flip game
« Reply #1 on: May 21^{st}, 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 21^{st}, 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 21^{st}, 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 23^{rd}, 2005, 12:37am » 
Quote Modify

on May 21^{st}, 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 S_{1}, then player’s 2 optimal strategy is to remove the last flip from S_{1} and prefix it by H or T (the two choices are never equally good). on May 21^{st}, 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 “selfoverlapping” if it’s copy may be shifted so that the 2 strings perfectly match on overlapping section. For instance, the sequence HTHTH is selfoverlapping, as is shown by the following shift: HTHTH HTHTH The result proved in 1966 states that no selfoverlapping sequences occur in average sooner than selfoverlapping sequences.


IP Logged 



Deedlit
Senior Riddler
Posts: 476


Re: Coin flip game
« Reply #5 on: May 23^{rd}, 2005, 1:30am » 
Quote Modify

on May 23^{rd}, 2005, 12:37am, Barukh wrote: If player 1 picks a sequence S_{1}, then player’s 2 optimal strategy is to remove the last flip from S_{1} 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 23^{rd}, 2005, 3:50am » 
Quote Modify

on May 23^{rd}, 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 23^{rd}, 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 23^{rd}, 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 {X_{n}} in which the expected value of the X_{n+1} is precisely X_{n}. The classic example is letting X_{n} 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 23^{rd}, 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 "leftsided 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 lengthd 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 L_{i} of each such matching sequence. Assuming the coin bias is 1/2, the expected time till this sequence shows up is then 2^{d} + sum_{i} 2^{Li} so in this case we have 2^{5} + 2^{3} + 2^{1}, since d=5, and the lengths of the matching shifted sequences are 3 and 1. Note the expectation is then minimized if the set { L_{i} } is empty, in which case the expected time is just 2^{d}. =================  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/cgibin/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 shutdown point, the lucky gambler gets 2^{d} 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 lengthd 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} 2^{i} 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 dlength 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 23^{rd}, 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 23^{rd}, 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 "leftsided overlapping structure" as the sequence is shifted to the right. 
 It seems to me that minimizing the expected time is not as important as coopting 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(X_{min (N,n)}) = E(X_{0}). So we would like to show that E(X_{N})  E(X_{min (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 / 2^{d})^{n/d}), while the amount of money is bounded above and below be linear functions (we have between n and cn 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 lengthd 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 l_{i} occuring with probabilities p_{i}, 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 dlength 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 23^{rd}, 2005, 12:38pm by Deedlit » 
IP Logged 



william wu
wu::riddles Administrator
Gender:
Posts: 1291


Re: Coin flip game
« Reply #11 on: May 23^{rd}, 2005, 5:36pm » 
Quote Modify

on May 23^{rd}, 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 : S_{n} = +1}, where S_{n} 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 23^{rd}, 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 27^{th}, 2005, 9:36am » 
Quote Modify

on May 23^{rd}, 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



