Conditional expectation of discrete random variables: Practice

For every integer \(k\) we can calculate \(\mathbb E\left[\left.Y\right|X=k\right]\). First we fix \(k\). Conditioned on \(\{X=k\}\) the number \(Y\) is drawn uniformly at random from \(\{1,2,\dots, k\}\). The probabilities of the events \(\{Y=1\}\), \(\{Y=2\}\), \(\dots\), \(\{Y=k\}\) are all equal to \(\frac1k\). Therefore the expected value of \(Y\) conditioned on \(\{X=k\}\) is equal to \[\mathbb E\left[\left.Y\right|X=k\right] = \frac1k\left(1+2+\cdots+k\right)=\frac{\frac{k(k+1)}2}k=\frac{k+1}2. \] Therefore \(\mathbb E\left[\left.Y\right|X\right]=\frac{X+1}2\).

We will use that the events \(\{X=1\}\), \(\{X=2\}\), \(\{X=3\}\) are disjoint and that their union has probability \(1\). Therefore \begin{eqnarray*} \mathbb E\left[Y\right]&=&\sum_{i=1}^{\infty}\mathbb E\left[\left.Y\right|X=i\right]\cdot\mathbb P\left(X=i\right). \end{eqnarray*} From the previous problem we know that \(\mathbb E\left[\left.Y\right|X=i\right]=\frac{i+1}2\). We know that \(X\) is geometric random variable with parameter \(p=\frac16\). Its probability mass function is \(f_X(i)=\frac16\cdot \left(\frac56\right)^{i-1}\). Therefore \begin{eqnarray*} \mathbb E\left[Y\right]&=&\sum_{i=1}^{\infty}\frac{i+1}2\cdot f_X(i)= \sum_{i=1}^{\infty}\frac{i+1}2\cdot f_X(i)=\mathbb E\left[\frac{X+1}2\right]= \frac{\mathbb E[X]+1}2=\frac{\frac1{\frac16}+1}{2}=\frac72. \end{eqnarray*} We used that the expectation of a geometric random variable with probability \(p\) is \(\frac1p\) which implies that the expectation of \(X\) is \(6\).

Thus we obtained that the expectation of \(Y\) is \(\frac72\).

Let us denote by \(N\) the random variable that represents the number of throws until the obtained number is \(6\). Let us denote by \(A\) the event that no odd number occurs before the first number \(6\). We need to calculate \(\mathbb E\left[\left.N\right|A\right]\). The conditional expectation can be written in the following form \begin{eqnarray*} \mathbb E\left[\left. N\right|A\right]&=&\sum_{k=1}^{\infty}k\mathbb P\left(\left.N=k\right|A\right). \end{eqnarray*} The definition of conditional probability implies \[\mathbb P\left(\left. N=k\right|A\right)=\frac{\mathbb P\left(\{N=k\}\cap A\right)}{\mathbb P\left(A\right)}.\] Consider now the event \(\{N=k\}\cap A\). This is the event that \(6\) appears for the first time at the \(k\)-th throw and only even numbers are thrown in the first \(k-1\) attempts. The probability that a throw results in an even number different from \(6\) is \(\frac13\). The probability that all of the first \(k-1\) throws result in even numbers different from \(6\) is \(\left(\frac13\right)^{k-1}\) hence \[\mathbb P\left(\{N=k\}\cap A\right)=\frac1{3^{k-1}}\cdot\frac16.\] The probability of the event \(A\) can be calculated in the following way \begin{eqnarray*} \mathbb P\left(A\right)&=&\sum_{k=1}^{\infty}\mathbb P\left(\{N=k\}\cap A\right)=\sum_{k=1}^{\infty}\frac16\cdot\frac1{3^{k-1}}\newline &=&\frac16\cdot \sum_{k=1}^{\infty}\frac1{3^{k-1}}=\frac16\cdot \frac1{1-\frac13}=\frac14. \end{eqnarray*} Therefore the required conditional expectation is \begin{eqnarray*} \mathbb E\left[\left. N\right|A\right]&=&\sum_{k=1}^{\infty}k\cdot \frac{\frac1{3^{k-1}}\cdot\frac16}{\frac14}\newline &=&\frac23\sum_{k=1}^{\infty}k\cdot \frac1{3^{k-1}}. \end{eqnarray*} The sum \(\sum_{k=1}^{\infty}kx^{k-1}\) can be calculated as \begin{eqnarray*}\sum_{k=1}^{\infty}kx^{k-1} &=&\left(\sum_{k=1}^{\infty}x^k\right)^{\prime}=\left(\frac{x}{1-x}\right)^{\prime}\newline &=&\frac1{(1-x)^2}.\end{eqnarray*} Therefore \[\mathbb E\left[\left. N\right|A\right]=\frac23\cdot \frac1{\left(\frac23\right)^2}=\frac32.\]

