Tossing a coin 3 times: Is it a fair game?

[humanino]

Hi,

It is often frustrating when tossing a coin if there is just one tossing and it's over. Let's say, Nicolas and George toss a coin and are after two given configurations, each his own. Nicolas likes the configuration Head-Tail-Tail. George chooses Head-Tail-Head. Whenever they argue, they play the game : they toss a coin, and the first to get his configuration wins.

Is this a fair game ?

 

[glueball8]

why not?

 

[K.J.Healey]

So long as it always starts from zero, I don't see why it would be any different than a single flip. Before either can possibly win, a Head-Tail pattern must occur. Then from that point, its a 50%.
Unless the wording is wrong somehow...

 

[humanino]

Unless the wording is wrong somehow...

I believe the wording is right. It did look pretty trivial to me too. Maybe you'd like to try it for yourself, I mean simulation on a computer, before making up you mind definitely.

This puzzle is really one of the best I have ever seen. It's simple, and nobody gets it right.

 

[humanino]

Unless the wording is wrong somehow...

Ah, you're right, I did not word it right... too bad

 

[lisab]

Hmmm, not sure if this is right...and it's hard to say with words.

Spoiler

George, with the HTH configuration.

It first appears that the winner is simply decided by the last toss, since they both chose HT as the first two flips in their configurations. But since the first toss of the each configuration is an H, that H could be George's winning flip, since his last flip is H.

Like I said, it's hard to say with words. English is my second language...an I don't have a first one .

 

[lisab]

OK, so nevermind the last post...it didn't seem quite right anyway.

So what is the correct wording?

 

[humanino]

So what is the correct wording?

• I am not sure how to word it then. It would seem unnatural. They win half of the time, but when one wins he wins faster on average. I could say, every new toss comes with a new coin from your pocket, and the looser (to compensate for his loss) keeps all the coins in the end
• If I do that, you solved it already

Congratulations lisab. You can solve even unknown problems. That is, you spotted the difference between the two configurations : one of them overlap itself, whereas the other does not. Since on a large number of tosses, they appear as often one as another, the average distance between two HTT is (8) less than between two HTH (10).

 

[maze]

How about they just keep flipping until their pattern shows up 3 times (or something of that nature).

 

[chroot]

Any string of flips of length three (HHH, TTT, HTH, THT, THH, HTT, TTH, HHT) is equally probable, so the game is certainly fair. It just takes more time to play.

- Warren

 

[maze]

Right, but if you wanted 3 repititions of hth, then you could win in 7 flips with hththth, whereas its going to take 9 flips for htt (htthtthtt).

 

[chroot]

Right, but if you wanted 3 repititions of hth, then you could win in 7 flips with hththth, whereas its going to take 9 flips for htt (htthtthtt).

The original post makes no mention of trying to obtain the desired pattern more than once; it says the first person to obtain their pattern wins.

- Warren

 

[humanino]

The original post makes no mention of trying to obtain the desired pattern more than once; it says the first person to obtain their pattern wins.

The original post was wrongly worded. The problem does not make sense as such.

Contrary to intuition (at least mine), the average number of tosses until HTH is 10, whereas the average number of tosses until HTT is 8. Still, HTH wins as often as HTT. The distributions of tosses until the configuration is reached are not the same.

 

[dubsed]

I did what you recomended and simulated this (in excel). Over 10,000 trials, both win evenly and both win in an average of 5 tosses.

 

[humanino]

both win evenly

That's right

both win in an average of 5 tosses.

I believe that's wrong. I do not use microsoft products, so I can not help you with your macro, sorry. I have a python script, and a couple of C programs that you would need to compile.

 

[dubsed]

Actually I did not use a macro I just used the options available in the sheet I just set up a series of tosses extracted the critical info from the seires, copied the series and info 100 times to the right (100 trials), and then copied that 100 times down (10,000) trials. At the very end I took totals and averages, averages then I can recalculate the sheet just by hitting F9. I tried to put a standard deviation to it but i don't think that is the correct way to do it. however averages are averages and pretty hard to screw up. I don't know how you wrote your program, if you were calculating odds or just running a random trials. random trials the result is prety clear and repeatable

 

[humanino]

Just to make it clear : I have the number 8 and 10 from a researcher in statistics applied to genetics at Oxford. They are what made me interested in this in the first place. I found them by myself by writing simluation programs, but I do not believe they are questionable.

 

[dubsed]

Here is 1/10 of the data I used. Unfortunately due to the brute force nature of the solution it was too large to keep in excel format and also in its entirety.

