Probability of getting a correct Bit

I have a probability problem that goes like this: I want to sent a bit across a channel that has a certain error rate. The probability of getting a bit wrong is $$0.3$$, and so to increase the chances of sending a correct message, I resend the bit $$n$$ times, and the receiver interprets the bit as the most common bit in the sequence, so $$n$$ is odd.

The error rate is not independent though, if a bit is incorrect, the bit after that has a probability of being incorrect of $$0.7$$. My question is, what is the minimum $$n$$ (number of resent bits) that I need to send to guarantee a probability of getting the correct bit interpreted of $$0.9$$?

I can't seem to find a closed form solution for the general probability.

• I would start by finding the probability that a correct bit is followed by another correct bit Dec 5, 2023 at 0:32
• @Henry Re my pseudo-answer (i.e. long winded comment) [1] Do you think that as $~n~$ increases, the probability of success will go to (1/2) ? [2] Analytically, the unresolved issue seems to be, given $~n~$ signals sent, $~k~$ of which were good, and $~r~$ switch events, and letting $~C(n,k,r)~$ denote the number of ways that $~(n,k,r)~$ can occur, is there a closed form expression for $~C(n,k,r) ~?$ Dec 5, 2023 at 2:37
• The larger we make $n$ the further we will get from .7 accuracy let alone .9 accuracy. Once you have the first error the remaining bits as a whole have a probabiilty of less than .5 of being correct, so the longer the string the worse it gets. Dec 5, 2023 at 4:00

Answer: No amount of bits you send will guarantee a success probability of $$0.9$$.

Suppose we use $$n$$ bits. For each $$k\in \{1,\dots,n\}$$, let $$p_k$$ be the probability that the $$k^\text{th}$$ bit is wrong. This satisfies the following linear recurrence: $$p_{k+1}=0.3(1-p_k)+0.7p_k \qquad (k\ge 1) \\ p_1=0.7\hspace{4.9cm}$$ This is because, either the $$k^\text{th}$$ bit is correct, so that the $$(k+1)^\text{st}$$ bit is wrong with probability $$0.3$$, or the $$k^\text{th}$$ bit is wrong, so that the $$(k+1)^\text{st}$$ bit is wrong with probability $$0.7$$.

You can then solve this nonhomogenous linear recurrence to find that $$p_k= \frac{1+(0.4)^k}{2}$$ Note that, whenever $$k\ge 30$$ (say), $$p_k$$ is very nearly $$1/2$$. So, for all intents and purposes, the $$n$$ bits you are sending are literally just noise.

The bits get noisier as $$k$$ progresses from $$1$$ to $$n$$. Therefore, I guess the best strategy for deciphering the $$n$$ bits would be to just read the first bit, ignoring the remaining $$n-1$$ bits. This is because the first bit is the least noisy. The first bit is correct with probability $$0.7$$, the second with probability $$0.58$$, then only $$0.532$$ for the third, and so on.

However, such a strategy is not allowed for the problem. You stipulated that the receiver must go with the majority of the bits to decipher the message. Since most of the bits have a near $$50\%$$ chance of being both $$0$$ and $$1$$, for large $$n$$, the probability the receiver correctly decodes the message will be very close to $$50\%$$. This is much worse than the $$70\%$$ success rate from just reading the first bit.

