# how many bits should I expect to flip, if I flip each bit with probability 1/n?

I am trying to work out some analysis for an algorithm I am trying to write, one step of what I am doing require knowing the answer to the above question.

I know it might sound a bit simple, but I am not sure of the approach (formally using probability theory).

Assume I have an algorithm that loops over a bitstring (x1,x2,x3...xn).

• If my loop decides at each iteration flip x_i with probability 1/n. How many bits should I expect to flip at the end?
• or an alternative way to see this: If I decide I want to flip k bits in my string and sample u.a.r the number the k integers between [1 and n] . what is the probability for a single bit X_i to be flipped?

Let $$X_i$$ be a random variable that equals $$1$$ if your algorithm flips the $$i$$-th bit and $$0$$ otherwise. Let $$X = \sum_{i=1}^n X_i$$ be the random variable counting the number of flipped bits. Your first question asks about $$\mathbb{E}[X]$$.

The expected value of a random variable is a linear function, therefore: \begin{align*} \mathbb{E}[X] &= \mathbb{E}\left[\sum_{i=1}^n X_i\right] = \sum_{i=1}^n\mathbb{E}\left[ X_i\right] = \sum_{i=1}^n \left(0 \cdot \Pr(X_i=0) + 1 \cdot \Pr(X_i=1)\right) \\&= \sum_{i=1}^n \Pr(X_i=1) = \sum_{i=1}^n \frac{1}{n} = 1. \end{align*}

Regarding the second question, since you say that you want to flip $$k$$ bits, I assume that you are sampling $$k \le n$$ elements from $$\{1, \dots, n\}$$ u.a.r. and without replacement. In that case the probability of flipping each bit is exactly $$\frac{k}{n}$$.

If you instead sample with replacement, fix some index $$i$$ and look at the probability of the event $$E_j$$ = "the $$j$$-th sample is not $$i$$". The probability of $$E_j$$ is $$\frac{n-1}{n}=1-\frac{1}{n}$$. Since the $$E_j$$s are independent, the probability of not sampling $$i$$ is the product of the probabilities of $$E_1, \dots, E_k$$, i.e.: $$\Pr\left(\bigcap_{j=1}^k E_j \right) = \prod_{j=1}^k \Pr(E_j) = \left( 1-\frac{1}{n} \right)^k.$$

Since you are interested in the complementary event, its probability is $$1-\left( 1-\frac{1}{n} \right)^k$$.

• Note that $1-\left( 1-\frac{1}{n} \right)^k$ is the probability of a given bit being chosen at least once in the sampling-with-replacement case. Depending on the situation, it may be more important to know the probability of a given bit being chosen an odd number of times (since flipping a bit an even number of times is equivalent to not flipping it at all), which is significantly more complicated. Mar 10, 2022 at 6:52
• @ruakh: the problem statement is unclear, but it seems that OP loops only once.
– user16034
Mar 10, 2022 at 8:05
• @ruakh. Good point. In that case the probability of flipping a fixed bit an odd number of times is $\sum_{i=1}^{\lceil k/2 \rceil} \binom{k}{2i-1} (\frac{1}{n})^{2i-1} (1-\frac{1}{n})^{k-2i+1} = \frac{1}{2} - \frac{1}{2}(1-\frac{2}{n})^k$. See also this answer. Mar 10, 2022 at 8:08