ELEC 321

# Tutorial 3

Updated 2017-09-29

## Expected Value and Variance

Given a random variable $X_i$, $\mathbb E(X_i)=\mu_i$ and $\text{Var}(X_i)=\sigma^2$

The weights can be described as

$W_n=a_1 x_1+ a_2 x_2+\dots+a_nx_n$

so

$\mathbb E(W_n)=\mathbb E(a_1x_1+\dots a_nx_n)=a_1\mu_1+\dots+a_n\mu_n$

and

$\text{Var}(W_n)=a_1^2\sigma_1^2+\dots+a^2_n\sigma_n^2$

Consider

$X_i$ are independent, $\mathbb E(X_i)=\mu$, and $\text{Var}(X_i)=\sigma^2$

$S_n=x_1+\dots+x_n$

Thus $\mathbb E(S_n)=n\mu$ and $\text{Var}(S_n)=\sigma_1^2+\dots+\sigma_n^2$.

If $\bar{X_n}=\frac{X_1+\dots+X_n}{n}$. then $\mathbb E(\bar{X_n})=\frac{n\mu}{n}=\mu$, and $\text{Var}(\bar{X_n})=\frac{1}{n}\sigma^2=\frac{\sigma^2}{n}$.

## Chebyshev Inequality

We want to prove the following inequality:

$\mathbb P(\vert X-\mu\vert \geq\epsilon)\leq\frac{\sigma^2}{\epsilon^2}$

Proof:

\begin{aligned} \sigma=\int_{-\infty}^{\infty}(x-\mu)^2f(x)\mathrm dx&\geq\int_{\vert x-\mu\vert \geq\epsilon}(x-\mu)^2f(x)\mathrm dx\\ &\geq\epsilon^2\int_{\vert x-\mu\vert \geq\epsilon}f(x)\mathrm dx = \epsilon^2\mathbb P(\vert X-\mu\vert \geq\epsilon) \end{aligned}

Consider previous example:

$\mathbb P(\vert \bar{X_n}-\mu\vert \geq\epsilon)\leq\frac{\frac{\sigma^2}{n}}{\epsilon^2}=\frac{\sigma^2}{n\epsilon^2}$

Example: Simple coin toss

$X_i(\omega)=\begin{cases} 1:\qquad\omega\in H\\ 0:\qquad\omega\notin H \end{cases}$

Examining the expected values we get

$\mathbb E(X_i)=(0)\mathbb P(H^c)+(1)\mathbb P(H)=\mathbb P(H)$

So

$\bar{X_i}=\mathbb P(H)$

The MATLAB code for this experiment is

clear
p = rand(1);

N = 1000;
S = zeros(1, N+1)
X_bar = zeros(1, N+1)
for n = 1:N
X_n = rand(1) < p;
S(n + 1) = S(n) + X_i;
X_bar(n + 1) = S(n + 1) / n;
end


Over time, X_bar will converge to a value since p is a random number

## Problem Set A

### A.12

For a majority decoding algorithm, if majority of the ($2N+1$) transmitted identical digits are received correctly, then the received digit is considered correctly decoded. Let $X$ be the number of errors in the transmission of the ($2N+1$) transmitted identical digits, and $p$ as the probability that each of the ($2N+1$) bits can be decoded correctly on its own. Assume that the errors in each of the ($2N+1$) positions are independent of each other.

So if the transmitted bits are 000, for the receiving bits to be 010, the probability is $(p)(1-p)(p)=p^2(1-p)$

(a) If $N=2, p=0.8$, what is the probability that one transmitted bit using majority decoding algorithm is decoded correctly?

Total bits are $2(2)+1=5$ bits, so if there is at least 3 changed, it cannot be decoded correctly.

Then we can say the probability of 3 bits unchanged is

${5 \choose 3}(1-p)^2p^3$

Which is the binomial random variable formula / distribution:

${n\choose k}(p)^k(1-p)^{n-k}$

So the probability of decoding correctly is

$\mathbb P(C)=\sum_{k=N+1}^{2N+1}{2N+1\choose k}p^k(1-p)^{2N+1-k}$

Plugging the number in, we get $0.942$

(b) If we only want use 3 identical bits in the majority decoding algorithm, what is the minimum $p$ required to have a better performance compared to (a)?

(c) If we use 7 identical bits, repeat (b).