SGT Sheet

Question 1

1. Calculate expectation and variance of each dice: Dice $X$: $E[X]={\sum }_{k}k\cdot p_x(k)=\frac{1}{6}+\frac{4}{6}+\frac{6}{6}+\frac{4}{6}=2.5$ $E[X^2]={\sum }_{k}k\cdot p_x(k{)}^2=\frac{1}{6}+\frac{8}{6}+\frac{18}{6}+\frac{16}{6}=\frac{43}{6}$ $\text{Var}[X]=\frac{43}{6}-2.5^2=\frac{11}{12}$

   Dice $Y$: $E[Y]={\sum }_{k}k\cdot p_y(k)=\frac{1+3+4+5+6+8}{6}=4.5$ $E[Y^2]={\sum }_{k}k\cdot p_y(k{)}^2=\frac{1+3^2+4^2+5^2+6^2+8^2}{6}=\frac{151}{6}$ $\text{Var}[Y]=\frac{151}{6}-4.5^2=\frac{59}{12}$

2. Calculate p.m.f. for their sum $X+Y$:

   1 & 2 & 4 & 5 & 6 & 7 & 9 \\ 2 & 3 & 5 & 6 & 7 & 8 & 10 \\ 3 & 4 & 6 & 7 & 8 & 9 & 11 \\ 4 & 5 & 7 & 8 & 9 & 10 & 12 \\\end{matrix}$$ | $k$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ | $11$ | $12$ | | ------------ | --- | --- | --- | --- | --- | --- | --- | --- | ---- | ---- | ---- | | $p_(x+y)(k)$ | $\frac{1}{36}$ | $\frac{2}{36}$ | $\frac{3}{36}$ | $\frac{4}{36}$ |$\frac{5}{36}$ | $\frac{6}{36}$ | $\frac{5}{36}$ | $\frac{4}{36}$ |$\frac{3}{36}$ | $\frac{1}{36}$ | $\frac{1}{36}$ |

3. Verify that $E[X+Y]=E[X]+E[Y]$ for this pair of dice. Find $E[X+Y]$ from the new p.m.f.:

   $7$ in the p.m.f. so we know that it is $7$.

   There is symmetry over

   Or otherwise: $E[X+Y]=\frac{2+3\cdot 2+4\cdot 3+5\cdot 4+\dots }{36}=7$ Hence, $E[X+Y]=E[X]+E[Y]$. As from earlier, $E[X]+E[Y]=2.5+4.5=7$

Question 2

1. Draw computational tree for $M$ on input $w=1111$:

2. Calculate probability that $M$ accepts $w$: $P(m(w)=1)=\frac{544}{625}$

3. Calculate expected termination time of $M$ on input $w$: (we add the probabilities of expected steps and then find expectation)

   $k$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
   $P_T(k)$	$0$	$\frac{2}{5}$	$0$	$\frac{6}{25}$	$\frac{81}{625}$	$\frac{18}{125}$	$0$	$\frac{54}{625}$

   $E[T]=2\cdot \frac{2}{5}+3\cdot \frac{6}{25}+4\cdot \frac{81}{625}+6\cdot \frac{18}{125}+8\cdot \frac{54}{625}=\frac{2477}{627}\approx 4$

Question 3

If run $5$ times:

1. What is probability that the algorithm returns correct answer all $5$ times? ${\left(\begin{array}{c}\frac{2}{3}\end{array}\right)}^5=\frac{32}{243}$
2. What is probability the algorithm returns correct answer more often than not? See 4-7. Four ways of selecting items. Either $3$, $4$, or $5$ are correct:
   • $3$ correct: ${\frac{2}{3}}^3\cdot {\frac{1}{3}}^2\cdot \left(\begin{array}{c}5\\ 2\end{array}\right)=\frac{80}{243}$
   • $4$ correct: ${\frac{2}{3}}^4\cdot \frac{1}{3}\cdot \left(\begin{array}{c}5\\ 1\end{array}\right)=\frac{80}{243}$ The probability is: $\frac{32+80+80}{243}=\frac{64}{81}\approx 79\%$
3. Design a poly-time Monte Carlo algorithm that has a probability of returning correct answer at least 90% of the time. Recommendation is to write a script for brute force.

   There is a mathematical proof that will be released on solutions.