I was asking my friends a riddle about identifying hats. Each person has to correctly identify the colour of their own hat that was put on their head randomlly. There is no defined number of either colour. So they could be all white or all black or any combination in between.

They gave an answer that gets 50% right but I fired back that getting 50% right is what you would expect, on average, for straight guesses. They claimed that that would depend on the colours of the hats that are on the people's heads. In other words, if everyone was wearing black then the 50% rule not apply. This just doesn't "feel" right to me.

Who is correct?


This is the puzzle I asked. You have 100 people standing one behind the other such that the last person can see all the people in front of him/her and so on. So the last one see 99 and the next sees 98 etc. They each have a hat put on their head which is black or white. They have no idea how many of each exist.

Assuming they plan on a strategy in advance, how many can get their hat right. They said that the best way is for the back person to say the colour of the hat on person 99. Person 99 can say his colour. Then 98 will say the colour of the one in front etc. This was I am guaranteed at least 50 right and maybe more if two consecutive people have the same colour. My claim was that 50% guaranteed is the same as random (ignoring the extra lucky one if there are consecutive hats). Their counter-claim was that the 50% random guess would only be right if their were exactly 50 of each colour.

  • 5
    $\begingroup$ There are many variants of the hat problem...which one are you thinking of? As a general point, there is certainly a difference between a method that is guaranteed to generate $50\%$ correct answers and a method that on average gives $50\%$. $\endgroup$ – lulu Nov 5 '18 at 16:31
  • $\begingroup$ " I fired back that getting 50% right is what you would expect, on average, for straight guesses." What other option is there? In this problem you seem to have people looking at hats and then guessing blind. i.e. straight guess. That is 50-50. $\endgroup$ – fleablood Nov 5 '18 at 16:34
  • $\begingroup$ "In other words, if everyone was wearing black then the 50% rule not apply. " If everyone is wearing black hats there are two options. Either everyone including yourself is wearing black hats of you are the only person wearing a white hate. We are told that the hats were randomly given. So either of those outcomes are equally likely. $\endgroup$ – fleablood Nov 5 '18 at 16:38
  • $\begingroup$ But we need more details. We there a set N number of hats that were in a box to begin with? Where did this box come from? How were its color distribution determined? Was each hat magically produced by flipping a coin as it was put on a head? Did the people in the hats know where the hats came from? If I saw 99 black hats I'd figure that'd be no accident. I'd figure either we were delivered 100 black hats or 99 black hats with 1 hat to mess with us. If it were 99 I'd figure the prob I get the white hat is 1/100 so it's probably all black. $\endgroup$ – fleablood Nov 5 '18 at 16:45
  • 1
    $\begingroup$ Well, I am getting the sense that there is missing information. But it does seem safe to say that a truly random set of $50-50$ bets should follow the law of large numbers. $\endgroup$ – lulu Nov 5 '18 at 17:06

Skip forward to below the "=====" for the answer that you're probably looking for. Read the first part to find out why I put it after the "=====".

To make sense of this, you need to think about probability spaces. And to do that right, you need more information about the meaning of the words in your question.

Case 1: There's a distribution $d$ from which the hats for each person are drawn independently randomly. The players guess black/white uniformly randomly. In this case, the expected number of correct guesses is 50 out of 100.

