Dr House’s rule

Recently a friend of mine posed me the following puzzle:

At first glance, it seems absolutely impossible to improve (or indeed change) the pair’s chance of success - after all, Alice has zero information about Bob’s dice rolls and vice versa. Indeed, it is certainly true that regardless of strategy, any guess Alice makes has probability of being correct precisely $\frac{1}{6}$. However, it turns out that with the right strategy, together they can do much better than $\frac{1}{36}$. How can this be?

Meanwhile on Dr House

The team has just finished scanning the patient’s ovaries, at House’s orders. As House expected, they’ve found a large mass.

Wilson: Solid non-cystic mass on the left ovary. 5 by 3 centimetres, central necrosis. The only question is whether she dies in two months or three.

Foreman: Oh God.

Wilson: You were right, there’s nothing we can do for her here. Might as well put her back on the street.

(Foreman had expressed doubts about the authenticity of the patient’s symptoms, since he dislikes homeless people.)

House: Unless it’s not cancer.

Chase: You’ve got to be joking.

House: Well, hard not to. Nothing funnier than cancer. But what if it’s a tuberculoma? She’s been living out on the streets, breathing all kinds of crap 24/7 - odds are she’s got TB. Why not a nice benign growth to go with it?

Wilson: A solid mass on her ovary. Ovarian cancer is way more likely.

House: You’re right, it’s not even close. Start her on INH, rifampin and streptomycin.

Cameron: But that’s the treatment for a tuberculoma.

House: And what’s the treatment for advanced ovarian cancer?

Foreman: (ominously) Pine box.

House’s reasoning is flawless, as usual. Advanced ovarian cancer is a death sentence, and there’s nothing they can do to treat it. Although bad news for the patient, this is also precisely why it’s perfectly rational to assume she doesn’t have ovarian cancer, and treat accordingly.

Back to our puzzle

While the ads are playing, let’s pretend we’re Alice for a moment. She’s just finished her 100 dice rolls and is now faced with deciding what her guess should be. Unfortunately it seems that all she knows about what’s going on in Bob’s room is that he’s following the strategy they agreed to at the start - which is all fine and good, but tells her nothing whatsoever about what’s written on Bob’s piece of paper. So how can she hope to do better than blindly guess?

The key realisation is that Alice does know something else - she may assume Bob’s guess is correct. This is because if Bob is wrong (i.e if the patient has ovarian cancer) then it doesn’t matter whether Alice (i.e House) guesses correctly or not - either way they lose. Hence we get

House’s rule: When devising a strategy, feel free to ignore any possibilities where you have no chance of success.

It sounds obvious, but let’s see how it solves our ‘almost trivially unsolvable’ problem. Notice that if Bob’s strategy took into account the results of his own dice rolls, then knowing his guess is correct (by House’s rule) gives us genuine information about what’s written on his sheet! If they are clever enough to realise all this in time, Alice and Bob might agree on both using a strategy like

“I’ll guess the index of my first 6.”

Then the knowledge that Bob is correct tells Alice:

• not only that he guessed one of her 6-s,

• but also that he guessed one of her 6-s because that’s where he has a 6

• and moreover that it was likely her first 6 that he guessed, since the most likely locations of his first 6 are at the beginning of the string.

So it makes sense for Alice to also guess her first 6, which is precisely what the strategy dictates - how neat!

It’s so nice, in fact, that it leaves little doubt that it’s the best possible strategy the two can hope for. This is what we’re about to prove, but let’s first check how much better than the naive $\frac{1}{36}$ we've managed.

Under our strategy, it's easy to check both guesses are correct iff the two players had their first 6 at the same exact time. The probability this occurs is (almost*) $\frac{1}{11}$ - indeed, consider the results of the first roll. If both dice show 6-s, we win. If exactly one shows a 6, we lose. In all other cases, we live to fight another day. So there's 1 good and 10 bad cases, all equally likely by symmetry - hence the result.

(*Almost, because there's a miniscule chance that we keep on living to fight another day until our 100 days run out. In other words, it's possible neither player ever rolls a 6. If this happens, though, no strategy can hope to succeed anyway - so again by House's rule we may assume this doesn't happen.)

Perhaps unsurprisingly, this “1 good and 10 bad” method of calculation is at the heart of why no other strategy can hope to do any better. To see this, imagine a scenario where Alice and Bob followed their cute little strategies (whatever they might be) and happened to succeed, say by guessing indices $X$ and $Y$ respectively. Now because they succeeded, both the relevant entries (i.e the $X$-th entry of Bob’s list and the $Y$-th entry of Alice’s) must have been 6-s. Imagine now what would’ve happened if those two particular dice results hadn’t been (6,6), but say (6,5). Then from Alice’s perspective, absolutely nothing is amiss and she’d still guess $X$ - and be wrong this time. Similarly if the “good” (6,6) is replaced by any of the ten “bad” pairs with a single 6, (at least) one of the players would be wrong. Thus no strategy can hope to beat $\frac{1}{11}$, and we're done.

Further problems

Having seen that "good" strategies which outperform $\frac{1}{36}$ exist, it is only natural that "bad" ones exist too. One particularly underwhelming example calls for Alice to guess the index of her first 6, while Bob guesses the index of his first non-6. By my calculations, this has a mere $\frac{1}{186}$ chance of success. Can one do worse?

Also, if we do away with the 100 roll restriction, is it true that any deterministic strategy has a probability of success reciprocal to a natural number?