Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

Question

I have a question about the paper "NP is as easy as detecting unique solutions" by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i).

The proof starts by saying

Clearly, $P_n(S) \ge P(S) \cdot \Pr(H_1 \cap \ldots \cap H_n = \{ 0^n\})$

Here, $S \subseteq \{0, 1\}^n$, $P_n(S)$ is defined as the probability over random vectors $w_1, \ldots, w_n$ that there is some $i$ between $1$ and $n$ such that $|S_i| = 1$ where $S_i = \{v \in S : v \cdot w_1 = \cdots = v \cdot w_i = 0\}$ where we take dot products mod 2. Also, $H_i = \{ v \in \{0, 1\}^n : v \cdot w_i = 0 \}$.

And $P(S)$ is defined to be the probability over infinite sequence $w_1, \ldots$ such that there is some $i$ such that $|S_i| = 1$.

Could anyone provide an explanation why the above statement is true?

We can show that the event $\{ \exists i, \lvert S_i \rvert = 1 \& H_1 \cap \cdots \cap H_n = \{0^n\} \}$ is contained in $\{ \exists i \le n, \lvert S_i \rvert = 1 \}$. So, it is sufficient to show that $\Pr(\{ \exists i, \lvert S_i \rvert = 1 \& H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S) P(H_1 \cap \cdots \cap H_n = \{0^n\})$. This is equivalent to showing that $\Pr(\{ \exists i, \lvert S_i \rvert = 1 \mid H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S)$.

My intuition is that the probability of the infinite sequence $\lvert S_i \rvert$ hitting to $1$ is independent of what happens to the sequence of $H_1 \cap \cdots \cap H_k$ for a fixed $k$, since with probability $1$, the intersection of $H_i$ will become $\{0^n\}$ at some point. But I am not really sure how to formalize this idea.

Answer 1

For notational convenience define r.v.s

• $T_S = \min\{i : |S_i| = 1\}$ (recalling $S_i = S \cap H_1 \cap \cdots \cap H_i$), and
• $T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$.

1. Then $P(S) = \Pr[T_S < \infty]$ and $P_n(S) = \Pr[T_S \le n]$.

2. In all outcomes $T_H \ge n$ because $|H_1 \cap \cdots \cap H_i| \ge 2^{n-i}$, so $T_H \le n$ iff $T_H = n$.

3. It seems to me that the desired inequality can be shown as follows: $$\begin{align} P_n(S) & {} = \Pr[T_S \le n] &&(\textit{by the definitions}) \\ & {} \ge \Pr[T_S \le n ~~|~ T_H = n] ~\times~ \Pr[T_H = n] && (\textit{basic probability}) \\ & {} = \Pr[T_S < \infty ~|~ T_H = n] ~\times~ \Pr[T_H = n] && (\textit{see Step 10 below}) \\ & {} = \Pr[T_S < \infty] ~\times~ \Pr[T_H = n] && (\textit{see Step 20 below}) \\ & {} = P(S) ~\times~ \Pr[H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}] && (\textit{by the definitions}) \end{align}$$

---

10. Next we argue that $\Pr[T_S \le n ~|~ T_H = n]$ equals $\Pr[T_S < \infty ~|~ T_H = n]$:

11. The event $T_H = n$ is equivalent to $H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}$.

12. Given this event, $H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}$ and $S_i = S_n$ for each $i\ge n$.

13. So (by the definitions) $T_S \le n$ iff $T_S < \infty$.

14. So $\Pr[T_S \le n ~|~ T_H = n]$ equals $\Pr[T_S <\infty ~|~ T_H = n]$, as desired.

---

20. Next we argue that $\Pr[T_S < \infty ~|~ T_H = n]$ equals $\Pr[T_S < \infty]$:

21. Call $w_i$ redundant if $H_1 \cap \cdots \cap H_i = H_1 \cap \cdots\cap H_{i-1}$.

22. If $w_i$ is redundant, then $S_i = S_{i-1}$, so, informally, the event $T_S < \infty$ is independent of redundant $w_i$'s.

23. Formally, consider modifying the random experiment so that redundant $w_i$'s are ignored. That is, redefine $w_i$ to be the $i$th non-redundant random vector. This does not change $\Pr[T_S < \infty]$.

24. But this modification is exactly the same as conditioning on $T_H \le n$, because each redundant vector doesn't change $H_i$, while each non-redundant vector cuts $|H_i|$ by a factor of two, so the distribution of first $n$ non-redundant vectors is exactly the same as the distribution of the first $n$ vectors conditioned on $T_H \le n$. (Out of time here, ask in comments if you have questions.)

---