Description
Odd Columns - Tosses generated with =int(rnd()*2)
Even Columns - winner of series

Third to last row shows winner in odd colums and the toss he won on in the even column
The second to last row shows the toss that he won on if HTH won
The last row shows the toss he won on if HTT won

On the far right the last two rows show the following table

HTH, qty won, average toss won on
HTT, qty won, average toss won on

I know this isn't the easiest format to work with but you can import it into most spreadsheet software. If anyone can point out my error I would like to know my mistake so I don't repeat it in the future.

 

[Howers]

Hmmm, not sure if this is right...and it's hard to say with words.

Spoiler

George, with the HTH configuration.

It first appears that the winner is simply decided by the last toss, since they both chose HT as the first two flips in their configurations. But since the first toss of the each configuration is an H, that H could be George's winning flip, since his last flip is H.

Like I said, it's hard to say with words. English is my second language...an I don't have a first one .

Huh?

 

[russ_watters]

Right, but if you wanted 3 repititions of hth, then you could win in 7 flips with hththth, whereas its going to take 9 flips for htt (htthtthtt).

That's only 2 repetitions of the pattern if you play it as a game. If the original intent was to allow overlapping patterns to count as multiple wins, then it isn't a fair game, but then no real game would ever work that way anyway. If it did, the best patterns to pick would be HHH and TTT, since any time you get 4 in a row, it would count as 2 "wins" and any time you get 5 in a row, it would count as 3.

 

[Borek]

It has nothing to do with efficiency, it just works and should be pretty easy to check whether it does what it should do.

#include "stdlib.h"
#include "stdio.h"

#define HEAD 1
#define TAIL 0

int toss1, toss2, toss3;
int Nicolas, Henry;

int nowinner()
{
	if (toss1 == HEAD && toss2 == TAIL && toss3 == TAIL)
	{
		Nicolas++;
		return 0;
	}
	if (toss1 == HEAD && toss2 == TAIL && toss3 == HEAD)
	{
		Henry++;
		return 0;
	}
	return 1;
}

int main(int argc, char* argv[])
{
	Nicolas = Henry = 0;

	while (1)
	{
		toss1 = rand() % 2;
		toss2 = rand() % 2;
		toss3 = rand() % 2;

		while(nowinner())
		{
			toss1 = toss2;
			toss2 = toss3;
			toss3 = rand() % 2;
		}

		printf("Nicolas/Henry = %i/%i = %.6f\n",Nicolas,Henry,float(Nicolas)/Henry);
	}

	return 0;
}

Output (after some time):

Nicolas/Henry = 764756/766032 = 0.998334
Nicolas/Henry = 764757/766032 = 0.998336
Nicolas/Henry = 764758/766032 = 0.998337
Nicolas/Henry = 764758/766033 = 0.998336
Nicolas/Henry = 764759/766033 = 0.998337
Nicolas/Henry = 764759/766034 = 0.998336
Nicolas/Henry = 764760/766034 = 0.998337
Nicolas/Henry = 764761/766034 = 0.998338
Nicolas/Henry = 764762/766034 = 0.998339
Nicolas/Henry = 764763/766034 = 0.998341
Nicolas/Henry = 764764/766034 = 0.998342
Nicolas/Henry = 764765/766034 = 0.998343

So the ratio is quite close to 1, I suspect it is skewed by the random numbers not being random.

 

[Borek]

Previous one was under Windows, this is Linux. Still for some reason not exactly 1.

Nicolas/Henry = 244450/242889 = 1.006427
Nicolas/Henry = 244451/242889 = 1.006431
Nicolas/Henry = 244452/242889 = 1.006435
Nicolas/Henry = 244453/242889 = 1.006439
Nicolas/Henry = 244453/242890 = 1.006435
Nicolas/Henry = 244454/242890 = 1.006439
Nicolas/Henry = 244455/242890 = 1.006443
Nicolas/Henry = 244456/242890 = 1.006447
Nicolas/Henry = 244456/242891 = 1.006443
Nicolas/Henry = 244456/242892 = 1.006439

 

[D H]

Borek, it is usually a very bad idea to use the low-order bits of rand(). You might well have just showed one example why.

An alternate explanation is that 0.998 is 1.000 for 1.5 million trials. I'd work out the variance, but it's Saturday afternoon and I'd much prefer to kick back and have a beer than work out the variance in a sequence of 0/1 random variables.

 

[Borek]

Borek, it is usually a very bad idea to use the low-order bits of rand(). You might well have just showed one example why.

