keyboard problem

Problem 5.17 pg 87 of Biggs: A simplified keypad has four keys 
arranged in two rows of two). If the intention is to press key x, 
there is probability α of pressing the other key in the same row 
and probability α of pressing the other key in the same column 
(and consequently probability 1 − 2α of pressing x). Write down 
the channel matrix for this situation and find its capacity 
(i.e. the maximum entropy, or information per symbol, that can 
be sent with this keyboard).

Jim Mahoney | Feb 2014

We're given $\Gamma = P(Y|X)$ , the conditional probabilities of the noise, where $Y$ are the outputs (after the noise) and $X$ are the inputs (before the noise).

I'll use the symbol $f$ instead of $\alpha$ because it's easier to type in python code.

The keyboard is

a  b
c  d

so there are four possible inputs (a, b, c, d) and four possible outputs (a, b, c, d)

The 4 x 4 $\Gamma$ matrix is

P(y=a|x=a)  P(y=b|x=a)  P(y=c|x=a)  P(y=d|x=a)
P(y=a|x=b)  P(y=b|x=b)  P(y=c|x=b)  P(y=d|x=b)
P(y=a|x=c)  P(y=b|x=c)  P(y=c|x=c)  P(y=d|x=c)
P(y=a|x=d)  P(y=b|x=d)  P(y=c|x=d)  P(y=d|x=d)

and has the property that each row sums to 1.

From the description of the problem, the values of $\Gamma$ are

1-2f  f     f     0
f     1-2f  0     f
f     0     1-2f  f
0     f     f     1-2f

We don't know P(X), and so the most general approach would be to use a general form of P(X) i.e. $(q, r, s, 1-q-r-s)$ where q, r, s are unknowns, solve for the channel capacity in terms of (f, q, r, s), and then find the maximum when looping over all 0 < q,r,s < 1. Ugh.

From the symmetry of the problem, though, we can guess that the max capacity happens when $P(x=a) = P(x=b) = P(x=c) = P(x=d) = 1/4$. And by looking at small variations from that we can see if the capacity gets smaller to check that assumption.

In any case, given $P(X)$, we can multiply the rows of $\Gamma$ by the $P(x)$ values to get the joint probability distribution $P(x,y)$ (see below) and by summing the columns, get $P(Y)$ (see below).

So there you are.