0
$\begingroup$

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?

Can someone please answer these and/(or preferably) explain the reasoning to answer such questions?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – ruakh
    Mar 10, 2022 at 6:52
  • $\begingroup$ @ruakh: the problem statement is unclear, but it seems that OP loops only once. $\endgroup$
    – user16034
    Mar 10, 2022 at 8:05
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Mar 10, 2022 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.