Let us denote by \(A_n\) the random variable that represents the number of dominoes that are placed on the \(1\times n\) board. Let us denote \(\alpha_n=\mathbb E\left[A_n\right]\). Clearly, \(\alpha_0=\alpha_1=0\) and \(\alpha_2=2\). We will now make a recursive equation for the sequence \(\left(\alpha_n\right)_{n=0}^{\infty}\). For each \(i\in\left\{1,2,\dots, n-1\right\}\) denote by \(B_i\) the event that the first domino is placed to occupy the squares \(i\) and \(i+1\). The probability of each event \(B_i\) is equal to \(\frac1{n-1}\). We now have for \(n\geq 3\) \begin{eqnarray*} \alpha_n&=&\mathbb E\left[A_n\right]=\mathbb E\left[\left. A_n\right|B_0\right]\cdot\mathbb P\left(B_0\right)+\mathbb E\left[\left. A_n\right|B_1\right]\cdot\mathbb P\left(B_1\right)+\cdots+\mathbb E\left[\left. A_n\right|B_{n-1}\right]\cdot\mathbb P\left(B_{n-1}\right)\newline &=&\frac1{n-1}\left(\mathbb E\left[\left.A_n\right|B_1\right]+\mathbb E\left[\left.A_n\right|B_2\right]+\cdots+\mathbb E\left[\left.A_n\right|B_{n-1}\right]\right). \end{eqnarray*} If the domino is placed on cells \(i\) and \(i+1\) on \(1\times n\) board the remaining cells form one \(1\times(i-1)\) board to the left of the domino and one \(1\times(n-i-1)\) board to the right of the domino. We conclude that \[\mathbb E\left[\left.A_n\right|B_i\right]=2+\alpha_{i-1}+\alpha_{n-i-1}.\] Therefore for \(n\geq 3\) we have \begin{eqnarray*} \alpha_n&=&2+\frac1{n-1}\left(\left(\alpha_0+\alpha_{n-2}\right)+\left(\alpha_1+\alpha_{n-3}\right)+\cdots+\left(\alpha_{n-2}+\alpha_0\right)\right) \newline &=&2+\frac2{n-1}\left(\alpha_0+\alpha_1+\cdots+\alpha_{n-2}\right). \end{eqnarray*} The last equation can be written in an equivalent form \[(n-1)\alpha_n=2(n-1)+2\left(\alpha_0+\alpha_1+\cdots+\alpha_{n-2}\right).\]

