# Probability to get the correct message

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!

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$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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
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}$$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

#### mathmari

##### Well-known member
MHB Site Helper
Great!!

At (b) we want that all symbols are transmitted correctly, so the probability is then equal to $p^r$, or not?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

#### mathmari

##### Well-known member
MHB Site Helper
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.
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}$ ?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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}$?

#### mathmari

##### Well-known member
MHB Site Helper
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}$?
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
$\displaystyle{\left (\sum_{i=k}^r\binom{r}{i}p^i(1-p)^{r-i}\right )^n}$.

Is that correct?
Yep.

#### mathmari

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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}$?

#### mathmari

##### Well-known member
MHB Site Helper
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}$?
Ahh because we miss the equality

#### mathmari

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

MHB Site Helper