3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I would start by finding the probability that a correct bit is followed by another correct bit $\endgroup$
    – Henry
    Dec 5, 2023 at 0:32
  • $\begingroup$ @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) ~?$ $\endgroup$ Dec 5, 2023 at 2:37
  • 1
    $\begingroup$ 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. $\endgroup$ Dec 5, 2023 at 4:00

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ +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? $\endgroup$ Jan 11 at 23:04
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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)

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Thanks - I corrected the vote! $\endgroup$ Dec 5, 2023 at 21:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .