MTH 4120: Introduction to Probability
Denote by \(A_k\) the event that all of the first \(k\) outcomes are heads and by \(B_k\) the event that the \(k\)--th outcome is a head. We need to find \(\mathbb P \left(\left. B_{n+1}\right|A_n \right)\). Note that \(A_n \cap B_{n+1} = A_{n+1}\). Then, \begin{eqnarray} \mathbb P \left(\left. B_{n+1}\right|A_n\right) &=& \frac{\mathbb P\left(A_n\cap B_{n+1}\right)}{\mathbb P\left(A_n\right)} = \frac{\mathbb P\left(A_{n+1}\right)}{\mathbb P\left(A_n\right)}. \end{eqnarray} Denote by \(F\) the cumulative distribution function of the uniform \([0,1]\) random variable. We apply the law of total probability and condition on the random variable \(p\) that takes a uniform value in the interval \([0,1]\). We obtain that \begin{eqnarray} \mathbb P\left(A_n\right) &=& \int_0^1\mathbb P\left(\left.A_n\right|p=t\right)\,d F(t) - \int_0^1 t^n\,dt=\frac1{n+1}. \end{eqnarray} It follows that \[ \mathbb P\left(\left.B_{n+1}\right|A_n\right) ~=~ \frac{n+1}{n+2}. \]
Note that \(\sin x\geq 0\) for \(x\in [0,\pi]\). Assume that \(s\in[0,1]\) is fixed. Conditioned on \(\sin X=s\), the random variable can be either \(\arcsin X\) or \(\pi-\arcsin X\). The two possibilities are equally likely, and therefore the expectation is their arithmetic mean. We conclude that \[ E[X|\sin{X}] ~=~ \frac{\pi}2. \]
Observe that \(N\) is a positive integer-valued random variable. We will use problem 4 from homework 3 to express \(\mathbb E\left[N\right]\) as \begin{eqnarray*} \mathbb E\left[N\right]&=& \sum_{k=0}^{\infty}\mathbb P\left[N>k\right]=1+1+\sum_{k=2}^{\infty}\mathbb P\left[N>k\right]. \end{eqnarray*} We have used that \(\mathbb P\left[N > 0\right]=\mathbb P\left[N > 1\right]=1\). The event \(\{N > k\}\) means that the smallest integer \(i\) for which the sum \(X_1+\cdots+ X_i\) exceeds \(1\) is bigger than \(k\). This is equivalent to saying that the sum of the first \(k\) random variables \(X_1\), \(\dots\), \(X_k\) is not exceeding \(1\). Therefore the event \(\{N > k\}\) is the same as the event \[\{X_1+X_2+\cdots+ X_k\leq 1\}\] and, hence, their probabilities must be equal. We are able to conclude that \[\mathbb P\left[N > k\right]=\mathbb P\left[X_1+\cdots+X_k\leq 1\right].\] Since \(X_1\), \(X_2\), \(\dots\), \(X_k\) are independent and identically distributed uniform \([0,1]\) random variables, the last probability corresponds to the volume of the \(k\)-dimensional pyramid \begin{eqnarray*}x_1+x_2+\cdots +x_k\leq 1,\newline x_1\geq 0, \; x_2\geq 0, \dots,x_k\geq 0.\;\end{eqnarray*} We will use calculus to prove that this volume is equal to \(\frac1{k!}\), i.e. \begin{eqnarray} \mathbb P\left(X_1+\cdots+X_k\leq 1\right)=\frac1{k!}. \end{eqnarray} We will prove a slightly more general result that will be of use for other problems. For \(t\in[0,1]\) the following equality holds \begin{eqnarray} \mathbb P\left(X_1+\cdots+X_k\leq t\right)=\frac{t^k}{k!}. \quad\quad\quad\quad\quad\quad\quad(*) \end{eqnarray} One way to prove this result is to use standard induction on iterated integrals \begin{eqnarray*} \mathbb P\left[X_1+\cdots+X_k\leq t\right] &=& \int\int\cdots \int_{x_1+\cdots+x_k\leq t}\,dx_kdx_{k-1} \cdots dx_1=\int_0^t\int_0^{t-x_1}\int_0^{t-x_1-x_2}\cdots\int_0^{t-x_1-\cdots-x_{k-1}} \,dx_k\cdots dx_1. \end{eqnarray*} In order to make the upper bounds of the integrals aesthetically more pleasing, we will denote them by \(B_0\), \(B_1\), \(\dots\), \(B_{k-1}\), where \[B_{\ell}=t-x_1-\cdots-x_{\ell}.\] This notation enables us to write \begin{eqnarray*}\mathbb P\left[X_1+\cdots+X_k\leq t\right] &=&\int_0^{B_0}\int_0^{B_1}\int_0^{B_2}\cdots\int_0^{B_{k-1}} dx_k\cdots dx_1. \end{eqnarray*} The innermost integral satisfies \begin{eqnarray*} \int_0^{B_{k-1}}\,dx_k &=&B_{k-1}=\left(t-x_1-\cdots -x_{k-1}\right). \end{eqnarray*} We can now evaluate the innermost double integral \begin{eqnarray*} \int_0^{B_{k-2}}\int_0^{B_{k-1}}\,dx_k\,dx_{k-1} &=&\int_0^{B_{k-2}}\left(B_{k-2} -x_{k-1}\right)\,dx_{k-1}.\end{eqnarray*} The last integrand can be solved using the substitution \(u_{k-1}=B_{k-2}-x_{k-1}\). The integral becomes \begin{eqnarray*}\int_0^{B_{k-2}}\int_0^{B_{k-1}}\,dx_k\,dx_{k-1} &=&\int_0^{B_{k-2}}u_{k-1}\,du_{k-1}=\frac12B_{k-2}^2=\frac12\left(t-x_1-\cdots-x_{k-2}\right)^2=\frac12\left(B_{k-3}-x_{k-2}\right)^2. \end{eqnarray*} The innermost triple integral now becomes \begin{eqnarray*} \int_0^{B_{k-3}}\int_0^{B_{k-2}}\int_0^{B_{k-1}} \,dx_kdx_{k-1}dx_{k-3} &=&\frac12\int_0^{B_{k-3}}\left(B_{k-3} -x_{k-2}\right)^2\,dx_{k-2}.\end{eqnarray*} Using the substitution \(u_{k-2}=B_{k-3}-x_{k-2}\) in the last integral we obtain \begin{eqnarray*} \int_0^{B_{k-3}}\int_0^{B_{k-2}}\int_0^{B_{k-1}} \,dx_kdx_{k-1}dx_{k-3} &=&\frac12\int_0^{B_{k-3}}u_{k-2}^2\,du_{k-2}=\frac12\cdot \frac13 B_{k-3}^3.\end{eqnarray*} Continuing in the same way we obtain that the original probability is \(\frac1{k!}B_0^k=\frac{t^k}{k!}\) which completes the proof of (*).
We can now complete the calculation of the expected value of \(N\) \begin{eqnarray*} \mathbb E\left[N\right]&=&1+1+\sum_{k=2}^{\infty}\frac1{k!}=e. \end{eqnarray*}
First solution. Let us denote \(S_k=X_1+X_2+\cdots+X_k\). From the previous problem we obtain that for \(t\in[0,1]\) the cumulative distribution function of \(S_k\) satisfies \[F_{S_k}(t)=\mathbb P\left[S_k\leq t\right]=\frac{t^k}{k!}.\] The required expected value of \(X_N\) can be calculated by evaluating the expectations \(\mathbb E\left[X_N,N=2\right]\), \(\mathbb E\left[X_N,N=3\right]\) and then adding them up. Thus the required expected value of \(X_n\) is represented as the series \begin{eqnarray} \mathbb E\left[X_N\right]&=&\sum_{k=1}^{\infty} \mathbb E\left[X_N,N=k+1\right]. \end{eqnarray} Observe that for fixed \(k\geq 1\) the event \(N=k+1\) implies that \(S_k < 1\) and \(X_{k+1} > 1-S_k\). Therefore \begin{eqnarray*} \mathbb E\left[X_N,N=k+1\right]&=&\mathbb E\left[X_N,N=k+1, S_k<1, X_{k+1}>1-S_k\right]. \end{eqnarray*} On the event \(\{N=k+1\}\) we can write \(X_N=X_{k+1}\) and use the following simplified expression \begin{eqnarray*} \mathbb E\left[X_N,N=k+1\right]&=&\mathbb E\left[X_{k+1}, S_k<1, X_{k+1}>1-S_k\right]. \end{eqnarray*} We will now condition on \(\{S_k=t\}\) and integrate over the interval \([0,1]\) to obtain \begin{eqnarray*} \mathbb E\left[X_N,N=k+1\right] &=&\int_0^1\mathbb E\left[X_{k+1}\cdot1_{ X_{k+1}>1-t}\left|S_k=t\right.\right]\,dF_{S_k}(t)=\int_0^1\mathbb E\left[X_{k+1}\cdot1_{ X_{k+1}>1-t}\left|S_k=t\right.\right]\,d\left(\frac{t^k}{k!}\right). \end{eqnarray*} The random variable \(X_{k+1}\) is independent of \(\{X_1\), \(\dots\), \(X_k\}\). Therefore \(X_{k+1}\) is independent of the event \(\left\{S_k=t\right\}\). Therefore \begin{eqnarray*} \mathbb E\left[X_{k+1}\cdot1_{ X_{k+1}>1-t}\left|S_k=t\right.\right] &=& \mathbb E\left[X_{k+1}\cdot1_{ X_{k+1}>1-t}\right] =\int_{1-t}^1s\,ds=\left.\frac12s^2\right|_{s=1-t}^{s=1}=\frac12t(2-t). \end{eqnarray*} This last result implies \begin{eqnarray*} \mathbb E\left[X_N,N=k+1\right]=\int_0^1\frac{t(2-t)}{2}\cdot\frac{t^{k-1}}{(k-1)!}\,dt. \end{eqnarray*} We now obtain \begin{eqnarray*} \mathbb E\left[X_N\right]&=&\sum_{k=1}^{\infty}\int_0^1\frac{t(2-t)}{2}\cdot\frac{t^{k-1}}{(k-1)!}\,dt=\int_0^1\frac{t(2-t)}{2}\cdot\sum_{k=1}^{\infty}\frac{t^{k-1}}{(k-1)!}\,dt=\int_0^1\frac{t(2-t)}2e^t\,dt. \end{eqnarray*} The last integral can be calculated using integration by parts twice. The final result is \begin{eqnarray*} \mathbb E\left[X_N\right]&=&2-\frac{e}2. \end{eqnarray*}
Second solution. Let us introduce the notation \[\varphi(t) =\mathbb E\left[X_N\left| X_1=t\right.\right].\] The expectation of \(X_N\) satisfies \(\mathbb E\left[X_N\right]=\varphi(0)\). We will now condition on the events \(\{X_2=s\}\) and integrate over the interval \([0,1]\). Observe that if \(s > 1-t\) then \(N=2\) and \(X_N=X_2=s\). Therefore, for \(s > 1-t\) we have \[\mathbb E\left[X_N|X_2=s,X_1=t\right]=s.\] The value \(\varphi(t)\) becomes \begin{eqnarray*} \varphi(t)&=&\int_0^{1-t}\mathbb E\left[X_N|X_2=s, X_1=t\right]\,ds +\int_{1-t}^1 s\,ds. \end{eqnarray*} Observe that \begin{eqnarray*} \mathbb E\left[X_N|X_2=s, X_1=t\right]&=& \mathbb E\left[X_N|X_1=t+s\right], \end{eqnarray*} hence \begin{eqnarray} \varphi(t)&=&\int_0^{1-t}\varphi(t+s)\,ds+\int_{1-t}^1s\,ds.\quad\quad\quad\quad\quad\quad\quad(1) \end{eqnarray} We will take the derivatives of both sides of the previous equation. We will first use two dimensional chain rule to derive the formula \begin{eqnarray}\nonumber &&\frac{d}{dt}\int_0^{A(t)}B(t,s)\,ds\newline &=& B(t,A(t))A'(t)+\int_0^{A(t)}\frac{\partial}{\partial t}B(t,s)\,ds.\quad\quad\quad\quad\quad\quad(2)\end{eqnarray} The last formula is obtained by introducing the function \(\Psi(x,t)=\int_0^xB(t,s)\,ds\) and observing that \begin{eqnarray*}\frac{\partial }{\partial x}\Psi(x,t)&=&B(t,x)\quad\mbox{and}\newline \frac{\partial \Psi}{\partial t}\Psi(x,t)&=&\int_0^x\frac{\partial}{\partial t}B(t,s)\,ds.\end{eqnarray*} Now applying the chain rule to the function \(G(t)=\Psi(A(t),t)\) gives us \begin{eqnarray*}G'(t)&=&\nabla \Psi(A(t),t)\cdot \langle A'(t),1\rangle\newline &=&\frac{\partial}{\partial x}\Psi(A(t),t)\cdot A'(t)+\frac{\partial}{\partial t}\Psi(A(t),t) \end{eqnarray*} which directly implies (2). Taking the derivatives of both sides of (1) implies \begin{eqnarray*} \varphi'(t)&=&-\varphi(t+1-t) +\int_0^{1-t}\varphi'(t+s)\,ds +(1-t)=-\varphi(1)+\varphi(1)-\varphi(t)+1-t. \end{eqnarray*} Thus we obtain the differential equation for \(\varphi\) \[\varphi'(t)+\varphi(t)=1-t.\] Multiplying both sides by \(e^t\) gives us \[\left(e^t\varphi(t)\right)'=\left(1-t\right)e^t.\] By fundamental theorem of calculus we now obtain \begin{eqnarray*} e^1\varphi(1)-e^0\varphi(0)&=&\int_0^1\left(e^t\varphi(t)\right)'\,dt=\int_0^1\left(1-t\right)e^t\,dt.\end{eqnarray*} The last integral is calculated using integration by parts. We derive \begin{eqnarray*}e^1\varphi(1)-e^0\varphi(0) &=&-1+\int_0^1e^t\,dt=e-2. \end{eqnarray*} Since \(\varphi(1)=\frac12\), we obtain \(\varphi(0)=2-\frac e2\).