problem set

Problem 2

How many time do we need to toss to estimate the fairness of a coin?

Checking whether a coin is fair

Problem 1

The expectation times of sampling to get a number twice from a discrete uniform distribution $U(1,n)$.

$$% <![CDATA[ begin{eqnarray} P(X = x | n) &=& frac{x}{n} frac{prod_{i=0}^{x-1} (n-i)}{n^x}, quad x = 1, 2, dots, n \ P(X = x | n) &=& frac{x}{n} frac{n-x+1}{x-1} P(x - 1 | n) \ end{eqnarray} %]]>$$

$P(X = x)$ denotes the probability that $S = {s_1, ..., s_x}$ are distinct numbers, and $s_{x+1} in S$.

Solution

Expectation:

$$% <![CDATA[ begin{eqnarray} E_n &=& 0 \ E_{n-1} &=& frac{1}{n}(1 + E_n) \ E_{n-2} &=& frac{2}{n}(1 + E_{n-1}) \ E_{i} &=& frac{n-i}{n}(1 + E_{i+1}) \ E(X) = E_{0} &=& frac{n}{n}(1 + E_{1}) \ end{eqnarray} %]]>$$
$$% <![CDATA[ begin{eqnarray} E(X) + 1 &=& frac{sum_{i=0}^{n} frac{n!}{i!}n^i}{n^n} \ &=& e^n n^{-n}Gamma(n+1,n) \ end{eqnarray} %]]>$$

where

$$% <![CDATA[ begin{eqnarray} Gamma(s,x) &=& int_x^infty t^{s-1}e^{-t} dt \ &=& (s-1)!e^{-x}sum_{k=0}^{s-1} frac{x^k}{k!} \ end{eqnarray} %]]>$$

Variance:

$$mathrm{Var}(X) = mathrm{E}(X^2) - (mathrm{E}X)^2$$

I don’t find a good way to calculate it yet.

$$% <![CDATA[ begin{eqnarray} mathrm{E}(10) = 3.660215680,& quad &mathrm{Var}(10) = 2.942605496\ mathrm{E}(100) = 12.20996063,& quad &mathrm{Var}(100) = 38.70690078\ mathrm{E}(200) = 17.39844386,& quad &mathrm{Var}(200) = 79.89570756\ mathrm{E}(10000) = 124.9991219,& quad &mathrm{Var}(10000) = 4250.220410\ end{eqnarray} %]]>$$
$$% <![CDATA[ begin{eqnarray} P(X le 94 | N = 1000) &>& 0.99 \ P(X le 302 | N = 10000) &>& 0.99 \ end{eqnarray} %]]>$$

pr[x_,n_] := x * Product[(n-i), {i, 0, x - 1}] / n^(x+1)

en1[n_] := Sum[i * pr[i, n], {i, 1, n}]

ens1[n_] := Sum[i * i * pr[i, n], {i, 1, n}]


prlist[n_] := NestList[{#[[1]] + 1, (#[[1]] + 1) / n * (n - #[[1]]) / #[[1]] * #[[2]]} &, {1, 1/n}, n - 1]

en2[n_] := Total[Apply[Times, prlist[n], {1}]]

ens2[n_] := Total[Apply[Function[{a,b}, a*a*b], prlist[n], {1}]]


en[n_] := (E/n)^n * Gamma[n+1,n] - 1

varn[n_] := ens2[n] - en[n]^2

N[en[10], 10]

N[en[100], 10]

N[en[200], 10]

N[varn[10], 10]

N[varn[100], 10]

N[varn[200], 10]

cdf[n_,p_] := 
  Catch[
    Fold[
      Function[{s, x}, Print[{x[[1]],N[x[[2]] + s]}];
        If[x[[2]] + s >= p, 
           Throw[x[[1]]], 
           s + x[[2]]]], 
      0, prlist[n]]]
           
cdf[1000, 0.99]

Problem 0

Sample $m$ numbers ${x_1, dots, x_m}$ without replacement from ${1, dots, n+m}$. Let $X = x_1 + dots + x_m$. Find $mathrm{E}(X)$ and $mathrm{Var}(X)$.

Solution

$$% <![CDATA[ begin{eqnarray} mathrm{E}(X) &=& frac{m}{n} sum_{i=1}^{n+m} i \ &=& m(m+n+1)/2 \ mathrm{E}(X^2) &=& frac{m}{n+m} sum_{i=1}^{n+m} i^2 + frac{m(m-1)}{(n+m)(n+m-1)} sum_{i=1}^{n+m-1}sum_{j=i+1}^{n+m} 2ij \ mathrm{Var}(X) &=& mathrm{E}(X^2) - (mathrm{E}(X))^2\ &=& nm(n+m+1)/12 \ end{eqnarray} %]]>$$

en := m/(n+m) * Sum[i, {i,1,n+m}]

ens := m/(n+m) * Sum[i^2, {i, 1, n+m}] + m(m-1)/((m+n)(n+m-1)) * Sum[Sum[2*i*j, {j, i+1, n+m}], {i,1,n+m-1}]

varn := Simplify[ens - en^2]