Intro to Probability - FAQ Week 4

Question

Show that $\sum _{j=0}^\infty x^j=\frac{1}{1-x}$ for $|x|<1$.

Notice first that $$ (1-x)\sum_{j=1}^nx^j=(1-x)(1+x+\dots+x^n)=(1+x+\dots+x^n)-(x+x^2+\dots x^{n+1})= 1-x^{n+1} $$ for any $x\in\mathbb{R}$. This clearly gives that $$ \sum_{j=1}^nx^j=\frac{1-x^{n+1}}{1-x}\text{ for }x\in \mathbb{R}. $$ Letting $n$ go to infinity $$ \sum_{j=1}^\infty x^j=\lim _{n\to\infty}\sum _{j=1}^n x^j= \lim _{n\to\infty}\frac{1-x^{n+1}}{1-x}=\frac{1}{1-x} $$ for $|x|<1$ since $x^{n+1}\to 0$ as $n\to\infty$ for such $|x|<1$.

Question

For $n=1,2,3,...$ and $k\leq n$, let $T_n(k)$ denote the number of ways in which the set $N_n=\{1,2,\dots,n\}$ can be partitioned into $k$ subsets $S_1,\dots,S_k$. Partitioned means that the sets are non-empty, pairwise disjoint and satisfy $\bigcup_{j=1}^kS_j=N_n$ . Argue that it must hold that $$ T_n(k)=T_{n-1}(k-1)+k\, T_{n-1}(k) $$

A partition of $N_n$ will be such that it either contains the set $S=\{n\}$ or it wil not contain it. So, if we account for all partitions for which, say $S_1=\{n\}$, and for all those for which $S_j\neq\{ n\}$ for all $j=1,\dots,k$, then we we all accounted for all possible partitions.

Partitions of the first type will correspond to partitions of $N_{n-1}$ into $k-1$ subsets (consisting of $S_2,\dots,S_k$) for a total of $T_{n-1}(k-1)$.

Partitions of the second kind will be such that $n\in S_j$ for some $j\in\{1,\dots,k\}$ and that $S_j\neq\{ n\}$. The latter implies that, removing $n$ from $S_j$ still leaves us with a non-empty set. Now $$ S_1,\dots, S_{j-1},S_j\setminus\{ n\},S_{j+1},\dots, S_k $$ is a partition of $N_{n-1}$. This means that there are $k\,T_{n-1}(k)$ of the second type. You can also think of this as follows: any partition into $k$ subsets of $N_{n-1}$ will give us a partition of the second kind for $N_n$ by simply choosing one of the sets in the partition ($k$ choices) and placing $n$ in that set.

Question

Why is it that $$ \frac{1}{2}-\frac{1}{3!}+\frac{1}{4!}-\dots+\frac{(-1)^n}{n!}= \sum_{j=0}^n \frac{(-1)^j}{j!}\simeq \frac{1}{e} $$ for $n$ large?

The exponential function is defined by $$ e^x=\sum _{j=0}^\infty \frac{x^j}{j!}=\lim_{n\to\infty}\sum_{j=0}^n \frac{x^j}{j!}, $$ which means that $$ \sum_{j=0}^n\frac{x^j}{j!}\simeq e^x $$ for large $n$. Taking $x=-1$ we get $$ \frac{1}{e}=e^{-1}=1-1+\frac{1}{2}-\frac{1}{3!}+\frac{1}{4!}\mp\dots $$ as stated in Lecture 4.

Question

When considering a sequence of $n$ independent experiments which have success probability $p$, why is the probability of observing exactly $k$ successes given by ${n\choose k}p^k(1-p)^{n-k}$?

Consider first the event $E$ that the $k$ successes occur in the first $k$ experiments. Let $S_j$, $F_j$ denote the event of having a success or a failure in experiment $j(=1,\dots,n)$, respectively. Then $$ E=S_1\cap\cdots\cap S_k\cap F_{k+1}\cap\cdots\cap F_n. $$ Independence then yields $$ P(E)=P(S_1\cap\cdots\cap S_k\cap F_{k+1}\cap\cdots\cap F_n)= P(S_1)P(S_2)\cdots P(S_k)P(F_{k+1})\cdots P(F_n)=p^k(1-p)^{n-k}. $$ Finally observe that the $k$ successes can actually happen in any $k$ of the $n$ experiments for a total ${n\choose k}$ different possibilities which all contribute the above probability to the probability of having exactly $k$ successes and lead to $$ P(``\text{exactly }k\text{ successes}")={n\choose k}p^k(1-p)^{n-k}. $$

Question

Consider a biased coin for which heads comes up with probability $p\in(0,1)$. Try to find a way to use the coin in a way as to simulate the outcome of a fair coin.

Continue to flip the coin two times until the outcome is not two heads nor two tails and stipulate that player A wins if heads occurs first in the pair, while B wins if heads occurs on the pair's second flip. Why does this yield a fair game?
The probabilties to flip heads followed by tails or tails followed by head are both $p(1-p)$. Thus the probability for either player to win is $$ \frac{p(1-p)}{2p(1-p)}=\frac{1}{2}. $$ In a more formal way, let $E$ be the event that the first of a pair of tosses yields heads and $F$ the event that the pair of flips yields heads and tails in any order. Then the probability of A winning is given by $$ P(E|F)=\frac{P(E\cap F)}{P(F)}=\frac{p(1-p)}{2p(1-p)}=\frac{1}{2}. $$