PROB_ClassAssignments

Vasudeva S N

Polya Urn Scheme

Question

An urn contains $r$ red balls and $b$ blue balls. One ball is selected at random and $c$ balls of the same colour are added into the urn. Prove that the chance of picking a red ball at any draw remains the same.

Let $P(R_n)$ denote the probability of picking a red ball in the $n$th draw.
Let $S_n$ be the statement: For $r,g\ge 1$, if there were initially $r$ red and $g$ green balls, $P(R_n)=\frac{r}{r+g}$.

$S_1$ is easily seen to be true. Next, for $n>1$, assume $S_k$ is true for all $k\le n$. Then,

$$\begin{array}{r}P(R_n)=P(R_n|R_1)P(R_1)+P(R_n|B_1)P(B_1)\end{array}$$

Now, $P(R_n|R_1)$ is equal to the probability of picking a red ball in the $n-1$th draw if there were initially $r+c$ and $b$ red balls and blue balls respectively. Since $S_{n-1}$ is true, $P(R_n|R_1)=\frac{r+c}{r+b+c}$. Similarly, $P(R_n|B_1)=\frac{r}{r+b+c}$. So,

$$\begin{array}{rl}P(R_n)& =\frac{r+c}{r+b+c}\frac{r}{r+b}+\frac{r}{r+b+c}\frac{b}{r+b}\\ & =\frac{r}{r+b}\end{array}$$

Hence proved.

Proof of Inclusion exclusion in probability

Theorem 1(The inclusion-exclusion principle).

Let $A_1,A_2,\dots ,A_n\in \mathcal{F}$ for some $(\Omega ,\mathcal{F},P)$. Define

$$S_1=\sum _{i=1}^{n}P(A_i)$$ $$S_2=\sum _{1\le i<j\le n}P(A_i\cap A_j)$$ $$S_3=\sum _{1\le i<j<k\le n}P(A_i\cap A_j\cap A_k)$$ $$⋮$$

Then,

$$P\left(\bigcup _{i=1}^n{A}_i\right)=S_1-S_2+S_3-\cdots +(-1{)}^{n+1}{S}_n$$

Easy to verify for $n=2,3$. For general $n$, assume the principle is proved for all $k<n$. Let $B_i=A_i$ for all $1\le i\le n-2$, and $B_{n-1}=A_{n-1}\cup A_n$Then,

$$\begin{array}{rl}& P\left(\bigcup _{i=1}^n{A}_i\right)=P\left(\bigcup _{i=1}^{n-1}{B}_i\right)\\ & =\sum _{i}P(A_i)-P(A_n\cap A_{n-1})\\ & -\sum _{\genfrac{}{}{0ex}{}{i\ne j}{\{i,j\}\ne \{n,n-1\}}}P(A_i\cap A_j)+\sum _{i}P(A_i\cap A_n\cap A_{n-1})\\ & ⋮\\ & \pm \left(P\left(A_{n-1}\cap \bigcap _{i=1}^{n-2}{A}_i\right)+P\left(A_n\cap \bigcap _{i=1}^{n-2}{A}_i\right)\right)\mp P\left(\bigcap _{i=1}^n{A}_n\right)\\ & =S_1-S_2+S_3-\cdots +(-1{)}^{n+1}{S}_n\end{array}$$

Bonferroni’s Inequalities

Let $A_1,\dots ,A_n$ be events in a probability space. Denote ${\bigcup }_{i=1}^n{A}_i$ by $A$. We want to prove that

$$\begin{array}{rl}& P\left(A\right)\le S_1-S_2+\cdots +S_i,\text{where }i\text{ is odd, and}\\ & P\left(A\right)\ge S_1-S_2+\cdots -S_i,\text{where }i\text{ is even.}\end{array}$$

Let $\omega \in \Omega$. Fix $i$. If $\omega \notin A$, then $\omega$ is counted $0$ times in the LHS and the RHS. Let $\omega$ be a member of $r$ sets from $A_1,\dots ,A_r$. $\omega$ is counted exactly once in the LHS. In the RHS, $\omega$ is counted

$$\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\cdots =\sum _{j=1}^i(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{r}{j})$$

times. Now, if $i=r$, the sum is just $1-(1-1{)}^r=1$. If $i<r$, we know that

$$\sum _{j=1}^i(-1{)}^{j+1}(\genfrac{}{}{0ex}{}{r}{j})=1+(-1{)}^{i+1}\left(\genfrac{}{}{0ex}{}{r-1}{i}\right)$$

This quantity is greater than 1 when $i$ is odd, and less than 1 when $i$ is even. Hence, $\omega$ gets counted less than 1 times if $i$ is odd, and more than 1 times if $i$ is even. This completes the proof.

Properties of conditional expectation

$E(aY+Z|X)=aE(Y|X)+E(Z|X)$

$$\begin{array}{rl}& E(aY+Z|X)\\ & =\sum _{y,z}(ay+z)P(Y=y,Z=z|X=x)\\ & =a\sum _{y}yP(Y=y|X=x)+\sum _{z}zP(Z=z|X=x)\\ & =aE(Y|X)+E(Z|X)\end{array}$$

$Y\ge 0,E(Y|X)\ge 0$

$$\begin{array}{r}E(Y|X=x)=\sum _{y}yP(Y=y|X=x)\end{array}$$

Since each term in the sum is positive, $E(Y|X=x)$ and hence $E(Y|X)$ is positive.

$E(g(X)Y|X)=g(X)E(Y|X)$

$$\begin{array}{rl}& E(g(X)Y|X=x)\\ & =\sum _{y}g(x)yP(Y=y|X=x)\\ & =g(x)\sum _{y}yP(Y=y|Z=x)\\ & =g(x)E(Y|X=x)\end{array}$$

$E(c|X)=c$

$$\begin{array}{r}E(c|X=x)=cP(c=c|X=x)=c\end{array}$$

$E(E(Y|X,Z)|X)=E(Y|X)=E(E(Y|X)|X,Z)$

$$\begin{array}{rl}& \\ & E(E(Y|X,Z)|X=x)\\ & =\sum _{z}E(Y|X=x,Z=z)P(Z=z|X=x)\\ & =\frac{1}{P(X=x)}\sum _z\sum _{y}yP(Y=y|X=x,Z=z)P(Z=z,X=x)\\ & =\frac{1}{P(X=x)}\sum _{y}y\sum _{z}P(Y=y,X=x,Z=z)\\ & =\sum _{y}y\frac{P(Y=y,X=x)}{P(X=x)}\\ & =\sum _{y}yP(Y=y|X=x)\\ & =E(Y|X=x)\end{array}$$ $$\begin{array}{rlr}& E(E(Y|X)|X=x,Z=z)& \\ & =E(Y|X)E(1|X=x,Z=z)& E(Y|X)\text{ is a function of }X\\ & =E(Y|X)& \end{array}$$