repeatedly XOR n-bit string - probability of getting all 1s

Question

Start with n-bits of all 0s

Each round, generate a n-bit string, delta, with probability of getting a 1 being p.

Output of the round is input XOR delta.

A success is when all n-bits are equal to 1.

Is there a closed-form solution for:

1. Probability it takes exactly k rounds for success
2. Probability of at least one success after k rounds

I wrote a computer program to simulate this.
And I can think of how to write a program to compute the probabilities exactly by pre-computing all the transition probabilities.

But is there a closed-form solution?

Answer 1

The case for exactly $n$ rounds:

Note that the bits are independent of one another and we can model each with a random variable following a Bernoulli distribution.

XOR-ing with a 1 will always cause a flip so the probability of a flip in each round is $p$. Assume that the input has $k_0$ zeros and $k_1$ ones then we're asking for $k_0$ of our random variables to "succeed" an even number of times and $k_1$ to "succeed" an odd number of times. Since the rounds are independent we can just use new random variables for each flip.

Okay let's start with the even case: after $n$ rounds we want to know the probability that the sum of $n$ iid Bernoulli random variables is even. This sum follows a $B(n,p)$ binomial distribution which has the probability mass function $$ P(X=k) = \binom{n}{k} p^k (1-p)^{n-k}. $$ We're now looking for the sum of the probabilities of all even numbers that are less than or equal to $n$. So assume that either $n=2N+1$ or $n=2N$ for some $N$ then $P(X=n)$ is given by $$ \sum_{i=0}^N \binom{n}{2i} p^{2i} (1-p)^{n-2i} $$ which we can work out (here's a proof Probability that binomial random variable is even) to equal $$ S_1(n) = \begin{cases} (p - \frac12)(1-2p)^{2N}+\frac12 & \text{ for odd } n \\ \frac12((2p-1)^{2N}+1) & \text{ for even } n \end{cases} = \frac{1+(1-2p)^n}{2}. $$

As noted above our bits are independent, so the probability of success after $n$ rounds for the $k_1$ ones is just $S_1(n)^{k_1}$.

We can similarly work out $S_0(n)$ by summing the probability function of the binomial distribution for all odd numbers up to $n$ - or we note that it's odd precisely when it's not even, such that $S_0(n) = 1 - S_1(n)$.

The total probability of success after $n$ rounds for input with $k_0$ zeros and $k_1$ ones then becomes $$S_1(n)^{k_1} S_0(n)^{k_0} = S_1(n)^{k_1} (1-S_1(n))^{k_0} = \left(\frac{1+(1-2p)^n}{2}\right)^{k_1} \left(\frac{1-(1-2p)^n}{2}\right)^{k_0}.$$

EDIT:

Some clarification about the basic setup and how even/odd come into it: the XOR of two bits corresponds to adding them (as integers) and taking the remainder after division by 2. This can be seen by considering all the possible 4 combinations of inputs and comparing the results. Using jargon this means we have an "isomorphism" (of "abelian/commutative groups"): the integers $0$ and $1$ play the same role with respect to addition modulo 2 as the logical states $0$ and $1$ (or true and false or whatever you want) with respect to the logical connective XOR. As long as what we're doing cares only about the relative roles with respect to this structure we can freely move from one viewpoint to the other.

The other central property we use is that this "group of integers modulo 2" plays quite nicely with the regular integers in that "finding the sum of (a bunch of integers mod 2)" is the same as "(finding the sum of a bunch of integers) mod 2".

You start with some input bit $X_0$ that's either $0$ or $1$ and successively XOR it with random bits $X_1, X_2, ..., X_n$. This corresponds to starting with an integer $X_0'$ and adding the corresponding random integers $X_1', X_2',..., X_n'$ modulo 2. Denoting XOR by $\oplus$, finding the successive XORs of the bits corresponds to summing up the integers $X_1', ..., X_n'$ and taking the remainder mod 2: $$ (...((X_0 \oplus X_1) \oplus X_2) \oplus ... \oplus X_n) \simeq (X_0' + X_1' + ... + X_n') \mod 2. $$ We can split this right hand sum up like this: $$ (X_0' \mod 2) + \left(\sum_{i=1}^n X_i' \right) \mod 2 $$ and we want it to equal $1$ for your success state: $$ (X_0' \mod 2) + \left(\sum_{i=1}^n X_i' \right) \mod 2 = 1. $$ Here $X_0' \mod 2$ is $0$ if $X_0'$ is even (because $2k \mod 2 = k (2 \mod 2) \mod 2 = k \cdot 0 \mod 2 = 0$) and $1$ if $X_0'$ if it's odd (can be shown analogously) - and the converse holds as well (if an integer mod 2 is 0 then it's even etc.). But if $X_0' \mod 2 = 0$ then we're really asking for the probability that $$ \left(\sum_{i=1}^n X_i' \right) \mod 2 = 1 $$ which is equivalent to asking that $\sum_{i=1}^n X_i'$ is odd. Similarly we find the case that $X_0' = 1$ to correspond to $\sum_{i=1}^n X_i'$ being even.

Answer 2

This doesn't give a closed form for the probabilities, but it does give an alternate way of computing for any fixed $n$:

Note that if the process succeeds on the next round, there is exactly one possible input $\delta$ that leads to this success. In particular, at the current step, each of the bits with a $1$ must have a zero of $\delta$ and each of the bits with a $0$ must have a $1$ of $\delta$.

Therefore, of the $2^n$ possibilities for $\delta$, exactly one leads to success. If the current state has $\ell$ $1$s and $n-\ell$ $0$s, then the probability of success is $p^{n-\ell}(1-p)^{\ell}$.

In general, this can be modeled as a Markov chain where the states are the number of $1$s in the current state. For a state with $\ell$ $1$s (where $\ell<n$), we can write down the probability of transitioning to a state with $m$ $1$'s as follows: $$ \sum_{i=0}^m\binom{\ell}{i}\binom{n-\ell}{m-i}p^{m+\ell-2i}(1-p)^{n-\ell-m+2i}, $$ where some of the binomials may be zero. The transition probabilities can be written in a matrix, and you can calculate many of your questions (for specific $k$ and $n$) using powers of that matrix.