<p>Suppose you had such a randomized procedure that takes a value in <span class="math-container">$\{-1,1\}$</span> and outputs a real number. Let <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> be the output distribution on input <span class="math-container">$+1$</span> and <span class="math-container">$-1$</span> respectively.</p>
<p>Consider the extreme case of <span class="math-container">$\mu = +1$</span>. In this case <span class="math-container">$Y = +1$</span> for sure, and you are outputting a sample from <span class="math-container">$P$</span>, which means that <span class="math-container">$P$</span> should be an <span class="math-container">$\mathcal{N}(\nu, 1)$</span> distribution for some <span class="math-container">$\nu$</span> with <span class="math-container">$|\nu|$</span> being <span class="math-container">$\Omega(1)$</span>. Similarly, the other extreme of <span class="math-container">$\mu=-1$</span> tells us that <span class="math-container">$Q$</span> is a <span class="math-container">$\mathcal{N}(\nu', 1)$</span> distribution for some <span class="math-container">$\nu'$</span> with <span class="math-container">$|\nu'|$</span> being <span class="math-container">$\Omega(1)$</span>.</p>
<p>But now, for <span class="math-container">$\mu=0$</span>, you are outputting the uniform mixture of two normals, which cannot be a normal distribution unless <span class="math-container">$\nu=\nu'$</span>. In the latter case, you get <span class="math-container">$\mathcal{N}(\nu, 1)$</span> for some <span class="math-container">$\nu$</span> bounded away from zero.</p>
<p>Thus you cannot satisfy this requirement simultaneously for <span class="math-container">$\mu\in \{-1, 0, 1\}$</span>.</p>

CC BY-SA 4.0
2020-12-16T00:52:21.093Z
That was fast—thanks!
Clement C.
CC BY-SA 4.0
2020-12-16T00:41:27.590Z
2020-12-16T00:41:27.590Z
Kunal
<p>It is not hard to see that, given one sample from a univariate unit-variance Gaussian <span class="math-container">$X\sim \mathcal{N}(\mu,1)$</span> with unknown <span class="math-container">$\mu$</span> s.t. <span class="math-container">$0&lt;|\mu|\leq 1$</span>, one can simulate one draw from a
&quot;Bernoulli&quot; random variable <span class="math-container">$Y\in\{-1,1\}$</span> with <span class="math-container">$|\mathbb{E}[Y]| = \Theta(|\mu|)$</span>. (Basically, just take <span class="math-container">$Y=\operatorname{sign}(X)$</span>.)</p>
<p>Is it possible to do the converse (even allowing extra randomness, independent of the sample)? That is:</p>
<blockquote>
<p>Given one realization of some random variable <span class="math-container">$Y\in\{-1,1\}$</span> with (unknown) <span class="math-container">$\mathbb{E}[Y] = \mu$</span>, output <span class="math-container">$X\sim \mathcal{N}(\nu,1)$</span> s.t. <span class="math-container">$|\nu| = \Theta(|\mu|)$</span>.</p>
</blockquote>
<p>I conjecture that to be impossible <em>(I have some mild contrived evidence)</em>, but I don't really see how one would go about proving that.</p>

<randomized-algorithms><it.information-theory><randomness>
Converting a Bernoulli to a Gaussian
Clement C.
# Converting a Bernoulli to a Gaussian

(Asked by: username_0 on 2020-12-15)

It is not hard to see that, given one sample from a univariate unit-variance Gaussian $X\sim \mathcal{N}(\mu,1)$ with unknown $\mu$ s.t. $0<|\mu|\leq 1$, one can simulate one draw from a
"Bernoulli" random variable $Y\in\{-1,1\}$ with $|\mathbb{E}[Y]| = \Theta(|\mu|)$. (Basically, just take $Y=\operatorname{sign}(X)$.)

Is it possible to do the converse (even allowing extra randomness, independent of the sample)? That is:

> Given one realization of some random variable $Y\in\{-1,1\}$ with (unknown) $\mathbb{E}[Y] = \mu$, output $X\sim \mathcal{N}(\nu,1)$ s.t. $|\nu| = \Theta(|\mu|)$.

I conjecture that to be impossible *(I have some mild contrived evidence)*, but I don't really see how one would go about proving that.

**Tags:** randomized-algorithms, it.information-theory, randomness

---

## 1 answers

### Answer by username_1 on 2020-12-16. Score: 6 | Accepted answer

Suppose you had such a randomized procedure that takes a value in $\{-1,1\}$ and outputs a real number. Let $P$ and $Q$ be the output distribution on input $+1$ and $-1$ respectively.

Consider the extreme case of $\mu = +1$. In this case $Y = +1$ for sure, and you are outputting a sample from $P$, which means that $P$ should be an $\mathcal{N}(\nu, 1)$ distribution for some $\nu$ with $|\nu|$ being $\Omega(1)$. Similarly, the other extreme of $\mu=-1$ tells us that $Q$ is a $\mathcal{N}(\nu', 1)$ distribution for some $\nu'$ with $|\nu'|$ being $\Omega(1)$.

But now, for $\mu=0$, you are outputting the uniform mixture of two normals, which cannot be a normal distribution unless $\nu=\nu'$. In the latter case, you get $\mathcal{N}(\nu, 1)$ for some $\nu$ bounded away from zero.

Thus you cannot satisfy this requirement simultaneously for $\mu\in \{-1, 0, 1\}$.

> **Comments:**
> **username_0**: That was fast—thanks!  

---

