Always Blame the Autograder [Solution]

Solution for the week of 4/13

Last week Professor Hadamard was wrestling with his crummy grading program.

While reviewing the code, he discovered a flaw: the part of the program that determined whether a student had answered “True” or “False” was occasionally incorrect. Specifically, it had a 10% chance of flipping each answer—so if a student marked “True,” the system would incorrectly record it as “False” with probability 0.1, and vice versa. Upon realizing this, Professor Hadamard decided to go back and check the tests by hand. He confirmed that the students’ actual answers were indeed pairwise orthogonal—just as the system had reported, despite the flaw. To be clear, he did not check whether each individual answer had been read correctly—only whether the actual test results were pairwise orthogonal.

The question for this week is how likely was was this?

In other words, if we have assume that the actual student test answer are pairwise orthogonal, and that the the test scoring program has a 10% chance of flipping an answer, what is the probability that program would also believe that the students’ test answers were pairwise orthogonal?

Shout out to

Eric Widdison

for the sole solution submission. He arrived at the correct answer in a very different way than I did so I strongly recommend reading his solution.

Recall that we were starting with a valid Hadamard matrix and want to compute the probability that it remains a Hadamard matrix if each element of the matrix is flipped with probability 10%. We know that each row of a Hadamard matrix H is pairwise orthogonal to each other row. If we let i and j be rows of the Hadamard matrix, then this can be written as

\(H_i \cdot H_j = 0\)

when i≠j. Let’s let F be a random matrix where each element is -1 with probability p (i.e. a flip) and 1 with probability 1-p (no flip). We need to determine what transformations to H will preserve pairwise orthogonality (PO) so that we can determine the structure of F. There are a few obvious transformations:

1. permutation of the rows of H

2. multiplication of a row by -1 (and trivially +1)

3. multiplication of a column by -1 (and trivially +1)

As it turns out, these are the only PO preserving transformations for Hadamard matrices up to size N=12. The tricky part of this problem (in my opinion) is realizing and leveraging this fact. I tried coming up with some simpler proofs—other than invoking isometries with the hyperoctahedral group—to verify this but I wasn’t able to.

So knowing that these are the only transformations we can perform, how likely is it that F preserves PO? First, let’s start with the permutations. This will become clearer as we go but we don’t actually need to consider every possible permutation of rows. It will suffice to consider the number of fixed rows c. This is because we are concerned with the number of entries that get flipped, which is fully determined by c. More specifically, given c, we know that the number of entries a_π of H that will be unchanged is

\(\begin{align*} &a_{\pi} = cN + (N-c)\frac{N}{2} = \frac{N^2 + cN}{2} \\ &b_{\pi} = N^2 - cN - (N-c)\frac{N}{2} = \frac{N^2 - cN}{2} \end{align*}\)

Similarly, the number of entries that are flipped is given by b_π above.

Ok great! So far we have

\(\begin{align*} &\Pr[\text{flips preserve Hadamard}] \\ &= \sum_{c=0}^N N_c \left(\Pr[\text{entry isn't flipped}]\right)^{\frac{N^2 + cN}{2}} \left( \Pr[\text{entry is flipped}]\right)^{\frac{N^2 - cN}{2}} \\ & \text{where $N_c$ is the number of permutations that fix $c$ elements} \end{align*}\)

Now we might be tempted to let Pr[entry is flipped]=p=0.1 but we need to remember that this probability needs to account for the Hadamard structure of F. In particular, if the ways of preserving the Hadamard structure is accomplished by multiplying an entire row or column by -1, then for an entry to be unflipped, either both its column and row get flipped or neither get flipped, yielding the probability q below. Conversely, for an entry to be flipped then one of the row or column must be flipped but not both. This yields the probability r below.

\(\begin{align*} &q = p^2 + (1-p)^2 \\ &r = 2p(1-p) \end{align*}\)

To be honest, The reasoning I just stated isn’t quite accurate. In reality, q and r represent the probability of a given entry F_ij has value +1 or -1 when we consider all possible 2^(2N) row and column negations. The justification for this is subtler and not terribly dissimilar to the description above so I’ll just leave it at that.

Using q and r, we can sum over all the different possible number of fixed points c to get our probability.

\(\begin{align*} &\Pr[\text{flips preserve Hadamard}] \\ &= \sum_{c=0}^N N_c q^{\frac{N^2 + cN}{2}} r^{\frac{N^2 - cN}{2}} \end{align*}\)

All that remains is determining the number of permutations that result in exactly c fixed elements. These are given by the Rencontres numbers which are pretty easy to derive. We simply choose c elements to fix and consider all possible derangements of the remaining elements.

\(\begin{align*} &D_{n,c} = \binom{n}{c} D_{n-k,0} \\ &\text{ where $D_{m,0}$ is the derangement on $m$ elements} \end{align*}\)

So we have our final expression

\(\begin{align*} &\Pr[\text{flips preserve Hadamard}] \\ &= \sum_{c=0}^N D_{N,c} q^{\frac{N^2 + cN}{2}} r^{\frac{N^2 - cN}{2}} \end{align*}\)

Evaluating this for N=4 and p=0.1 give 18.68%

As always, please comment with any thoughts or feedback you had on this problem or if you approached it differently. Thanks for reading!