# Simulating Bernoulli processes using several random binary strings

I recently stumbled upon a mathematical puzzle while trying to work with the limitations of a certain program. Said program effectively has the ability to simulate Bernoulli processes, but only at integer percentages. However, one can also perform bitwise logical operations between the resulting strings, which allows for somewhat finer control of the percentages: up to two extra digits per additional string. (For example, ANDing two independent 25% strings results in a 6.25% string.)

On the other hand, this process isn't perfect, as not all percentages with the right number of digits are covered, even allowing for all $2^{2^n}$ possible truth tables. For instance, for $P(A_k=1)=0.27$, $P(B_k=1)=0.34$, and $P(C_k=1)=0.29$, $P(((A_k\veebar B_k)\lor C_k)=1)=0.592744$, a fairly good (but not ideal) six-digit approximation to the square site percolation coefficient of $0.59274605079210(2)$ (according to this paper cited by Wikipedia).

However, from what I can tell, it is apparently not possible to get to $0.592746$ with just three independent processes; one apparently needs at least four. Has there been any work done on this kind of question, either about the minimum number of processes needed for a particular percentage, or what decimal percentages cannot be produced by the number of processes specified by the two-digits-per-process rule?

• Why the downvotes? What can I do to improve the question? – 404UserNotFound Dec 14 '15 at 21:16
• It's not entirely clear what the question is (it's not clear what phrases like "the resulting strings" refer to, for example) and it contains some irrelevant details - for instance, we don't really need to hear about the "square site percolation coefficient" if that's not part of the problem. Ideally you would have begun with something like "Let $B_n$ be independant bernouilli random variables whose probabilities are expressible as integer percentages..." and asked a specific mathematical question about them. As you noted under my answer, I wasn't quite able to understand what you were asking. – Jack M Dec 15 '15 at 22:07

If I understand what you're getting at, it can be reformulated in the following purely number-theoretic fashion.

Let $A$, $B$, and $C$ be integers between $-50$ and $50$, and consider the $8$ possible values

$$(50\pm A)(50\pm B)(50\pm C)$$

where the $\pm$ is chosen independently for each factor. Now add up any subset of these $8$ values. Of the $256$ possible sums, the smallest is $0$ (if the subset is empty) and the largest is $1000000$ (if you add up all $8$ values). What you're basically asking is for a characterization of the $6$-digit "target" numbers $N$ that can appear as one of these sums for some choice of $A$, $B$, and $C$. For example,

$$592744=(73\cdot34\cdot71)+(27\cdot66\cdot71)+(73\cdot66\cdot29)+(73\cdot34\cdot29)+(27\cdot66\cdot29)+(27\cdot34\cdot29)$$

where we've taken $A=23$, $B=16$, and $C=21$.

Given this reformulation, the specific question about the target number $N=592746$ can clearly be settled by an exhaustive search through $256\cdot101^3$ possibilities. Whether there is a simpler way to resolve it is not at all clear (to me, at least).

Remarks (added later): As the OP observes in comments, the symmetry between plus and minus allows one to restrict the exhaustive search to $0\le A,B,C\le50$. In fact, it's not necessary to go all the way to $50$, so the search space can be trimmed to size $256\cdot50^3=32{,}000{,}000$. Some target numbers, such as any $N$ that is the product of three two-digit numbers, are obviously achievable; the tricky question is identifying target numbers that are not achievable -- it would be nice to have a proof that $N=592746$ is not achievable (if indeed it isn't) that doesn't amount to saying "an exhaustive search failed to find it."

As far as I know there is no literature on this question. If you generalize it from $3$ integer variables $(A,B,C)$ to $n$, so your target numbers $N$ lies between $0$ and $100^n$, the exhaustive search generalizes to size $2^{2^n}\cdot50^n$, which grows extremely rapidly with $n$, so my offhand guess would be that for some not-very-large $n$, every $2n$-digit target number $N$ is achievable. (Actually, that's already trivially true for $n=1$, but it's probably not true for $n=2$. It's conceivable that "universal" achievability might come and go even for large $n$.)

• This is a correct rewording, although the exhaustive search can be trimmed down by two different methods: 1) Only 0 through 50 need to be examined, as the negatives are already covered by the plus-minus sign. 2) Since the target (in the case of 592746) is divisible by 2, and not by 4 or 5, one of A, B, and C must be even but not divisible by 4, and the other two must be odd; none of the numbers can be divisible by 5. (continues in next comment) – 404UserNotFound Dec 14 '15 at 23:21
• (continued from previous comment) However, now that I think about it, I made a (now obvious) error in reasoning of confusing the direction of implication, so that it's possible that A, B, and C are all odd in this case. (The proper direction of reasoning is unaffected; I only realized that it also allows for fewer factors than the final result contains, instead of just the same number, but it still can't contain more factors.) I shall do another search with only odd numbers and see if it changes. – 404UserNotFound Dec 14 '15 at 23:26
• Nope, there's still nothing for exactly 592746, although I did find two results for 592747: {1, 33, 41} and {23, 23, 43}; both truth tables contain five entries of 1. Also, don't forget to answer the question! – 404UserNotFound Dec 14 '15 at 23:41
• (extra comment added because I can't edit past five minutes) Realized that the numbers are in my formatting of a choice between p and (100-p); in your notation they would be {49, 17, 9} and {27, 27, 7}. – 404UserNotFound Dec 14 '15 at 23:55

If $X$ and $Y$ are two independant Bernoulli random variables with $P(X=1)=p$ and $P(Y=1)=q$, then $P((X\wedge Y)=1)=P(X=1 \wedge Y = 1)=pq$. Thus your questions, if I understand them correctly, reduce to some number theory questions:

1. What numbers can be written as a product of fractions of the form $\frac n {100}$, where $0\leq n \leq 100$?

2. How many such factors are necessary when this is possible?

• This is a good way of rephrasing things, with one slight exception: it only includes truth tables with only one possibility resulting in 1, and the rest resulting in 0. For instance, the example of 0.592744 given involves six of the eight possible truth table elements resulting in 1. (Or, more simply, the inverse of that truth table involves two elements.) – 404UserNotFound Dec 14 '15 at 21:37