Most likely that's the reason, I have tried for 0x100 and it gives better results (like 1.000). Still, it was just a quick and dirty approach to find fast answer. My first idea was to try all possible permutations of - say - 20 tosses, looking for the winner, but I had just about 15 minutes at the time and no further concept how to do that.

Right now it occurred to me that that's very simple - just take every integer up to 2ⁿ, and shift it right till (i & 0b101 == 0b101 || i & 0b001 == 0b001). Some will end in the draw, but that will probably not change the result substantially.

 

[Redbelly98]

I think the problem was wrongly stated to begin with. I remember seeing one similar, some years back, and the explanation for why the probability was not 50/50 made sense at the time.

humanino, are you sure that the configurations you gave (hth & htt) are the correct ones for this problem?

edit:
I'll propose a new problem, which is: come up with 2 configuration that do not have 50/50 odds.

edit #2:
What are people's thoughts about HTT vs. TTT ?

 

[D H]

Most likely that's the reason, I have tried for 0x100 and it gives better results (like 1.000).

Just luck. You are measuring the mean experimentally. The quality of the answer increases with the square root of the population size. With 225 trials, your answer is good to one significant digit. For two significant digits it takes 100 times that, and for three significant digits, you have to tack on another two zeros: 2.25 million trials just to reliably get the ratio to 0.999.

 

[humanino]

I had been writing my code under ROOT environment (probably familiar to particle/nuclear physicists). Anyway, I took Borek's code, modified it a little bit. I think now you can look for yourself : as I said, the probability of winning is 50/50. What changes is how long it takes to win on average. Please use this code to check the results if you please

#include "stdlib.h"
#include "stdio.h"

#define HEAD 1
#define TAIL 0

int toss1, toss2, toss3;
int Nicolas, Henry, stop;

int nowinner(int i)
{
 if (Nicolas==0 && toss1 == HEAD && toss2 == TAIL && toss3 == TAIL)
 {
  Nicolas+=i;
  stop++; 
  return 0;
 }
 if (Henry==0 && toss1 == HEAD && toss2 == TAIL && toss3 == HEAD)
 {
  Henry+=i;
  stop++; 
  return 0;
 }
 return 1;
}

