2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ A very simple case is $p+p'=1$ where you can just invert all the bits. $\endgroup$ – Ross Millikan Jun 24 '18 at 18:38
  • $\begingroup$ @RossMillikan - ah yes, if only my case were so simple. In practice $p'$ is arbitrary in my use case. The underlying motivation is that we have some very fast generators of bit strings for various fixed $p$, but since we actually want a string with some arbitrary probability that doesn't correspond to any of the fixed generators, I would like to select a "nearby" p and then adjust it to get to p'. The adjustment turned out not be as trivial as I'd hoped. $\endgroup$ – BeeOnRope Jun 24 '18 at 18:45
  • $\begingroup$ Do you need to change a relatively small number of bits, or is it acceptable to take in the $n$ bits with probability $p$ and output a string of $n$ bits with probability $p'$ but with no detectable relationship between the strings? Is it acceptable if the output string is slightly shorter than the input string? $\endgroup$ – Ross Millikan Jun 24 '18 at 19:28
  • $\begingroup$ @RossMillikan - yes, I expect that a relatively small number of bits need to be changed, i.e., that $p$ and $p'$ are generally quite close (within 0.01 or even 0.001). So simply implementing an $f$ that essentially overwrites the original string doesn't make sense here: the goal is to do a limited number of "fixups" to the the original string, since generating the original string is cheap, and each fixup relatively expensive. I suppose the output string could be smaller than the input string, since I could scale up $n$ a bit to make sure it is usually longer and then truncate it ... $\endgroup$ – BeeOnRope Jun 24 '18 at 20:07
  • $\begingroup$ ... and in the case it still ended up smaller than desired, generate another short string to fill in the missing bits. That said, the details are important: "removing" bits from the middle of the string isn't going to be cheap. $\endgroup$ – BeeOnRope Jun 24 '18 at 20:08
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I'm hoping there is a closed form calculation for the $f_k$ or at least some way to efficiently sample that distribution over $k$ since otherwise you'll end up doing $n$ such calculations since $k$ runs all the way to $n$. I guess what I could do, however, is to calculate ahead of time all the $f_k$ for some small(ish) value like 1000 and adjust the input string in segments of 1000. In this way, the cost doesn't depend on $n$ anymore. Does it introduce any bias or problem? $\endgroup$ – BeeOnRope Jun 24 '18 at 21:02
  • 1
    $\begingroup$ @BeeOnRope: Yes, it would just be $\sum_{i=0}^kf_ia_{k-i}=b_k$ then. I'm working on a simulation to check which (if either) of the two methods admits a solution. $\endgroup$ – joriki Jun 24 '18 at 21:32
  • 1
    $\begingroup$ @BeeOnRope: Actually, that won't work because there might not be enough zero bits to set. Then you'd have to say "set $k$ zero bits if there are enough, else fewer", and that would make things complicated again. I guess if you're increasing $p$ from $0.5$ to $0.501$ for $n=1000$, this would never happen in practice, so you could work with the simpler equations for practical purposes. Anyway, the good news is, I added code to the answer to calculate the probabilities, and in all the cases I tried they came out in $[0,1]$. $\endgroup$ – joriki Jun 24 '18 at 22:06
  • 1
    $\begingroup$ @BeeOnRope: I tried out the simplified formula, ignoring the complications, and as you suspected, it fails right away -- e.g. for $p=0.5$, $p=0.51$, $n=20$ it already yields $f_0+f_1\gt1$ before even getting close to the region with appreciable probability for not having enough zero bits. The original formula, on the other hand, seems to produce nice probability distributions, with a peek where one would expect it, around $k=\frac{p'-p}{1-p}n$. $\endgroup$ – joriki Jun 24 '18 at 22:37
  • 1
    $\begingroup$ Thank you very much, this is awesome and the original/complicated answer still serves a great purpose as a "backup proof" - i.e., a backup to the intuitive description you have at the top of the answer. I'll add a comment here if I use this (with attribution) somewhere interesting. $\endgroup$ – BeeOnRope Jun 24 '18 at 23:28
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sure, I am aware of this approach for generating biased bit strings using more or less the minimum amount of input entropy, but it is very slow. That's why I want to take a string that is close enough (the $p$ string) and change a small number ($O(n*(p' - p))$) of bits to get the new string. Maybe I need to formulate my question better (suggestions welcome) - but note the restriction on not using the input string as an input to the algorithm - the above clearly does. Thanks anyways for your answer. $\endgroup$ – BeeOnRope Jun 24 '18 at 20:19

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.