<p>For notational convenience define r.v.s</p>
<ul>
<li><span class="math-container">$T_S = \min\{i : |S_i| = 1\}$</span> (recalling <span class="math-container">$S_i = S \cap H_1 \cap \cdots \cap H_i$</span>), and</li>
<li><span class="math-container">$T_H = \min\big\{i : H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}\big\}$</span>.</li>
</ul>
<ol>
<li><p>Then <span class="math-container">$P(S) = \Pr[T_S &lt; \infty]$</span> and <span class="math-container">$P_n(S) = \Pr[T_S \le n]$</span>.</p>
</li>
<li><p>In all outcomes <span class="math-container">$T_H \ge n$</span> because <span class="math-container">$|H_1 \cap \cdots \cap H_i| \ge 2^{n-i}$</span>, so <span class="math-container">$T_H \le n$</span> iff <span class="math-container">$T_H = n$</span>.</p>
</li>
<li><p>It seems to me that the desired inequality can be shown as follows:
<span class="math-container">$$\begin{align}
P_n(S) &amp; 
{} = \Pr[T_S \le n] &amp;&amp;(\textit{by the definitions}) \\
&amp; {} \ge \Pr[T_S \le n ~~|~ T_H = n]
 ~\times~ \Pr[T_H = n] &amp;&amp; (\textit{basic probability}) \\
&amp; {} =
\Pr[T_S &lt; \infty ~|~ T_H = n] 
 ~\times~ \Pr[T_H = n] &amp;&amp; (\textit{see Step 10 below}) \\
&amp; {} = \Pr[T_S &lt; \infty] ~\times~ \Pr[T_H = n] &amp;&amp; (\textit{see Step 20 below}) \\
&amp; {} = P(S) ~\times~ \Pr[H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}]
&amp;&amp; (\textit{by the definitions})
\end{align}$$</span></p>
</li>
</ol>
<hr />
<ol start="10">
<li><p>Next we argue that <span class="math-container">$\Pr[T_S \le n ~|~ T_H = n]$</span> equals <span class="math-container">$\Pr[T_S &lt; \infty ~|~ T_H = n]$</span>:</p>
</li>
<li><p>The event <span class="math-container">$T_H = n$</span> is equivalent to <span class="math-container">$H_1 \cap H_2 \cap \cdots \cap H_n = \{0^n\}$</span>.</p>
</li>
<li><p>Given this event,
<span class="math-container">$H_1 \cap H_2 \cap \cdots \cap H_i = \{0^n\}$</span>
and <span class="math-container">$S_i = S_n$</span> for each <span class="math-container">$i\ge n$</span>.</p>
</li>
<li><p>So (by the definitions) <span class="math-container">$T_S \le n$</span> iff <span class="math-container">$T_S &lt; \infty$</span>.</p>
</li>
<li><p>So <span class="math-container">$\Pr[T_S \le n ~|~ T_H = n]$</span> equals <span class="math-container">$\Pr[T_S &lt;\infty ~|~ T_H = n]$</span>,
as desired.</p>
</li>
</ol>
<hr />
<ol start="20">
<li><p>Next we argue that <span class="math-container">$\Pr[T_S &lt; \infty ~|~ T_H = n]$</span> equals <span class="math-container">$\Pr[T_S &lt; \infty]$</span>:</p>
</li>
<li><p>Call <span class="math-container">$w_i$</span> <em>redundant</em> if <span class="math-container">$H_1 \cap \cdots \cap H_i = H_1 \cap \cdots\cap H_{i-1}$</span>.</p>
</li>
<li><p>If <span class="math-container">$w_i$</span> is redundant, then <span class="math-container">$S_i = S_{i-1}$</span>, so, informally, the event <span class="math-container">$T_S &lt; \infty$</span> is independent of redundant <span class="math-container">$w_i$</span>'s.</p>
</li>
<li><p>Formally, consider modifying the random experiment so that redundant <span class="math-container">$w_i$</span>'s are ignored. That is, redefine <span class="math-container">$w_i$</span> to be the <span class="math-container">$i$</span>th <em>non-redundant</em> random vector. This does not change <span class="math-container">$\Pr[T_S &lt; \infty]$</span>.</p>
</li>
<li><p>But this modification is exactly the same as conditioning on <span class="math-container">$T_H \le n$</span>, because each redundant vector doesn't change <span class="math-container">$H_i$</span>,
while each non-redundant vector cuts <span class="math-container">$|H_i|$</span> by a factor of two,
so the distribution of first <span class="math-container">$n$</span> non-redundant vectors
is exactly the same as the distribution of the first <span class="math-container">$n$</span> vectors
<em>conditioned on <span class="math-container">$T_H \le n$</span>.</em>  (Out of time here, ask in comments if you have questions.)</p>
</li>
</ol>
<hr />

