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:


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

  • $\begingroup$ How do you mean "rejection sampling is not an option"? How do you rigorously distinguish between instances and non-instances of rejection sampling? $\endgroup$ – joriki May 19 '12 at 22:36
  • $\begingroup$ @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. $\endgroup$ – jmad May 19 '12 at 22:43
  • $\begingroup$ I see; thanks for the clarification. $\endgroup$ – joriki May 20 '12 at 9:39
  • $\begingroup$ I think you mean any integer sequence $(a_i)_{i\le n}$ such that $a_i\le\binom{n}{i}$? $\endgroup$ – joriki May 20 '12 at 9:45
  • $\begingroup$ Integer, yes. I edited and explained the reason of the bound. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.