I'm designing a deduction/guessing game (similar to 'Mastermind') and I want to quantify the difficulty for the guesser. I believe the way to do this is by computing how much mutual information is shared between two random variables that describe the game, however I'm having trouble with this calculation.
Below is a simplified example,
The game: Imagine a deck of cards with two suits and three values: $\{A1, A2, A3, B1, B2, B3\}$. The 'choosing' player chooses a card uniformly at random, memorises the suit and value, then puts it back in the deck. The 'guessing' player then reveals two cards at random from the shuffled deck, and asks the 'choosing' player how many properties of the two revealed cards match their chosen card. The 'choosing' player must answer truthfully. E.g. if I chose the card $A1$, and the revealed cards were $\{A3, B1\}$, I would answer '2' - one suit, and one value matches. The deck is then shuffled and two more cards revealed. This repeats until the 'guessing' player knows exactly which card was chosen.
If we denote the target card $t$, then the probability distribution over possible target cards is a random variable $T$ that is uniform, $P_T(T=t) = 1/6 \ \forall t$.
If we denote the number of matching properties from two revealed cards as $m$, then the probability distribution over possible match counts is a random variable $M$. Enumerating the ${}_6C_2 = 15$ possible pairs of cards that can be revealed shows that $M$ is distributed as below;
$$ \begin{array}{c|c} m & P_M(M=m) \\ \hline 0 & 1/15 \\ 1 & 6/15 \\ 2 & 5/15 \\ 3 & 3/15 \end{array} $$
I want to know how much each pair of revealed cards 'helps' the guessing player. To do this, I was trying to compute the mutual information I(T, M).
$$ \begin{align} I(T,M) = \sum_{t=1}^6 \sum_{m=0}^3 P_{(T,M)}(t, m) \log \left( \frac{P_{(T,M)}(t, m)}{P_T(t) P_M(m)} \right) \end{align} $$
Because $T$ is uniform, I believe the joint PMF will just be $P_{(T,M)}(t, m) = \frac{1}{6} P_M(m) \implies I(T,M) = 0$. However, it seems this must be wrong, as intuitively, this game will be easy to solve for the guesser after just a few cards are revealed.
- Is mutual information a valid way to quantify the guesser's difficulty?
- Have I computed $I(T,M)$ correctly here?
You’re ignoring the fact that the guesser obtains not just the value of $M$ but the identity of the two cards. If you kept drawing pairs of cards and only telling the guesser the values of $M$ without showing them the cards, then indeed they would not be gaining any information at all about the card to be guessed. But that’s very far from how the game works. The information they’re getting is the mutual information between the pair of cards and the $M$ value as a whole on the one hand and $T$ on the other hand, and there’s a strong dependence between these two variables and thus a lot of mutual information.