This question relates to the 2nd edition of Probability and Computation by Mitzenmacher and Upfal.

enter image description here

enter image description here

The authors then use the Law of Total Probability enter image description here

My question concerns the line that begins with $\leq$. Shouldn't that be replaced with $=$ because the authors proved that the event $\mathbf{AB} \bar{r} = \mathbf{C}\bar{r}$ is equivalent to the event $$r_{1} = - \frac{\sum_{j=2}^n d_{1j} r_{j}}{d_{11}}$$ ?

  • 3
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX. $\endgroup$
    – D.W.
    Commented Oct 31, 2021 at 23:04
  • $\begingroup$ The authors do not say that $AB\bar{r} = C\bar{r}$ is equivalent to the event $r_1 = -\sum_j d_{1j}r_j / d_{11}$, rather that it implies it. $\endgroup$ Commented Jul 29, 2022 at 13:01

1 Answer 1


I'm assuming that all matrices in question are $n \times n$.

Suppose that $A=B=0$ are zero matrices and $C=I$ is the identity matrix. Then $$ \Pr[ABr = Cr] = \Pr[r = 0] = 2^{-n}. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.