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)