• +1 : (also) : "You can then solve this nonhomogenous linear recurrence..." : It never occurred to me that you could obtain a closed form formula for $~p_k.~$ Can you recommend a (beginner's) textbook that discusses attacking recurrence equations? Alternatively, which specific branch of math is involved here, combinatorics, probability theory, or something else? Jan 11 at 23:04

This is not an answer. This is a long-winded comment.

I don't know if the problem can be solved analytically. I suspect, without knowing for sure that the problem can be solved by brute force, with computer assistance, simply by having the computer step $$~n~$$ through each element in $$~\{3,5,7,\cdots\},~$$ until you have success.

You can use the following as a guide to consider how to write the program for generic values of $$~n.~$$

Let No-Switch refer to the event where the current and previous bit are either both accurate or both in error. The probability of a No-Switch event is $$~(0.7).~$$

Let Switch refer to the event complementary to the No-Switch event. So, the probability of a Switch event is $$~(0.3).$$

Assume that $$~n = 5.~$$ To consider the transmission a success, you must have either $$~5, ~4,~$$ or $$~3~$$ good bits. From the problem constraint, it is as if the $$~0$$-th bit was good (but not sent).

By the way, it is unclear to me that a satisfactory $$~n~$$ exists. As $$~n~$$ increases in value, my intuition suggests (perhaps wrongly) that the importance of the $$~0$$-th bit being good will diminish. This suggests that as $$~n \to \infty,~$$ the probability of success goes to $$~(1/2).~$$ Again, I could easily be wrong here.

Let $$~p(k)~$$ denote the probability of $$~k~$$ good bits out of the $$~5~$$ bits sent.

Then $$~p(5)~$$ involves (in effect) $$~5~$$ consecutive No-Switch events, and so has a computation of

$$p(5) = (0.7)^5.$$

To compute $$~p(4)~$$ you have to examine the $$\displaystyle \binom{5}{1} = 5~$$ mutually exclusive ways that this can occur. $$~1~$$ of these ways (where the last bit sent is wrong) involve $$~4~$$ No-Switch events and $$~1~$$ Switch event.

The other $$~4~$$ ways involve $$~3~$$ No-Switch events and $$~2~$$ Switch events. Therefore,

$$p(4) = \left[~ 1 \times (0.7)^4 \times (0.3)^1 ~\right] + \left[~ 4 \times (0.7)^3 \times (0.3)^2 ~\right].$$

To compute $$~p(3)~$$ you have to examine the $$\displaystyle \binom{5}{2} = 10~$$ mutually exclusive ways that this can occur. These are illustrated as follows (1 = good bit, 0 = bad bit):

0 0 1 1 1 : 2 switches (re 0-th bit pretended good)
0 1 0 1 1 : 4 switches
0 1 1 0 1 : 4 switches
0 1 1 1 0 : 3 switches

1 0 0 1 1 : 2 switches
1 0 1 0 1 : 4 switches
1 0 1 1 0 : 3 switches

1 1 0 0 1 : 2 switches
1 1 0 1 0 : 3 switches

1 1 1 0 0 : 1 switch


4 Switch events : 3 ways
3 Switch events : 3 ways
2 Switch events : 3 ways
1 Switch event : 1 way

Therefore,

$$p(3) = \\ \left[~ 3 \times (0.7)^1 \times (0.3)^4 ~\right] \\ + \left[~ 3 \times (0.7)^2 \times (0.3)^3 ~\right] \\ + \left[~ 3 \times (0.7)^3 \times (0.3)^2 ~\right] \\ + \left[~ 1 \times (0.7)^4 \times (0.3)^1 ~\right].$$

You know that the unconditional probability of getting a bit wrong is $$0.3$$, so of getting it right is $$0.7$$. Presumably this is the case for each bit, including both the first bit and each later bit.

You also know that if a bit is incorrect, the bit after that has a probability of being incorrect of $$0.7$$ and so of being correct is $$0.3$$.

For these two statements to be consistent, if a bit is correct then the probability of the next bit being incorrect is $$\frac{0.3-0.3\times0.7}{0.7} =\frac{9}{70}\approx 0.12857$$ and of being correct is $$\frac{0.7-0.3\times0.7}{0.7}=\frac{61}{70}\approx 0.87143$$.

I do not see an easy way of doing the calculation analytically, but it is easy enough to use brute force. If you say $$f(n,k)$$ is the probability you have sent $$n$$ bits of which $$k$$ are good including the most recent one and $$g(n,k)$$ is the probability you have sent $$n$$ bits of which $$k$$ are good but not the most recent, you have $$f(n,k)=\frac{61}{70}f(n-1,k-1)+\frac3{10}g(n-1,k-1)$$ $$g(n,k)=\frac{9}{70}f(n-1,k)+\frac7{10}g(n-1,k)$$ and you start with $$f(1,k)=g(1,k)=0$$ except that $$f(1,1)=0.7$$ and $$g(1,0)=0.3$$ . Just carry on until you meet the $$0.9$$ criterion. For example in R:

n <- 1
f <- c(0,0.7)
g <- c(0.3,0)

while(n %% 2 == 0 | sum((f+g)[((n+1)/2+1):(n+1)]) < 0.9){
n <- n+1
fnew <- c(0,f*61/70 + g*3/10)
gnew <- c(f*9/70 + g*7/10, 0)
f <- fnew
g <- gnew
}

n
# 35


$$35$$ seems large, and if successive bits had been independent then the probability of the majority being good would have been 1 - pbinom(n/2,n,0.7) about $$0.99358$$ but with the dependency is sum((f+g)[((n+1)/2+1):(n+1)]) is $$0.905795$$ as required in the question.

We can check the $$0.7$$s and $$0.3$$ and illustrate the distribution of the number of good bits:

#checks
sum(f)             # should be 0.7 as probability last is good
# 0.7
sum(g)             # should be 0.3 as probability last is bad
# 0.3
sum((f+g)*(0:n)/n) # should be 0.7 as expected proportion good
# 0.7
plot(0:n,f+g)
abline(v=n/2)
abline(h=0)


• Thanks - I corrected the vote! Dec 5, 2023 at 21:51