Probability to get the correct message

[mathmari]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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]

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:

 

[I like Serena]

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

Is that correct?

Yep. (Nod)

 

[mathmari]

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:

 

[I like Serena]

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]

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

 

[mathmari]

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:

 

[I like Serena]

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]

I believe that is equivalent yes. (Nod)

Great! Many thanks! (Malthe)