MHB Probability to get the correct message

  • Thread starter Thread starter mathmari
  • Start date Start date
  • Tags Tags
    Probability
AI Thread Summary
The discussion focuses on improving the reliability of digital communication through symbol repetition and majority decoding. The probability of correctly decoding a single symbol, sent multiple times, is determined by the formula involving binomial coefficients, specifically requiring at least a certain number of correct transmissions. For the entire message, the probability of all symbols being decoded correctly is calculated as the product of individual probabilities raised to the power of the number of symbols. Additionally, the probability of altering no more than a specified number of symbols is derived using binomial distribution principles. The conversation concludes with agreement on the equivalence of different probability formulations for altered symbols.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :giggle:

One of the techniques we are using at the digital communications to improve the reliability of a noisy communication channel, is to repeat a symbol many times.
For example, we can send each symbol $0$ or $1$ say three times. More precisely, applying the rule of majority, a $0$ (or $1$) is sent as $000$ (or $111$ respectively) and is decoded at the receiver with $0$ (or $1$) if and only if the received sequence of three symbols contains at least two $0$ (or $1$ respectively).

In this case we consider a message that is sent through a noisy communication channel and consists of $n$ symbols ($0$ or $1$). At the transmission each symbol can be altered (independent from the other ones) due to the noise. To increase the reliability of the transmission each symbol is repeated $r$ times. The probability of correct transmission of each symbol ($0$ or $1$) is $p$. Applying the rule of majority, a symbol $0$ (or $1$) is decoded correctly at the receiver if and only if the received sequence of $r$ symbols contains at least $k$ $\ 0$ (or $1$ respectively), with $k>\frac{r}{2}$.
Calculate:
(a) the probability a sent symbol to be decoded correctly.
(b) the probability the whole message to be decoded correctly.
(c) the probability to be altered not more than $x$ symbols of the message, with $x<n$.For (a) do we have to consider that at least $k$ symbols have to be decoded correctly with probability $p$ ? :unsure:
 
Physics news on Phys.org
Hey mathmari!

I think we should look at just $1$ symbol to be sent and to be decoded.
When we send $1$ symbol, we transmit that symbol $r$ times.
We want to know the probability that the decoded symbol is the same as the sent symbol.
That is the case if at least $k$ of the $r$ transmitted symbols are transmitted correctly, which happens with probability $p$. 🤔
 
Klaas van Aarsen said:
I think we should look at just $1$ symbol to be sent and to be decoded.
When we send $1$ symbol, we transmit that symbol $r$ times.
We want to know the probability that the decoded symbol is the same as the sent symbol.
That is the case if at least $k$ of the $r$ transmitted symbols are transmitted correctly, which happens with probability $p$. 🤔

Since each symbols independent from the other ones, if they will be altered or not, is the probability that at least $k$ symbols are transitted correctly equal to $$\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}$$ ? :unsure:
 
mathmari said:
Since each symbols independent from the other ones, if they will be altered or not, is the probability that at least $k$ symbols are transitted correctly equal to $$\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}$$ ?
Yep. (Nod)
 
Klaas van Aarsen said:
Yep. (Nod)

Great!

At (b) we want that all symbols are transmitted correctly, so the probability is then equal to $p^r$, or not? :unsure:
 
mathmari said:
At (b) we want that all symbols are transmitted correctly, so the probability is then equal to $p^r$, or not?
Isn't that the probability that each transmission of a $1$ symbol was received correctly?
I think (b) asks for the probability that $n$ symbols are sent and decoded correctly. :unsure:
 
Klaas van Aarsen said:
Isn't that the probability that each transmission of a $1$ symbol was received correctly?
I think (b) asks for the probability that $n$ symbols are sent and decoded correctly. :unsure:

Ahh so the probability that $1$ symbol was received correctly is $p^r$. Then is the probability that $n$ symbols are sent and decoded correctly equal to $\left (p^r\right )^n=p^{rn}$ ? :unsure:
 
mathmari said:
Ahh so the probability that $1$ symbol was received correctly is $p^r$. Then is the probability that $n$ symbols are sent and decoded correctly equal to $\left (p^r\right )^n=p^{rn}$ ?
Didn't you find in (a) that the probability that $1$ symbol was sent and decoded correctly was $\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}$? :unsure:
 
Klaas van Aarsen said:
Didn't you find in (a) that the probability that $1$ symbol was sent and decoded correctly was $\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}$? :unsure:

Ahh I was confused.. I thought that all symbols of the message have to be correctly transmitted, but for each symbol of the message it must be that at least $k$ symbols must be correct at the sequence, right?

The probability that one sent symbol is decoded correctly is equal to $\displaystyle{\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}}$.
We consider $n$ symbols of the message. So each of the $n$ symbols has the probability $\displaystyle{\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}}$ to be transimtted correctly. Since each symbol is independent from each other we take the product of the probabilities, i.e. $\displaystyle{\left (\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}\right )^n}$.

Is that correct? :unsure:

 
  • #10
mathmari said:
$\displaystyle{\left (\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}\right )^n}$.

Is that correct?
Yep. (Nod)
 
  • #11
Klaas van Aarsen said:
Yep. (Nod)

Great!

For (c) do we consider binomial distribution?

Let X be the number of symbols that are correctly transmitted.
Then we have that $$P(X\geq n−x)=1−P(X<n−x)=1−\sum_{m=0}^{n-x}\binom{n}{m}W^m(1-W)^{n-m}$$ where $W$ is the probability we calculated at (a).
And this probability is equal to the probability that not more than $x$ symbols of the message will be altered.

Is that correct? :unsure:
 
  • #12
mathmari said:
Let X be the number of symbols that are correctly transmitted.
Then we have that $$P(X\geq n−x)=1−P(X<n−x)=1−\sum_{m=0}^{n-x}\binom{n}{m}W^m(1-W)^{n-m}$$ where $W$ is the probability we calculated at (a).
And this probability is equal to the probability that not more than $x$ symbols of the message will be altered.
Binomial distribution sound good.

But don't we have $P(X<n−x)=P(X\le n−x-1)=\sum\limits_{m=0}^{n-x-1}\binom{n}{m}W^m(1-W)^{n-m}$? :unsure:
 
  • #13
Klaas van Aarsen said:
Binomial distribution sound good.

But don't we have $P(X<n−x)=P(X\le n−x-1)=\sum\limits_{m=0}^{n-x-1}\binom{n}{m}W^m(1-W)^{n-m}$? :unsure:

Ahh because we miss the equality :oops:
 
  • #14
But we could write it also as follows, or not?
$$ \sum\limits_{m=0}^{x}\binom{n}{m}W^{n-m}(1-W)^{m} $$ which is equal to the probability that at most $x$ from $n$ symbols are wrongly transmitted (altered), or isn't that equivalent to the formula above? :unsure:
 
  • #15
mathmari said:
But we could write it also as follows, or not?
$$ \sum\limits_{m=0}^{x}\binom{n}{m}W^{n-m}(1-W)^{m} $$ which is equal to the probability that at most $x$ from $n$ symbols are wrongly transmitted (altered), or isn't that equivalent to the formula above?
I believe that is equivalent yes. (Nod)
 
  • #16
Klaas van Aarsen said:
I believe that is equivalent yes. (Nod)

Great! Many thanks! (Malthe)
 
Back
Top