Tutorial 3

Updated 2017-09-29

Expected Value and Variance
Chebyshev Inequality
Problem Set A
- A.12

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\]

\[\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:

Let’s start with definition of variance for continuous random variable:

\[\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)?