1. See proof of \(\displaystyle\lim_{n\to\infty}(H_n-\ln n)=\gamma\)
  2. The probability of $a_k$ is given by:
    \(\displaystyle P(a_k=i)=\frac{\binom {i-1}{k-1}}{\binom nk}\)
    And therefore
    \(\displaystyle \begin{align}E[a_k^2]&=\sum_{i=k}^n\frac{\binom {i-1}{k-1}}{\binom nk}i^2=\frac 1{\binom nk}\sum_{i=k}^{n}ki\binom ik=\frac 1{\binom nk}\sum_{i=k}^{n}\left(k(k+1)\binom {i+1}{k+1}-k\binom ik\right)\\&=\frac1{\binom nk}\left(k(k+1)\binom {n+2}{k+2}-k\binom {n+1}{k+1}\right)\\ &=\frac{k(k+1)(n+k+nk)}{(k+1)(k+2)} \end{align}\)
    And hence
    \(\sigma(a_k)=\sqrt{\frac{k(k+1)(n+k+nk)}{(k+1)(k+2)}-\frac {k^2(n+1)^2}{(k+1)^2}}=\frac 1{k+1}\sqrt{\frac{k(k-n)(k^2+(k+2)nk+k-1)}{k+2}}\)
  3. Fisher-Yates Shuffle
  4. $F$ is whether the coin is faulty, $H$ is heads. We are given:
    • Unbiased coin: $P(H=1|F=0)=P(H=0|F=0)=1/2$
    • Biased coin: $P(H=1|F=1)=1,P(H=0|F=1)=0$
    • Now
      $P(F=1|H=0)=\frac{P(H=0|F=1)P(F=1)}{P(H=0)}=\frac{0\cdot P(F=1)}{P(H=0)}=0$
    • And:
      $P(F=1|H=1)=\frac{P(H=1|F=1)P(F=1)}{P(H=1|F=1)P(F=1)+P(H=1|F=0)P(F=0)}=\frac{P(F=1)}{P(F=1)+(1/2)P(F=0)}$
      Assuming $P(F=1)=P(F=0)=1/2$ we get $\frac{1/2}{1/2+1/4}=\frac 23$.
  5. $C$ student has cheated, $G$ student held guilty, we are given:
    • If a student cheats, the software might declare the student honest with a probability of 0.8
      $P(G=0|C=1)=0.8\implies P(G=1|C=1)=0.2$
    • If a student has not cheated, the software might hold the student guilty with a probability of 0.0001.
      $P(G=1|C=0)=0.0001\implies P(G=1|C=0)=0.9999$
    • 10% of the students in the class actually cheated in the mid semester exams.
      $P(C=1)=0.1\implies P(C=0)=0.9$
    • Now we have:
      \(P(G=1)=P(G=1|C=0)P(C=0)+P(G=1|C=1)P(C=1)\\=0.0001\cdot 0.9+0.2\cdot 0.1\\=0.02009\) \(P(C=1|G=1)=\frac{P(G=1|C=1)P(C=1)}{P(G=1)}=\frac{0.2\cdot 0.1}{0.02009}\approx 99.95\%\)
  6. Examples:
  7. Every subset $\displaystyle {x_1,x_2…x_k}$ has an attached probability:
    \(\displaystyle \left(\frac12\right)^{k}\left(1-\frac 12\right)^{n-k}=\frac 1{2^n}\)
    • (i) $S$ is partitioned by 3 sets - $X$, $Y\setminus X$, $S\setminus Y$ hence $(3/4)^n$
    • (ii) symmetric - $(3/4)^n$
    • (iii) $S$ is partitioned by 2 sets - $X=Y$ and $S\setminus X=S\setminus Y$ hence $(1/2)^n$
    • (iv) $S$ is partitioned by 3 sets $X\setminus Y$, $Y\setminus X$ and $X\cap Y$ hence $(3/4)^n$
  8. Case a: We perform an enumeration:
    • 3 X’s: $8$ positions
    • 4 X’s: $8\times6=48$ positions (In each of the above $\binom 61$ can become a X)
    • 5 X’s: First we count where only one line is formed. For horizontal and vertical, this can be done by adding 2 X to 3 X’s such that they do not create a line, i.e. in $\binom 62 -3=12$ and for diagonal $\binom 62-7=8$, so total $6\times 12+2\times 8=88$. Now when two lines can be formed, it will be $3\times3$ for horizontal and vertical, $1$ for both diagonals, hence total $88+10=98$.
    • 6 X’s: Leave any three blocks empty $\binom 93=84$ minus two where these three lie on the diagonal, hence $82$
    • 7 X’s: Leave any two blocks empty $\binom 92=36$.
    • 8 X’s: Leave every block with circle each time $9$.
    • 9 X’s: All blocks: $1$.
    • Total: $8+48+98+82+36+9+1=282$ hence $282/512=141/256$, Note that in the below enumeration, both can win $21/64$ which is also counted here, giving: $99/256+21/128=141/256$
    • We get the following (where $X$ is 1 if crosses win and $Y$ is 1 if circles win): \(P_{X,Y}(x,y)=\begin{cases} \frac{1}{16}&x=0,y=0\\ \frac{99}{256}&x=0,y=1\\ \frac{99}{256}&x=1,y=0\\ \frac{21}{128}&x=1,y=1 \end{cases}\)\

    Case b: We perform an enumeration:

    • TODO (Manual calculation is quite tedious)
  9. \[\frac {70000}{100000}\frac {999}{1000}+\frac {30000}{100000}\frac{1}{1000}=\frac{1749}{2500}\approx 69.96\%\]
  10. Let her win $k$ rounds and loose $n-k$ rounds then:
    \(P=k\cdot 1+(n-k)\cdot (-1)=2k-n>0\implies k>n/2\)
    Now the expected number of steps to get positive profit: (TODO, Possibly not taught yet)