# 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:

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:

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

Example: Simple coin tossExamining 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).