I'm reading through Mitzenmacher and Vadan's book Probability and Computing. In Chapter 1.3, they outline a randomized algorithm for the following problem:
Given two $n \times n$ matrices $A$ and $B$ and a third matrix $C$, check whether $AB = C$, assuming we are working with integers modulo 2.
The algorithm works as follows: choose a uniformly random $n$-element vector $r$ of 0s and 1s, then return whether $A(Br) = Cr$. The book makes the following claims, all of which I'm comfortable with:
- If the algorithm is wrong, it means that $AB \ne C$ but that $ABr = Cr$.
- This in turn means $D = AB - C$ is not a zero matrix, but $Dr = 0$.
- Therefore, there is some nonzero entry in $D$. Assume WLOG it's the first entry of the first row of the matrix (i.e. $d_{11} \ne 0$).
- This means that $\sum_{i=1}^n{d_{1i} r_i} = 0$, or, equivalently, that $r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}$.
The book then proceeds to bound the probability that $r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}$ is true. They use the "principle of deferred decisions" to achieve this, and do so as follows:
$$\begin{aligned}Pr(r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}) &= \sum_{(x_2, x_3, ..., x_n) \in \{0, 1\}^{n-1}}{ Pr\left( \left(r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}\right) \cap \left( (r_2, r_3, ..., r_n) = (x_2, x_3, ..., x_n) \right)\right)} \\ &= \sum_{(x_2, x_3, ..., x_n) \in \{0, 1\}^{n-1}}{ Pr\left( r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i} \right) \cdot Pr \left( (r_2, r_3, ..., r_n) = (x_2, x_3, ..., x_n) \right)} \\ &\le \sum_{(x_2, x_3, ..., x_n) \in \{0, 1\}^{n-1}}{ \frac{1}{2} Pr \left( (r_2, r_3, ..., r_n) = (x_2, x_3, ..., x_n) \right)} \\ &= \frac{1}{2}. \end{aligned}$$
However, I had expected this analysis to look very different. Specifically, here's what I did. Begin by defining $Z = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i})$. Because we are working with integers modulo 2, we know that $Z$ can only take on the values of 0 and 1. Therefore, we can run the analysis as follows:
$$\begin{aligned}Pr(r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}) &= Pr(r_1 = Z) \\ &= Pr(r_1 = Z | Z = 0) Pr(Z = 0) + Pr(r_1 = Z | Z = 1) Pr(Z = 1) \\ &= Pr(r_1 = 0) Pr(Z = 0) + Pr(r_1 = 1) Pr(Z = 1) \\ &= \frac{1}{2} \left( Pr(Z = 0) + Pr(Z = 1) \right) \\ &= \frac{1}{2}.\end{aligned}$$
I suspect that I may have an error in here because the book ends up proving $Pr(r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}) \le \frac{1}{2}$, but my analysis shows the stronger $Pr(r_1 = \frac{-1}{d_{11}} \sum_{i=2}^n{d_{1i} r_i}) = \frac{1}{2}$ and I'm not able to identify why the original analysis ends up with an upper bound.
I have two questions:
- Is my analysis is correct?
- If my analysis is correct, can the upper bound in the textbook proof be replaced by a strict equality sign?
Thanks!
Your analysis appears correct, if $Z$ takes only values $0$ and $1$. If we are not working modulo $2$, then the value of $Z$ can be other than $0$ and $1$, and the probability that $r_1$ takes such a value would be zero. This is the only reason I can see that the authors would use an inequality in place of strict equality.
There are two upper bounds in the textbook's proof of Theorem 1.4. You've shown that the second one can be replaced by equality. However, the first upper bound is $$P(Dr=0)\le P\left(\sum_j d_{1j}r_j=0\right)$$ and the inequality here cannot in general be replaced by equality. Hence the conclusion remains $P(Dr=0)\le\frac12$.