Case 2: There's a distribution as before, again with independent drawing of hat colors, but the players get to look at others' hats before guessing; they then guess black with a probability proportional to the number of black hats they see (out of the total 99 hats they see). (Roughly: if 95 others have black hats, and 4 have white hats, you guess "black" 95 out of 99 times (perhaps by rolling a die to generate your guess). The expected number of correct guesses in this case is always at least 50, but can be far greater. If the distribution $d$ is highly skewed, this strategy wins big. Note that the players are still "guessing randomly" here ... just not uniformly randomly.

Case 3: The hat-placer is an adversary, and has thought about strategies you might employ. The hat-placer carefully chooses a number $k$ of black hats and $100-k$ white hats, and then distributes these randomly among the players by picking uniformly randomly a permutation of the numbers 1...100. (Note that this still meets the condition "that was put on their head randomly"). The players guess uniformly randomly from "black" or "white", without observing the others' hats. The expected number of correct guesses is again 50.

Case 4: Same adversarial setup as in case 3, but the players use the 'bayesian' approach of case 2. In this case, the adversary will presumably optimize, which will turn out to set $k = 50$, and again the expected number of correct guesses is 50.


Anyhow, case 2 makes the point that saying what distribution is being used in each step of randomness in the problem is critical to assessing expected values. Just saying "randomly" doesn't guarantee uniform randomness. And "straight guesses" doesn't actually mean much of anything to me, although I'm guessing that to you it means "uniformly randomly chosen from 'black' and 'white'."

Let me ramble on a little further still, and formulate the problem a little differently.

You have a fixed but unknown list of 100 bits, $b_1, \ldots, b_{100}$, each either a $0$ or a $1$.

You generate another list of 100 bits, $c_i$, $i = 1, \ldots, 100$, chosen independently identically distributed from the uniform distribution on the set $\{0, 1\}$.

You ask "What is the expected number of $i$ for which $b_i = c_i$?"

The answer in this case is $50$, and does not depend on the initial bit sequence $b$. The proof is straightforward: the probability space consists of all possible $c$-sequences; there are $2^{100}$ of these, each equally probably.

If we look at the $i$th digit of each of these sequences, in half of them $c_i$ is zero; in the other half, $c_i = 1$. Hence the probability that $c_i$ equals $b_i$ is exactly $1/2$, and the expected value of the event $c_i = b_i$ is $1/2$. By linearity of expectation, the expected number of matching bits is the sum of the expected number of matching first-bits, matching second-bits, and so so, hence is $100$ times $1/2$, or $50$.

| cite | improve this answer | |
  • $\begingroup$ I honestly think this misses the point. It's the people that are guessing their own hat colour (and it seems unreasonable to suppose that they are not guessing either black of white with probability 1/2). The distribution the hats are placed in is not relevant as each person is guessing independently; that's the "straight guessing" strategy. $\endgroup$ – T_M Jul 6 at 7:46
  • $\begingroup$ 1. That argument is exactly the one I made in the second part, after the "===="; i the first part, I was trying to use this as an opportunity to teach OP how careful one has to be using words describing randomness. That may have been a misguided goal, and I may have failed, but part 2 does answer the question as asked, with reasonable assumptions. The "edit" in which the questioner discloses that it's the "people in a line seeing in front of them" puzzle was added after I wrote my answer; it, in fact, demonstrates that a conditionally-random approach, while still being random, can do well. $\endgroup$ – John Hughes Jul 6 at 11:54
  • $\begingroup$ @Moko19's answer shows just how very good a conditionally-random approach can be [although in that answer, there's exactly no randomness, i.e., among all conditionally random approaches, it's one of the "least random." :) ] $\endgroup$ – John Hughes Jul 6 at 11:56

If I understand the riddle correctly, for a set of N people, there is an algorithm by which all but one person are guaranteed to get the correct answer, assuming all the players are perfect mathematicians and can arrange a strategy before being assigned hats.

The person in back counts the number of black hats that he can see. If he sees an odd number, he says white and otherwise says black. He has no information whatsoever about his own hat, and has a 50-50 chance of what he said being the correct color hat for himself.

The other N-1 players have a similar game, except that they know whether the total number of the N-1 players with black hats is even or odd. As such, by counting the number of black hats that the others of the N-1 players have (whether by seeing the hats of the people in front of them or from the answers of the people behind them) and determining it as either even or odd, they can deduce whether they themselves have black or white hats.

Similarly, if there there M colors $(C_0,C_1,C_2,C_3,...,C_{m-1})$, they total the value of the hats of players in front of them by adding 0 for $C_0$, 1 for $C_1$, etc, and taking the remainder after dividing the total by M. As such, in a group of N players with M hat colors, the minimum number of players to answer correctly will be N-1, the maximum will be N, and the mathematical expectation of the number of correct answers is $N-1+\frac{1}{M}$

| cite | improve this answer | |

You are correct, 50% is what you would expect, on average, for straight guesses.

Your friend is missing the point of saying "expect, on average" if they claim that what happens "on average" won't happen some of the time.

The 50% rule does apply even if everyone is wearing black. It's the people that are guessing, not whoever put the hats on their heads. Each person is still guessing their own hat with a 50/50 chance of being correct, no matter what colour their hat is.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.