<p>I am reading a research paper where multiple times the authors use the following, which they claim follows from an averaging argument.</p>
<p><strong>Claim:</strong> Suppose <span class="math-container">$\mathcal{X}$</span> and <span class="math-container">$\mathcal{Y}$</span> are two finite domains. Suppose <span class="math-container">$A(x,y)$</span> is a probabilistic Turing machine such that for some <span class="math-container">$p&lt;1$</span>,</p>
<p><span class="math-container">$$\mathrm{Pr}_{x \in \mathcal{X}, y \in \mathcal{Y}} [A(x,y)=1] \geq 1-p.$$</span></p>
<p>Then,</p>
<p><span class="math-container">$$\mathrm{Pr}_{x \in \mathcal{X}} \left[\mathrm{Pr}_{ y \in \mathcal{Y}}[A(x,y)=1] \geq 1-\sqrt{p}\right] \geq 1-\sqrt{p}.$$</span></p>
<p>I am unable to see why such a strong bound follows from an averaging argument. I am convinced for example that the following weaker statement follows from averaging:</p>
<p><span class="math-container">$$\mathrm{Pr}_{x \in \mathcal{X}} \left[\mathrm{Pr}_{ y \in \mathcal{Y}}[A(x,y)=1] \geq \frac{1-p}{2}\right] \geq \frac{1-p}{2}.$$</span></p>
<p>It will be very helpful if you can provide a proof that the stronger claim is true. If it is not, I would like to know what is the best bound of the form <span class="math-container">$\mathrm{Pr}_{x \in \mathcal{X}} \left[\mathrm{Pr}_{ y \in \mathcal{Y}}[A(x,y)=1] \geq c\right] \geq c$</span> that can be obtained in the above scenario.</p>

CC BY-SA 4.0
2024-10-23T21:13:25.953Z
This is not a research-level question, and should have been asked at https://cs.stackexchange.com . The bound with $c=1-\sqrt p$ is indeed correct by trivial computation: putting $q=\Pr_x[\Pr_y[A(x,y)=1]\ge1-\sqrt p]$, we have $1-p\le\Pr_{x,y}[A(x,y)=1]\le q+(1-q)(1-\sqrt p)=1-(1-q)\sqrt p$, thus $q\ge1-\sqrt p$.
Emil Jeřábek
CC BY-SA 4.0
2024-10-23T21:35:55.393Z
Sorry, I was not aware that such questions should have been posted at cs.stackexchange. Thanks for your answer, the proof is clear to me now.
Subin Pulari
<pr.probability><randomized-algorithms><probabilistic-computation><cryptography>
Strongest lower bound from averaging argument for probability $\geq 1-p$?
Subin Pulari
# Strongest lower bound from averaging argument for probability $\geq 1-p$?

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

I am reading a research paper where multiple times the authors use the following, which they claim follows from an averaging argument.

**Claim:** Suppose $\mathcal{X}$ and $\mathcal{Y}$ are two finite domains. Suppose $A(x,y)$ is a probabilistic Turing machine such that for some $p<1$,

$$\mathrm{Pr}\_{x \in \mathcal{X}, y \in \mathcal{Y}} [A(x,y)=1] \geq 1-p.$$

Then,

$$\mathrm{Pr}\_{x \in \mathcal{X}} \left[\mathrm{Pr}\_{ y \in \mathcal{Y}}[A(x,y)=1] \geq 1-\sqrt{p}\right] \geq 1-\sqrt{p}.$$

I am unable to see why such a strong bound follows from an averaging argument. I am convinced for example that the following weaker statement follows from averaging:

$$\mathrm{Pr}\_{x \in \mathcal{X}} \left[\mathrm{Pr}\_{ y \in \mathcal{Y}}[A(x,y)=1] \geq \frac{1-p}{2}\right] \geq \frac{1-p}{2}.$$

It will be very helpful if you can provide a proof that the stronger claim is true. If it is not, I would like to know what is the best bound of the form $\mathrm{Pr}\_{x \in \mathcal{X}} \left[\mathrm{Pr}\_{ y \in \mathcal{Y}}[A(x,y)=1] \geq c\right] \geq c$ that can be obtained in the above scenario.

**Tags:** pr.probability, randomized-algorithms, probabilistic-computation, cryptography

> **Comments:**
> **username_1**: This is not a research-level question, and should have been asked at https://cs.stackexchange.com . The bound with $c=1-\sqrt p$ is indeed correct by trivial computation: putting $q=\Pr_x[\Pr_y[A(x,y)=1]\ge1-\sqrt p]$, we have $1-p\le\Pr_{x,y}[A(x,y)=1]\le q+(1-q)(1-\sqrt p)=1-(1-q)\sqrt p$, thus $q\ge1-\sqrt p$.  
> **username_0**: Sorry, I was not aware that such questions should have been posted at cs.stackexchange. Thanks for your answer, the proof is clear to me now.  

---

## 0 answers

