A probability puzzle

[tar503]

You give 1 fair coin each to 1 million people. You give the following instructions, "Flip the coin as many times as it takes to flip a heads. Once you flip heads, stop flipping. For every flip of the coin that you make, write either a T or an H corresponding to the result that you got and put it in this bag."

You let everyone flip and write their results until everyone is done (that is, everyone has flipped heads once and stopped). You randomly draw a piece of paper from the bag. What are the odds it has an H on it?

Example flipper: Person 7,422 flips Tails, Tails, Heads, so he would have written 3 pieces of paper, a T, T and an H and put it in the bag.

I think I know the answer to this (and I think I may even be able to draft up a formal proof as to why it's the answer) but I am not 100% sure.

[Jaglavak]

The answer is, you're out $10,000 for all those pennies.

[Sour Grapes]

100%. If the flipper hasn't got a head yet then the coin isn't in the bag. But with a million people throwing coins it's not overly likely that anyone took more than 20 flips.

[Jaglavak]

The odds are almost exactly 50%. It all comes down to the last flipper.

[Mbossa]

I agree with Jag. 50%.

If we assume for each round that exactly half get heads and half get tails:

First round:
500,000 people write H and stop flipping.
500,000 people write T and advance to the next round.
The bag contains 500,000 'H's and 500,000 'T's.

Second round:
250,000 people write H and stop flipping.
250,000 people write T and advance to the next round.
The bag now contains 750,000 'H's and 750,000 'T's.

Third round:
125,000 people write H and stop flipping.
125,000 people write T and advance to the next round.
The bag now contains 875,000 'H's and 875,000 'T's.

Fourth round:
62,500 people write H and stop flipping.
62,500 people write T and advance to the next round.
The bag now contains 937,500 'H's and 937,500 'T's.

...you get the idea.

In reality, it's extremely unlikely that exactly half will get heads and half will get tails in each round (especially in the earlier rounds). But in the absence of any additional information about how the rounds play out, 50%.

[Mbossa]

I've seen a nearly identical problem in a puzzle book, formulated this way:

A sexist totalitarian military dictatorship decides that it needs to reduce its population growth, but it also wants to increase the number of boys being born compared to girls so that the boys can join its army. So they introduce a law that says that couples can keep having children as long as they're boys, but as soon as they have a girl they have to stop having children. Assuming that the chance of each sex being born is 50%, does the government succeed in its goals?

The answer it gave in the back of the book (without much of an explanation, unfortunately) was that they do succeed in reducing its population growth, but the boy:girl ratio remains unchanged.

[tar503]

I too think it's 50%, and I think the proof has to do with the series (1/2) + (1/4) + (1/8) + ... but I'm not entirely sure.

[Sour Grapes]

Again: The question actually was

You randomly draw a piece of paper from the bag. What are the odds it has an H on it?

By the conditions given, a piece of paper is in the bag if and only if it has an H on it. So the odds are 100%.

To a rounding error, the number of Hs and Ts will be identical: You have recorded n coin flips and each has a 50-50 chance of being a head or a tail. What you did after flipping the coin doesn't affect the odds.

ETA: If you mean "only an H" then it's a 50% chance.

[Sour Grapes]

Originally Posted by Mbossa

I've seen a nearly identical problem in a puzzle book, formulated this way:

A sexist totalitarian military dictatorship decides that it needs to reduce its population growth, but it also wants to increase the number of boys being born compared to girls so that the boys can join its army. So they introduce a law that says that couples can keep having children as long as they're boys, but as soon as they have a girl they have to stop having children. Assuming that the chance of each sex being born is 50%, does the government succeed in its goals?

The answer it gave in the back of the book (without much of an explanation, unfortunately) was that they do succeed in reducing its population growth, but the boy:girl ratio remains unchanged.

Same story. If the birth ratio is 50:50 (which isn't spot on, but will do for now) then it doesn't matter one whit what you do to the mother after the birth. The birth rate itself will drop by an insignificant amount, simply because in order to remain as it was before it would theoretically require a tiny fraction of women to have a larger number of boys than the human breeding cycle allows.

[Mbossa]

Originally Posted by Sour Grapes

Again: The question actually was

By the conditions given, a piece of paper is in the bag if and only if it has an H on it. So the odds are 100%.

To a rounding error, the number of Hs and Ts will be identical: You have recorded n coin flips and each has a 50-50 chance of being a head or a tail. What you did after flipping the coin doesn't affect the odds.

ETA: If you mean "only an H" then it's a 50% chance.

The way I interpreted it (and I'm quite certain the way drewtwo99 intended it to be interpreted), each piece of paper would only have one letter on it. Each flip would result in a new piece of paper going into the bag.

[Sour Grapes]

Originally Posted by Mbossa

The way I interpreted it (and I'm quite certain the way drewtwo99 intended it to be interpreted), each piece of paper would only have one letter on it. Each flip would result in a new piece of paper going into the bag.

Ah yes, I read the first part and thought the person would write down their results when they were done flipping. I completely skimmed over the example later on in the OP. Well then, 50% - and why would you ever think it would be different?

[Wolf Larsen]

I tried to convince myself it wasn't 50/50, but other than the usual jitter in coin flipping outcomes I can't find an argument that it isn't.

[Sour Grapes]

Originally Posted by Wolf Larsen

I tried to convince myself it wasn't 50/50, but other than the usual jitter in coin flipping outcomes I can't find an argument that it isn't.

Indeed not. What causes a piece of paper to be put in the bag? The flip of a fair coin. What are the possible outcomes of that flip? Head or tail with equal probability. What must the distribution of H and T be therefore?

The phrasing of the puzzle, like the old three-men-buy-a-TV, where-did-the-dollar-go puzzle, may distract, but the math doesn't change.

[Giraffe]

Originally Posted by Sour Grapes

Indeed not. What causes a piece of paper to be put in the bag? The flip of a fair coin. What are the possible outcomes of that flip? Head or tail with equal probability. What must the distribution of H and T be therefore?

Exactly. You have a bunch of people flipping coins and writing down the results. The fact that the number of flippers changes over time based on past flips feels like it should matter, but it doesn't. Because coin flips are uncorrelated.

[Pere]

Originally Posted by Sour Grapes

Same story. If the birth ratio is 50:50 (which isn't spot on, but will do for now) then it doesn't matter one whit what you do to the mother after the birth. The birth rate itself will drop by an insignificant amount, simply because in order to remain as it was before it would theoretically require a tiny fraction of women to have a larger number of boys than the human breeding cycle allows.

Of course the stipulated assumption indicates that this is a pure-math problem, not an actual one of biology and social engineering.

Otherwise it would be pretty relevant that overall sex ratio at birth is definitely not 50:50. Furthermore, the odds for any particular birth are skewed by the mother's previous gestational history (boys become less likely in successive births), by environmental factors (malnutrition and contaminants make boys less likely), and by father's age (older fathers make boys less likely). There may also be interactive biochemical factors for particular couples.

So the government should work on any hunger and pollution problems it may have, and it should encourage generally young marriage, and of still-fertile women to younger men.

A real-world dictatorship with this goal would probably just go straight to gender-selective abortion/infanticide.

[Rat Diva]

That's why those word problems always have a line to the effect of "assume the m/f birth ratio is 1:1 and there are no other factors that would favor one or the other." Because once you bring in environmental factors, the health/age of the parents, how to account for twins/ other multiples, stillbirths, miscarriages, intersex children, and so on so on so forth, you're filling up 48 blue books just to answer one question and no math professor I ever met has time for that shit.

[tar503]

Probability Puzzle Part 2:

Same setup as before, with a twist. Each person is given $1000 dollars and told that for every time they flip tails, they lose $100 until they flip heads, and keep whatever is left. Half the population is honest, and will always write down the correct H or T value that they flip. Half the population will lie and say they've flipped an H if they flip a T (and subsequently stop flipping). If you get to $0 you still continue to flip until you get heads (only the honest half will end up doing this of course).

Now what are the odds of pulling an H out of the bag after everyone is done flipping?

Bonus question: What is the average amount of money a person takes away after all is said and done?

[Rat Diva]

The 500000 liars might as well not bother with flipping, since they all will write H on their paper, stick it in the bag, and keep their whole $1000. The 500000 honest people will follow the same pattern as Mbossa's post #5, with a 50/50 split each round.

My WAG is that it will work out to 66.6% chance of pulling an H out of the bag when all is said and done. I'm thinking of it like the Monty Haul problem.

Round one:
500000 liars + 250000 honest=750000 heads (in the bag)
250000 tails (in the bag)
1000000 papers (in the bag)
odds of pulling an H=75%

round two:
750000+125000=875000 heads
250000+125000=375000 tails
1250000 papers
odds of pulling an H=70%

round three:
875000+62500=937500 heads
375000+62500=437500 tails
1375000 papers
odds of H=68.2%

[lots of math later]

at the end I get:
1000000 heads
497925 tails
1497925 pieces of paper
for a 66.76 chance of pulling a head

Q.E. D.

[Rat Diva]

And unless I'm completely screwing something up (enteriely possible) the average amount of money is $995.

[tar503]

$995 seems shockingly high to me. But I can't do the math to figure it out if you're wrong. You probably are right on the money! (pun fully intended)

[Rat Diva]

It surprised me too, that it was such a high amount.

What I did was take the number of people flipping heads on each round x the prize money for that round, total everything for all the rounds and divide by a million to figure out the money per person. Excel is my friend.

The reason it skews so high is because there are 750000 people in the first round getting the full $1000, followed by only 125000 getting $990 in the second. The number of people getting lower amounts drops exponentially so it doesn't figure into the average all that much.

[Rat Diva]

except, genius that I am, I decreased the prize money by $10 per round instead of $100. Reading comprehension is NOT my friend.

ETA I still had the spreadsheet open so I was able to just plug the correct dollar amounts in. Which brings us to $950.05 average. Arrgh.

[Jaglavak]

Please present your answer to the class in closed form.

[happyheathen]

This is the old "I this absolutely perfectly balanced coin (exactly 50% heads, 50% tails).

I start flipping it and I get Heads 49 times in a row! What is the probability of the coin coming up heads on the 50th flip?"

50% See first sentence.

The question is not "what is the probability of a coin coming up heads on 50 consecutive flips - it is simply the probability of a single toss.

And, to be picky - all of the slips will have a H - it may be the 4th letter, but, if all 1 million understand the instructions and flip until a heads, all will have an H as the last letter. There is a 50/50 chance it will be first.

Coins DO NOT HAVE MEMORIES, of knowledge of the other 999,999 coins. Perfectly balanced coins have 50/50, come Hell or high water, on each flip.

Why is that so damn difficult to remember?

[Pere]

Originally Posted by happyheathen

And, to be picky - all of the slips will have a H - it may be the 4th letter, but, if all 1 million understand the instructions and flip until a heads, all will have an H as the last letter.

If a million people read a probability puzzle, how many will understand the instructions?


(Each slip has only one letter.)

[happyheathen]

I never was any good with calculus, so I'm not going to take a guess - but I"ll guess your chance will be one of those "approaching x%".
Probably something less that 2/3 - some poor fool is going to get TTTH and really throw off pretty numbers.

[tar503]

Originally Posted by Pere

If a million people read a probability puzzle, how many will understand the instructions?


(Each slip has only one letter.)

Haha! So true. Then again, trying this experiment out in real life... a huge percentage of people are going to write something other than T or H on the paper. "heads" "tales" "tails" "Hedz" "lizard people" and so forth.