CC BY-SA 4.0
2024-04-14T20:24:27.023Z
Thank you for your answer!
deltaepsilonnn
CC BY-SA 4.0
2024-04-13T21:35:13.950Z
2024-04-22T19:15:36.850Z
2024-04-22T19:15:36.850Z
Neal Young
<p>I have a question about the paper <a href="https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf" rel="noreferrer">&quot;NP is as easy as detecting unique solutions&quot;</a> by Valiant and Vazirani, specifically the proof of the Theorem 2.4(i).</p>
<p>The proof starts by saying</p>
<blockquote>
<p>Clearly, <span class="math-container">$P_n(S) \ge P(S) \cdot \Pr(H_1 \cap \ldots \cap H_n = \{ 0^n\})$</span></p>
</blockquote>
<p>Here, <span class="math-container">$S \subseteq \{0, 1\}^n$</span>,
<span class="math-container">$P_n(S)$</span> is defined as the probability over random vectors <span class="math-container">$w_1, \ldots, w_n$</span> that there is some <span class="math-container">$i$</span> between <span class="math-container">$1$</span> and <span class="math-container">$n$</span> such that <span class="math-container">$|S_i| = 1$</span> where <span class="math-container">$S_i = \{v \in S : v \cdot w_1 = \cdots = v \cdot w_i = 0\}$</span> where we take dot products mod 2.
Also, <span class="math-container">$H_i = \{ v \in \{0, 1\}^n : v \cdot w_i = 0 \}$</span>.</p>
<p>And <span class="math-container">$P(S)$</span> is defined to be the probability over infinite sequence <span class="math-container">$w_1, \ldots$</span> such that there is some <span class="math-container">$i$</span> such that <span class="math-container">$|S_i| = 1$</span>.</p>
<p>Could anyone provide an explanation why the above statement is true?</p>
<p>We can show that the event <span class="math-container">$\{ \exists i, \lvert S_i \rvert = 1 \&amp; H_1 \cap \cdots \cap H_n = \{0^n\} \}$</span> is contained in <span class="math-container">$\{ \exists i \le n, \lvert S_i \rvert = 1 \}$</span>. So, it is sufficient to show that <span class="math-container">$\Pr(\{ \exists i, \lvert S_i \rvert = 1 \&amp; H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S) P(H_1 \cap \cdots \cap H_n = \{0^n\})$</span>.
This is equivalent to showing that <span class="math-container">$\Pr(\{ \exists i, \lvert S_i \rvert = 1 \mid H_1 \cap \cdots \cap H_n = \{0^n\} \}) \ge P(S)$</span>.</p>
<p>My intuition is that the probability of the infinite sequence <span class="math-container">$\lvert S_i \rvert$</span> hitting to <span class="math-container">$1$</span> is independent of what happens to the sequence of <span class="math-container">$H_1 \cap \cdots \cap H_k$</span> for a fixed <span class="math-container">$k$</span>, since with probability <span class="math-container">$1$</span>, the intersection of <span class="math-container">$H_i$</span> will become <span class="math-container">$\{0^n\}$</span> at some point. But I am not really sure how to formalize this idea.</p>

CC BY-SA 4.0
2024-04-11T11:35:31.880Z
Clearly, $P_n(S)\ge\Pr[\exists i\,|S_i|=1\& H_1\cap\dots\cap H_n=\{0\}]$. But it’s not clear to me why these two events should be independent (if that is intended to be the argument).
Emil Jeřábek
CC BY-SA 4.0
2024-04-11T14:07:47.747Z
@EmilJeřábek That is as far as I got also. If we assume that $| S_i |$ becomes 1 at some point and $H_1 \cap \cdots \cap H_n = \{ 0^n \}$ then $S_i$ must have become singleton for some $i \le n$. I do not think those two events are independent, but it seems sufficient to show that they have a positive correlation. I am just not seeing it for the case when $0^n \notin S$.
deltaepsilonnn
CC BY-SA 4.0
2024-04-13T06:07:33.250Z
Please don't use "EDIT: more stuff".  Instead, revise the question so it reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755
D.W.
CC BY-SA 4.0
2024-04-13T15:11:13.300Z
To make the post more self-contained, can you give the definition of $H_i = \{ v : v\cdot w_i = 0 \}$?
Neal Young
CC BY-SA 4.0
2024-04-14T20:22:24.937Z
@NealYoung Added!
deltaepsilonnn
<pr.probability><linear-algebra><randomness><unique-solution>
Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"
deltaepsilonnn
# Theorem 2.4(i) in Valiant-Vazirani paper "NP is as easy as detecting unique solutions"

(Asked by: username_0 on 2024-04-10)

I have a question about the paper ["NP is as easy as detecting unique solutions"](https://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/NP_is_as.pdf) 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.

**Tags:** pr.probability, linear-algebra, randomness, unique-solution
> **Comments:**
> **username_1**: Clearly, $P_n(S)\ge\Pr[\exists i\,|S_i|=1\& H_1\cap\dots\cap H_n=\{0\}]$. But it’s not clear to me why these two events should be independent (if that is intended to be the argument).  
> **username_0**: @EmilJeřábek That is as far as I got also. If we assume that $| S_i |$ becomes 1 at some point and $H_1 \cap \cdots \cap H_n = \{ 0^n \}$ then $S_i$ must have become singleton for some $i \le n$. I do not think those two events are independent, but it seems sufficient to show that they have a positive correlation. I am just not seeing it for the case when $0^n \notin S$.  
> **username_2**: Please don't use "EDIT: more stuff".  Instead, revise the question so it reads well for someone who encounters it for the first time.  See https://cs.meta.stackexchange.com/q/657/755  
> **username_3**: To make the post more self-contained, can you give the definition of $H_i = \{ v : v\cdot w_i = 0 \}$?  
> **username_0**: @NealYoung Added!  

---

## 1 answers

### Answer by username_3 on 2024-04-13. Score: 10 | Accepted answer

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.)

---

> **Comments:**
> **username_0**: Thank you for your answer!  

---

