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).