Let us define the function \(F(x)\) in the following way: \begin{eqnarray*} F(x)&=&\sum_{n=0}^{\infty}\alpha_nx^n=\sum_{n=2}^{\infty}\alpha_nx^n. \end{eqnarray*} The last equation holds because \(\alpha_1=\alpha_0=0\). Let us define \(G(x)=\frac{F(x)}x\). The derivative of the function \(G\) satisfies \begin{eqnarray*} G^{\prime}(x)&=&\left(\sum_{n=2}^{\infty}\alpha_nx^{n-1}\right)^{\prime}=\sum_{n=2}^{\infty}(n-1)\alpha_nx^{n-2}\newline &=&2\sum_{n=2}^{\infty}(n-1)x^{n-2}+2\sum_{n=2}^{\infty} \left(\alpha_0+\alpha_1+\cdots+\alpha_{n-2}\right)x^{n-2}\newline &=&2\left(x+x^2+x^3+\cdots\right)^{\prime}+2\sum_{m=0}^{\infty} \left(\alpha_0+\alpha_1+\cdots+\alpha_{m}\right)x^m. \end{eqnarray*} The first sum is equal to \(\frac{x}{1-x}=\frac{x-1}{1-x}+\frac1{1-x}\). Its derivative is \(\frac1{(1-x)^2}\). Therefore \begin{eqnarray*} G^{\prime}(x)&=&\frac2{(1-x)^2}+2\alpha_0\left(x^0+x^1+x^2+\cdots\right)+2\alpha_1\left(x^1+x^2+x^3+\cdots\right)+\cdots \newline &=&\frac2{(1-x)^2}+\frac{2\alpha_0}{1-x}+\frac{2\alpha_1x}{1-x}+\frac{2\alpha_2x^2}{1-x}\cdots\newline &=&\frac2{(1-x)^2}+2\frac{F(x)}{1-x}\newline &=&\frac2{(1-x)^2}+2\frac{xG(x)}{1-x}. \end{eqnarray*} Therefore the function \(G\) satisfies the following differential equation \[G^{\prime}(x)-\frac{2x}{1-x}G(x)=\frac{2}{(1-x)^2}.\] We will multiply both left and right side of the equation with \(e^{M(x)}\) where \(M\) is the anti-derivative of \(\frac{-2x}{1-x}\). It is easy to obtain that \[M(x)=-2\int\frac{x}{1-x}\,dx=2x+2\ln|1-x|+C,\] where \(C\) is a real constant. We may choose \(C=0\) and multiply both sides of differential equation with \(e^{M(x)}=e^{2x}\cdot (1-x)^2\). The equation becomes \[\left((1-x)^2e^{2x}G(x)\right)^{\prime}=2e^{2x}.\] The last equation implies that \[G(x)=\frac1{(1-x)^2}+D\frac{e^{-2x}}{(1-x)^2},\] where \(D\) is a real number. We will determine the real number \(D\) from the requirement that \(G(0)=0\). This implies that \(D=-1\). Therefore \begin{eqnarray*}F(x)&=&xG(x)=\frac{x}{(1-x)^2}-\frac{xe^{-2x}}{(1-x)^2}. \end{eqnarray*} We will now find the Taylor expansion of \(F(x)\) around \(0\). The Taylor expansion of \(\frac x{(1-x)^2}\) around \(x=0\) is \[\frac x{(1-x)^2}= x\cdot \left(\frac1{(1-x)}\right)^{\prime}=x\sum_{i=1}^{\infty}ix^{i-1}=\sum_{n=1}^{\infty}nx^n.\] The Taylor expansion of \(e^{-2x}\) around \(0\) is \[e^{-2x}=\sum_{n=0}^{\infty}\frac{(-2)^n}{n!}x^n.\] Therefore the Taylor expansion of \(F\) is \begin{eqnarray*} F(x)&=&\sum_{n=0}^{\infty}\left(n-\sum_{i=0}^ni\cdot \frac{(-2)^{n-i}}{(n-i)!}\right)x^n, \end{eqnarray*} which implies that for \(n\geq 3\) the following holds \begin{eqnarray*} \alpha_n&=&n-\sum_{i=0}^ni\cdot \frac{(-2)^{n-i}}{(n-i)!}=-\sum_{i=1}^{n-1}i\frac{(-2)^{n-i}}{(n-i)!}. \end{eqnarray*} With the substitution \(j=n-i\) the last summation transforms into \begin{eqnarray*} \alpha_n&=&-\sum_{i=1}^{n-1}i\frac{(-2)^{n-i}}{(n-i)!}=-\sum_{j=1}^{n-1}(n-j)\frac{(-2)^j}{j!}\newline &=&-\sum_{j=1}^{n-1}n\frac{(-2)^j}{j!}+\sum_{j=1}^{n-1} j\frac{(-2)^j}{j!}\newline &=&-n\sum_{j=1}^{n-1}\frac{(-2)^j}{j!}+\sum_{j=1}^{n-1} \frac{(-2)^j}{(j-1)!}\newline &=&n-n\sum_{j=0}^{n-1}\frac{(-2)^j}{j!}-2\sum_{j=1}^{n-1} \frac{(-2)^{j-1}}{(j-1)!}\newline &=&n-n\sum_{j=0}^{n-2}\frac{(-2)^j}{j!}-2\sum_{j=0}^{n-2} \frac{(-2)^{j}}{j!}-n\frac{(-2)^{n-1}}{(n-1)!}\newline &=&n-(n+2)\sum_{j=0}^{n-2}\frac{(-2)^j}{j!}-n\frac{(-2)^{n-1}}{(n-1)!}. \end{eqnarray*}

We can now calculate the required limit \(\lim_{n\to\infty}\frac{\alpha_n}{n}\). We will use that \(\sum_{j=0}^{\infty}\frac{(-2)^j}{j!}=e^{-2}\). As a consequence of convergence of the series, we know that the terms must converge to \(0\). Therefore \(\lim_{j\to\infty}\frac{(-2)^j}{j!}=0\). Therefore \begin{eqnarray*} \lim_{n\to\infty}\frac{\alpha_n}n&=&1-\lim_{n\to\infty}\left(1+\frac2n\right)\cdot\sum_{j=0}^{n-2}\frac{(-2)^j}{j!}-\lim_{n\to\infty}\frac{(-2)^{n-1}}{(n-1)!}\newline &=&1-\lim_{n\to\infty}\left(1+\frac2n\right)\cdot \sum_{j=0}^{\infty}\frac{(-2)^j}{j!}-0\newline &=&1-e^{-2}. \end{eqnarray*}