10

A message consists of 100 bits (either 0 or 1), of which every bit can change (from 0 to 1 or the other way around) during the data transfer with probability p = 0,001 (independently of other bits). What is the probability that a message is in its original form after 10 data transfers?

Is my reasoning correct here (my answer): In order to calculate the probability that a message is in its original form after 10 data transfers we first have to calculate the probability of one bit being transferred correctly and then do that for the next 100 bits to lastly calculate the probability of doing this 9 more times (10 total).

so: P(X=100) = (1-p)^100 = (0.999)^100 and for 10 total transfers we get P(X=10) = ((1-p)^100)^10 == (0.999)^1000 ~= 0.3677 so the probability that the message is received in its original form is 0.3677 (~36.8%)

Noolenne
  • 103
  • Calculate the probability all bits are uncorrupted, i.e., $0.999^{100}$. – David G. Stork Jul 05 '23 at 17:20
  • 2
    What do you mean by "P(X=100) " ? – leonbloy Jul 05 '23 at 17:23
  • 6
    Bear in mind that if, say, the first bit changes in the first transfer but it changes again in the second transfer, then it gets ok.... (if I understand it right) – leonbloy Jul 05 '23 at 17:24
  • @leonbloy so theres 100 bits right, so i calculate the probability of one bit getting corrupted and then take that to the power of number of bits (100 in this case) which i assume is the correct way of doing it.

    im not sure how to take into account that if one bit changes in one transfer it could get "fixed" in any of the other answers.

    – Noolenne Jul 05 '23 at 18:06
  • since the question is phrased a bit weird im not sure if the point is to take into account what you're asking @leonbloy.

    but i guess having an answer for both would be nice. The question is from a statistical compendium i've been using to learn probabilities

    – Noolenne Jul 05 '23 at 18:56
  • Have you quoted the exact question ? – true blue anil Jul 05 '23 at 18:59
  • Yes, i have. its directly written from the compendium. – Noolenne Jul 05 '23 at 19:05

3 Answers3

15

If this is meant to be practical question, where a good approximation is sufficient, then yes your computation is good! However, it is not the exact answer.

As leonbloy pointed out, the case where all the bits are always transferred correctly isn't the only way for the message to be the same at the end. Let's think about a simpler case, with only one bit and four transfers. Let's say the bit starts as a $1$, and let's write "F" when it flips during a transfer, and "N" when nothing happens. Here are a few examples of possible scenarios :

\begin{align*} 1 \underset{N}{\longrightarrow} 1 \underset{N}{\longrightarrow} 1 \underset{N}{\longrightarrow} 1 \underset{N}{\longrightarrow} 1 \\ \\ 1 \underset{N}{\longrightarrow} 1 \underset{F}{\longrightarrow} 0 \underset{N}{\longrightarrow} 0 \underset{N}{\longrightarrow} 0 \\ \\ 1 \underset{F}{\longrightarrow} 0 \underset{N}{\longrightarrow} 0 \underset{N}{\longrightarrow} 0 \underset{F}{\longrightarrow} 1 \\ \\ 1 \underset{F}{\longrightarrow} 0 \underset{N}{\longrightarrow} 0 \underset{F}{\longrightarrow} 1 \underset{F}{\longrightarrow} 0 \\ \\ 1 \underset{F}{\longrightarrow} 0 \underset{F}{\longrightarrow} 1 \underset{F}{\longrightarrow} 0 \underset{F}{\longrightarrow} 1 \end{align*}

As you can see, there's actually many ways for the bit to be the same at the beginning and at the end. It's hard to imagine because it seems unlikely that a large message would coincidentally have the right flips to still be preserved, but it is still a non-negligible part of it.

Thinking about it, you might notice that the bit stays preserved whenever there's an even number of flips happening, so that a flip is always cancelled out by another flip. In our simple case, the probability that this happens is : $$ \mathbb{P}(\text{"preserved"}) = \mathbb{P}(\text{"0 flips" or "2 flips" or "4 flips"}), $$ and since those events are all disjoint : $$ \mathbb{P}(\text{"preserved"}) = \mathbb{P}(\text{"0 flips"}) + \mathbb{P}(\text{"2 flips"}) + \mathbb{P}(\text{"4 flips"}). $$ The number of flips follows a binomial distribution, and so : $$ \mathbb{P}(\text{"preserved"}) = \binom{4}{0}(1-p)^4 + \binom{4}{2}p^2(1-p)^2 + \binom{4}{4}p^4 \approx 0.996, $$ which is $0.006$ higher than just the probability of no flips happening.

Let's generalize even more by considering $T\in\mathbb{N}$ transfers. Now, the probability that a random number following a binomial distribution is even is actually given by the simple formula : $$ \mathbb{P}(\text{"preserved"}) = \mathbb{P}(\text{"even number of flips"}) = \frac{1}{2}(1+(1-2p)^T). $$ Several proofs of this expression are given here, as well as this answer I really like.

Let's further consider a message made up of $n$ bits. Since the bits are independent of each other, the probability that the whole message gets preserved is : $$ \mathbb{P}(\text{"n bits are preserved"}) =\mathbb{P}(\text{"1 bit is preserved"})^n = \left(\frac{1+(1-2p)^T}{2}\right)^n. $$ Plugging in our values, $T=10$, $p=0.001$, and $n=100$, we get : $$ \mathbb{P}(\text{"n bits are preserved"}) \approx 0.369357 $$ which is just about a $0.16$% difference from the no-flips case. Not a whole lot in practice, but notice that over a very large number of transfers $T$, the probability of the message being preserved would approach $1/2^n$, whereas the probability of no flips at all would approach $0$. Quite different!

Willow Wisp
  • 1,153
  • "would approach 2**(-n)" -> which is the probability of random noise matching the message, and therefore seems very reasonable – Ben Voigt Jul 06 '23 at 16:01
8

Going by the wording of the question, we only want the final and original messages to match

thus each bit must either remain uncorrupted throughout or switch an even number of times, so taking $p=0.999, q = 0.001$,

P(a bit remains unchanged at the end)

$= p^{10} + \binom{10}{2}p^8q^2 + \binom{10}{4}p^6q^4 + \binom{10}{6}p^4q^6 + \binom{10}{8}p^2q^8 +\binom{10}{10}q^{10}$, which comes to $0.99009$

Thus P("message is in its original form after 10 data transfers") $= 0.99009^{100}, \approx 36.94 \%$

8

To add to the other answers:

The numbers involved here lead to some approximations that simplify the computation:

  1. It's true that the event that a bit is received unaltered includes the events that there happened zero, two, four, etc changes. But, because the single alteration is quite improbable ($p = 0.001$), the first case (no alteration) dominates, hence the probability is approximately $(1-p)^{10}$

  2. Under the above approximation, the probability that all bits are received as the original is $[(1-p)^{10}]^{100}=(1-p)^{1000}$

Again, because the exponent is big, we can approximate $(1-x/n)^{n} \approx e^{-x}$ hence

$$\left(1- \frac{1000 \cdot p}{1000}\right)^{1000} \approx e^{- 1000 \cdot p} = e^{-1}\approx 0.368$$

leonbloy
  • 63,430