int main(int argc, char* argv[]) 
{
 int LNicolas, LHenry; 
 LNicolas = LHenry = 0;
 int NNicolas, NHenry; 
 NNicolas = NHenry = 0;
 int Ngames=10000000;
 for(int game=0;game<Ngames;game++)
 {
  stop=0; 
  Nicolas = Henry = 0;
  toss1 = rand() % 2;
  toss2 = rand() % 2;
  toss3 = rand() % 2;
  if(game%(Ngames/10)==0)printf("game=%d %d%d%d",game,toss1,toss2,toss3);
  for(int i=3;i<100&&stop<2;i++)
  {
  {
   nowinner(i);
   toss1 = toss2;
   toss2 = toss3;
   toss3 = rand() % 2;
   if(game%(Ngames/10)==0)printf("%d",toss3);
  }
  if(Nicolas<Henry){NNicolas++;}
  else{NHenry++;}
  if(game%(Ngames/10)==0)printf("\n%d %d\n",Nicolas,Henry);
  LNicolas+=Nicolas;
  LHenry+=Henry;
 }
 printf("Probabilities to win : Nicolas=%2.6f Henry=%2.6f\n",NNicolas*1.0/(1.0*Ngames),NHenry*1.0/(1.0*Ngames));
 printf("Number of tosses to victory : Nicolas=%2.6f/ Henry=%2.6f\n",LNicolas*1.0/(1.0*Ngames),LHenry*1.0/(1.0*Ngames));
 return 0;
}

Here are the results I just obtained :

game=0 101111001
8 3
game=1000000 0001011101101111000
18 6
game=2000000 101000
5 3
game=3000000 1101001
6 4
game=4000000 11101000
7 5
game=5000000 101000
5 3
game=6000000 10110101000
10 3
game=7000000 00010000011000100111000110000011000000111011
6 43
game=8000000 1000010011010
3 12
game=9000000 0010111000
9 5
Probabilities to win : Nicolas=0.500367 Henry=0.499633
Number of tosses to victory : Nicolas=7.993227/ Henry=10.001438

edit
Just saw that there is one additional toss at the and of each series... does not change much the results, it's just confusing.

 

[Borek]

Right now it occurred to me that that's very simple - just take every integer up to 2ⁿ, and shift it right till (i & 0b101 == 0b101 || i & 0b001 == 0b001). Some will end in the draw, but that will probably not change the result substantially.

It wasn't that simple, but the results are identical. Fair game. Out of 2²⁰ possible sequences 382 don't have a winner (yet), both Henry and Nicolas won 524097 times.

Edit: I have missed the moment humanino posted his code. I have not checked number of tosses in my new code, but it could be implemented.

 

[Borek]

humanino: sorry to say that, but your code is completely unreadable to me, and it doesn't compile.

Edit: geez... FUBAR... and for sure it is wrong. At least in one place:

LNicolas*1.0/(1.0*Ngames)

is not an average length of the sequence needed by Nicolas to win. If anything, that'll be LNicolas/NNicolas.

My simulations show that it is 5/5 - both lenghts identical.

#include "stdlib.h"
#include "stdio.h"

#define HEAD 1
#define TAIL 0

int toss1, toss2, toss3;
int Nicolas, Henry;
int LNicolas, LHenry; 

int nowinner(int Tosses)
{
	if (toss1 == HEAD && toss2 == TAIL && toss3 == TAIL)
	{
		Nicolas++;
		LNicolas += Tosses;
		return 0;
	}
	if (toss1 == HEAD && toss2 == TAIL && toss3 == HEAD)
	{
		Henry++;
		LHenry += Tosses;
		return 0;
	}
	return 1;
}

int main(int argc, char* argv[]) 
{
	Nicolas = Henry = LNicolas = LHenry = 0;
	int Ngames=100000, Tosses;

	for(int game=0;game<Ngames;game++)
	{
		toss1 = rand() % 2;
		toss2 = rand() % 2;
		toss3 = rand() % 2;
		Tosses = 3;

		while(nowinner(Tosses++))
		{
			toss1 = toss2;
			toss2 = toss3;
			toss3 = rand() % 2;
		}
	}
	printf("Probabilities to win : Nicolas=%2.6f Henry=%2.6f\n",float(Nicolas)/Ngames,float(Henry)/Ngames);
	printf("Number of tosses to victory : Nicolas=%2.6f/ Henry=%2.6f\n",float(LNicolas)/Nicolas,float(LHenry)/Henry);
	return 0;
}

 

[humanino]

humanino: sorry to say that, but your code is completely unreadable to me, and it doesn't compile.

for(int game=0;game<Ngames;game++)

is a loop over Ngames games : for each game, you toss until you have found both configurations. "stop" counts how many configurations have been found for each game. It is increased in "nowinner(int i)" : i counts the toss number. For each game, you toss in the loop

for(int i=3;i<100&&stop<2;i++)

that is to say, at most 100 times (this could be removed). Notice that with have already tossed 3 times before the beginning of the loop, hence begins at i=3. At the beginning of the tossing loop, "Nicolas = Henry = 0;" are initialized to 0, and they count how many tosses are necessary to reach a given configuration. They are filled in "nowinner(int i)"

Nicolas+=i;

only if the configuration was not found yet for this game

if(Nicolas==0 &&...

"LNicolas = LHenry = 0;" initalized to 0 before all games, count the total number of tosses for all games, are incremented after all tosses for each game

 LNicolas+=Nicolas;
  LHenry+=Henry;

so the average number of tosses at the end of all games is

 printf("Number of tosses to victory : Nicolas=%2.6f/ Henry=%2.6f\n",LNicolas*1.0/(1.0*Ngames),LHenry*1.0/(1.0*Ngames));

I don't know why it does not compile. It is not strictly c, it has some c++ I guess. It should not be difficult to debug.

Anyway, if you don't like my code, you can count the number of tosses in yours and tell us how many you find. I seriously think you should find 8 and 10.

Here is a python macro

import random
import sys

def giveRand():
        return int(round(random.random()))
        
a = []

for i in range(0, 3):
        a.append(giveRand())
        
tries = 3
average = []

for i in range(0, 100000):
        while((a[0] != int(sys.argv[1])) | (a[1] != int(sys.argv[2])) | (a[2] != int(sys.argv[3]))):
                a.pop(0)
                a.append(giveRand())
                tries = tries + 1
         
         
        average.append(tries)
        tries = 3
        a = []  
        for k in range(0, 3):
                a.append(giveRand())
        

        
        
result = 0
for i in range(0, 100000):
        result = result + average[i]
        
result = result/100000.0

print "average number of tosses = " + str(result)

Just call is with

linux:/me[N]> python htrand.py 1 0 0
average number of tosses = 8.01837
linux:/me[N+1]> python htrand.py 1 0 1
average number of tosses = 9.9947