Welcome to our community

Be a part of something great, join today!

Probability to get the correct message

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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$. 🤔
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:

 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440
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:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,162
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)
 

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,440