# Bounded simulations between Bernoulli distributions

Let $B(p)$ be the Bernoulli distribution associated to the probability $p$. Let $(→)$ be the relation such that $(p→q)$ iff you can generate $B(q)$ from $B(p)$ with a bounded number of draws. (This implies that rejection sampling is not relevant here.)

Obviously $p→1-p$ since you just need to swap the output bit. In fact I think that the relation is characterized by:

$$p→\sum_{i=0}^{n}a_ip^i(1-p)^{n-i}$$

for any integer sequence $(a_i)_{i≤n}$ such that $a_i≤\binom{n}{i}$. This is done by sampling $n$ times and then choosing which words $w$ of $\{0,1\}^n$ will be mapped to $0$ and which will be mapped to $1$. The probability of $w$ is $P(w)=p^{|w|_1}(1-p)^{|w|_0}$. The bound on $a_i$ comes from the fact that for each $i$ there is exactly $\binom{n}{i}$ words $w$ with $i$ $1$'s and $(n-i)$ $0$'s.

My questions are:

(1) Is there an easier characterization of this relation?

(2) Is there a characterization of $D=\{p ∣ p→\frac12\}$?

For now it seems obvious that $\frac13∉D$ and more generally that it only contains only dyadic numbers. What is more surprising to me is that it seems that $\frac14∉D$.

-
How do you mean "rejection sampling is not an option"? How do you rigorously distinguish between instances and non-instances of rejection sampling? – joriki May 19 '12 at 22:36
@joriki: sorry, this is not a requirement but a consequence of the fact that the number of draws should be bounded. Rejection sampling only has a bound on the expected number of draws. I hope the question is more clear now. – jmad May 19 '12 at 22:43
I see; thanks for the clarification. – joriki May 20 '12 at 9:39
I think you mean any integer sequence $(a_i)_{i\le n}$ such that $a_i\le\binom{n}{i}$? – joriki May 20 '12 at 9:45
Integer, yes. I edited and explained the reason of the bound. – jmad May 20 '12 at 13:56

Fact: The set $D$ is at most countable.

Proof: The map $(n,a_0,a_1,\ldots,a_n)\mapsto p$ is surjective.

Fact: The set $D$ contains irrational numbers.

Proof: Use $a_n=1$ and $a_i=0$ for every $i\leqslant n-1$. Hence $p$ such that $p^n=1/2$ is in $D$.

Fact: For every integer $k\geqslant2$, $p=1/(k+1)$ is not in $D$.

Proof: Otherwise, there exists $n\geqslant0$ and some admissible integers $(a_i)$ such that $$2\sum\limits_{i=0}^na_ik^{n-i}=(k+1)^n.$$ In particular, $2a_n=1\pmod{k}$ with $a_n=0$ or $a_n=1$. Both options are absurd if $k\geqslant2$.

Fact: The only rational numbers in $D$ are $0$, $1$ and $1/2$.

Proof: Let $p=u/v$ denote a rational number in $D$ with $p\ne0$, $p\ne1$, $p\ne1/2$, and $u$ and $v$ relatively prime. Assume without loss of generality that $u\geqslant2$. Then, there exists $n\geqslant0$ and some admissible integers $(a_i)$ such that $$2\sum\limits_{i=0}^na_iu^i(v-u)^{n-i}=v^n.$$ In particular, $2a_0(v-u)^n=v^n\pmod{u}$. Since $(v-u)^n=v^n\pmod{u}$ and $v$ is invertible modulo $u$, $2a_0=1\pmod{u}$. Since $a_0=0$ or $a_0=1$, and $u\geqslant2$, this is absurd.

To sum up: The set $D$ contains $0$, $1$, $1/2$, $1/\sqrt[n]{2}$ for every $n\geqslant2$, and other irrational numbers, at most countably many.

-
Thanks for your answer. Can you give an example of an irrational number in $D$? – jmad May 20 '12 at 14:54
$p=1/\sqrt2$.  – Did May 20 '12 at 14:56