Bias-free adjustment of random bit strings

Question

Let's say you have a source of random bit strings, which can generate a bit string of any length where each bit is independently set with fixed probability $p$, which I'll call my $p$-source.

Now imagine you want a bit string of length $n$ with bits set with probability $p'$ instead of $p$. Assume for now that $p' > p$ although the other case should be symmetric.

Is it possible to generate a length-$n$ string using my $p$-source, and then set $f(n, p, p', X)$ additional bits in the bitstring so that each bit in the resulting string is now set, independently, with probability $p'$? Here $X$ is a random variable we can use, since I'm pretty sure that f cannot return a fixed value but itself must draw from some distribution.

If it is possible, what is f?

Additional Notes

f should be independent of the particular string selected. I.e., the algorithm employed by f shouldn't need as input the string, but should independently select some bits to set.

I expect that difference between $p$ and $p'$ to be small, e.g, $p' - p < 0.01$ typically, although of course this probably doesn't matter with respect to the correctness of most solutions.

Answer 1

Imagine going through the bits one by one and setting each of them (independent of its previous state, and of the other bits) with probability $r$, and leaving it unchanged with probability $1-r$. Since the bit was originally set with probability $p$, it's now set with probability

$$ p(1-r)+r\stackrel!=p'\;, $$

so if we choose

$$ r=\frac{p'-p}{1-p}\;, $$

the modified string will be indistinguishable from a string generated with probability $p'$ for bits to be set. Instead of going through the bits individually, you can draw $f(n,p,p',X)$ from a binomial distribution with parameters $n$ and $r$ and then uniformly randomly select that many bits to set.

The original answer below is unnecessarily complicated; I'll just leave it there to document the thought process (or perhaps because I want to avoid the pain of having to delete my work :-).

---

You have exactly the right number of degrees of freedom to do this, and there's a simple algorithm to determine them. I don't know how to prove that there will always be a solution, though.

If you choose the $f(n,p,p′,X)$ additional bits that you set uniformly, then the bits of the resulting strings will have the right uniform distribution conditional on the total number of bits set, so all you have to get right to get the entire distribution right is the binomial distribution of the total number of bits set. That's $n$ conditions ($n+1$ minus one for normalization), and you have $n$ degrees of freedom on $f$ (again, $n+1$ minus one for normalization).

Let $a_k=\binom nkp^k(1-p)^{n-k}$ denote the original distribution of the number of set bits, let $b_k\stackrel{!}{=}\binom nkp'^k(1-p')^{n-k}$ denote the target distribution, and let $f_k=P(f(n,p,p',X)=k)$ denote the probability that you decide to set $k$ additional uniformly randomly chosen bits.

To choose the $f_k$, you need to start at the bottom: The only way to get $0$ bits in the result is to set $0$ additional bits, so we need $a_0f_0=b_0$, which yields $f_0=b_0/a_0$ (which is certain to yield a valid probability because $b_0\lt a_0$).

Now we can write an equation for $f_1$ such that we get $b_1$ right: $f_0a_1+f_1(a_0+a_1/n)=b_1$. That is, we end up with one bit set either by starting with zero and adding one, or by starting with one and adding zero, or by starting with one and setting one but accidentally setting the one that was already set. Thus

$$ f_1=\frac{b_1-f_0a_1}{a_0+a_1/n}=\frac{b_1-b_0a_1/a_0}{a_0+a_1/n}\;. $$

You can keep going like this until you've determined all the $f_k$. There may be a systematic way to do this, but even if there isn't, it's straightforward to write a program that carries out the calculations. My guess would be that there will always be a solution, but I'm not sure.

P.S.:

Here's the general equation to get $b_k$ right by choosing $f_k$:

$$ \sum_{i=0}^kf_i\sum_{j=0}^ia_{k-j}\frac{\binom{n-k+j}j\binom{k-j}{i-j}}{\binom ni}=b_k\;. $$

P.P.S.:

Here's Java code to compute the coefficients. In all the cases I tried, the $f_k$ came out as proper probabilities in $[0,1]$, so it seems that this should generally work.

Answer 2

If you have a generator with $p=\frac 12$ that is optimal in that it gives you the most information per bit. I don't see anything special about having $p \approx p'$. You can think of an $n$ bit string as being an approximation to an (infinite precision) real number between $0$ and $1$. You multiply the real by $2^n$ and truncate the result. If you read the bit string as a binary number $k$ you know that the real was in $[k \cdot 2^{-n},(k+1)2^{-n})$

We can use this real to generate a bit string with each bit having probability $p'$ of being set. We can't guarantee how long the bit string will be. If $k\cdot 2^{-n} \gt p'$ the first bit is $1$. If $(k+1)\cdot 2^{-n} \lt p'$ the first bit is $0$. If neither of these is true we are uncertain about the first bit and give up. If the bit was $1$ we subtract $p'$ from our real and multiply by $\frac 1{1-p'}$. If the bit was $0$ we multiply by $\frac 1{p'}$ We again check if the bottom of the range is above $p'$ and output a $1$ and if the top of the range is below $p'$ and output a $0$. At each step the uncertainty interval grows. Eventually it will include $p'$ and we can't produce any more bits.