4.5.2 Solution

Part (A)

We first covert the sequence of random variables \(X_{n}\) to sequence of random variables \(I_{i}\) as described. A diagram below will also help illustrate this conversion

We need to show that \(P\left ( I_{i}=1\right ) =\frac {1}{i}.\) Using the hint given, we write (for \(i\geq 2\))

\[ P(I_{i}=1)=P\left ( X_{1}<X_{i},X_{2}<X_{i},\cdots ,X_{i-1}<X_{i}\right ) \]

Conditioning on \(X_{i}\), and assuming the pdf of \(X\) is given by \(f\left ( x\right ) \) we write

\[ P(I_{i}=1)={\displaystyle \int \limits _{-\infty }^{\infty }} P\left ( X_{1}<X_{i},X_{2}<X_{i},\cdots ,X_{i-1}<X_{i}|X_{i}=x\right ) f\left ( x\right ) dx \]

Since the \(X_{j}\) random variables are independent from each others, we break the above ’and’ probabilities to products of probabilities.

\[ P(I_{i}=1)={\displaystyle \int \limits _{-\infty }^{\infty }} P\left ( X_{1}<X_{i}|X_{i}=x\right ) \ \ P\left ( X_{2}<X_{i}|X_{i}=x\right ) \ \cdots P\left ( X_{i-1}<X_{i}|X_{i}=x\right ) \ \ f\left ( x\right ) dx \]

But \(P\left ( X_{j}<X_{i}|X_{i}=x\right ) =F\left ( x\right ) \), hence the above becomes

\begin{equation} P(I_{i}=1)={\displaystyle \int \limits _{-\infty }^{\infty }} \left [ F\left ( x\right ) \right ] ^{i-1}\ \ f\left ( x\right ) dx \tag {1}\end{equation}

But \(f\left ( x\right ) =F^{\prime }\left ( x\right ) \), hence the above becomes

\[ P(I_{i}=1)={\displaystyle \int \limits _{-\infty }^{\infty }} \left [ F\left ( x\right ) \right ] ^{i-1}\ \ F^{\prime }\left ( x\right ) dx \]

Now do integration by parts (let \(dv=F^{\prime }\left ( x\right ) \) and \(u=\left [ F\left ( x\right ) \right ] ^{i-1}\)

\begin{align*} P(I_{i} & =1)=\left [ uv\right ] _{-\infty }^{\infty }-{\displaystyle \int \limits _{-\infty }^{\infty }} vdu\\ & =\left [ F\left ( x\right ) \left [ F\left ( x\right ) \right ] ^{i-1}\right ] _{-\infty }^{\infty }-{\displaystyle \int \limits _{-\infty }^{\infty }} F\left ( x\right ) \left ( i-1\right ) \left [ F\left ( x\right ) \right ] ^{i-2}F^{\prime }\left ( x\right ) dx\\ & =\left [ F\left ( x\right ) ^{i}\right ] _{-\infty }^{\infty }-\left ( i-1\right ) {\displaystyle \int \limits _{-\infty }^{\infty }} \left [ F\left ( x\right ) \right ] ^{i-1}F^{\prime }\left ( x\right ) dx \end{align*}

But \(\left [ F\left ( x\right ) ^{i}\right ] _{-\infty }^{\infty }=1-\left ( 0\right ) =1\) hence the above becomes

\[ P(I_{i}=1)=1-\left ( i-1\right ) \overset {P\left ( I_{i}=1\right ) }{\overbrace {{\displaystyle \int \limits _{-\infty }^{\infty }} \left [ F\left ( x\right ) \right ] ^{i-1}F^{\prime }\left ( x\right ) dx}}\]

But \({\displaystyle \int \limits _{-\infty }^{\infty }} \left [ F\left ( x\right ) \right ] ^{i-1}F^{\prime }\left ( x\right ) dx=P(I_{i}=1)\) since it is the integral we started with (see (1)), so move it to the left side, and the above becomes

\begin{align*} P(I_{i} & =1)=1-\left ( i-1\right ) P(I_{i}=1)\\ P(I_{i} & =1)+\left ( i-1\right ) P(I_{i}=1)=1\\ P(I_{i} & =1)i=1 \end{align*}

Hence

\[ P(I_{i}=1)=\frac {1}{i} \]

Part(B)

\(N_{n}\) is number of records up to time \(n\). We need to find \(E\left ( N_{n}\right ) \) and \(Var\left ( N_{n}\right ) \)

\begin{align*} N_{n} & =I_{1}+I_{2}+\cdots +I_{n}\\ E\left ( N_{n}\right ) & =E\left ( I_{1}+I_{2}+\cdots +I_{n}\right ) \\ & =E\left ( I_{1}\right ) +E\left ( I_{2}\right ) +\cdots +E\left ( I_{n}\right ) \end{align*}

But \(E\left ( I_{1}\right ) =1\times P\left ( I_{1}=1\right ) +0\times P\left ( I_{1}=0\right ) =P\left ( I_{1}=1\right ) \) and similarly, \(E\left ( I_{i}\right ) =P\left ( I_{i}=1\right ) \)

Hence

\begin{align*} E\left ( N_{n}\right ) & =P\left ( I_{1}=1\right ) +P\left ( I_{2}=1\right ) +\cdots +P\left ( I_{n}=1\right ) \\ & =1+\frac {1}{2}+\frac {1}{3}+\cdots +\frac {1}{n}\\ & ={\displaystyle \sum \limits _{i=1}^{n}} \frac {1}{i}\end{align*}

So \(E\left ( N_{n}\right ) \) is a harmonic number. In the limit, this sum is infinity. Hence number of records is infinite. i.e. if we wait long enough, we will always obtain a new record.

To find the variance of \(N_{n}\), we use the hint and assume \(I_{i}\) are independent of each others (i.e. when a record occurs is independent of when previous record occurred), hence the covariance terms drop out (since all zero) and we are left with the sum of variances

\begin{align*} Var\left ( N_{n}\right ) & =Var\left ( I_{1}+I_{2}+\cdots +I_{n}\right ) \\ & =Var\left ( I_{1}\right ) +Var\left ( I_{2}\right ) +\cdots +Var\left ( I_{n}\right ) \end{align*}

But

\[ Var\left ( I_{i}\right ) =E\left ( I_{i}^{2}\right ) -E\left ( I_{i}\right ) ^{2}\]

But \(E\left ( I_{i}^{2}\right ) =1^{2}\times P\left ( I_{i}=1\right ) +0^{2}\times P\left ( I_{1}=0\right ) =P\left ( I_{i}=1\right ) =\frac {1}{i}\)

Hence \(E\left ( I_{i}^{2}\right ) =\frac {1}{i}\) , therefore

\begin{align*} Var\left ( I_{i}\right ) & =\frac {1}{i}-P\left ( I_{i}=1\right ) ^{2}\\ & =\frac {1}{i}-\left ( \frac {1}{i}\right ) ^{2}\end{align*}

therefore

\[ Var\left ( N_{n}\right ) ={\displaystyle \sum \limits _{i=1}^{n}} \frac {1}{i}-\left ( \frac {1}{i}\right ) ^{2}\]

Since \({\displaystyle \sum \limits _{i=1}^{n}} \frac {1}{i}=\infty \) as \(n\) gets very large, and \({\displaystyle \sum \limits _{i=1}^{n}} \frac {1}{i^{2}}=\frac {\pi ^{2}}{6}\) as \(n\) gets very large, then

\(Var\left ( N_{n}\right ) =\infty \) as \(n\) gets very large.

Part(C)

We need to find \(\Pr \left ( T=n\right ) \) where \(T\) is the time of the first record (not counting \(n=1\) which is always a record ofcourse).

\[ \Pr \left ( T=2\right ) =\Pr \left ( I_{2}=1\right ) =\frac {1}{2}\]

Now

\[ \Pr \left ( T=3\right ) =\Pr \left ( \text {no record at T=2,record at T=3}\right ) \]

Since having no record at \(T=2\) and having a record at \(T=3\) are indepdent events the above becomes

\begin{align*} \Pr \left ( T=3\right ) & =\Pr \left ( \text {no record at T=2}\right ) \text {\ }\Pr \left ( \text {record at T=3}\right ) \\ & =\left ( 1-\Pr \left ( I_{2}=1\right ) \right ) \times \Pr \left ( I_{3}=1\right ) \\ & =\left ( 1-\frac {1}{2}\right ) \left ( \frac {1}{3}\right ) \\ & =\frac {1}{2}\times \frac {1}{3}\end{align*}

Similarly,

\begin{align*} \Pr \left ( T=4\right ) & =\Pr \left ( \text {no record at T=2,no record at T=3,record at T=4}\right ) \\ & =\left ( 1-\Pr \left ( I_{2}=1\right ) \right ) \times \left ( 1-\Pr \left ( I_{3}=1\right ) \right ) \times \Pr \left ( I_{4}=1\right ) \\ & =\left ( 1-\frac {1}{2}\right ) \left ( 1-\frac {1}{3}\right ) \left ( \frac {1}{4}\right ) \\ & =\frac {1}{2}\times \frac {2}{3}\times \frac {1}{4}\\ & =\frac {1}{3}\times \frac {1}{4}\end{align*}

Similarly,

\begin{align*} \Pr \left ( T=5\right ) & =\Pr \left ( \text {no record at T=2,no record at T=3,no record at T=4,record at T=5}\right ) \\ & =\left ( 1-\Pr \left ( I_{2}=1\right ) \right ) \times \left ( 1-\Pr \left ( I_{3}=1\right ) \right ) \times \left ( 1-\Pr \left ( I_{4}=1\right ) \right ) \times \Pr \left ( I_{5}=1\right ) \\ & =\left ( 1-\frac {1}{2}\right ) \left ( 1-\frac {1}{3}\right ) \left ( 1-\frac {1}{4}\right ) \left ( \frac {1}{5}\right ) \\ & =\frac {1}{2}\times \frac {2}{3}\times \frac {3}{4}\times \frac {1}{4}\\ & =\frac {1}{4}\times \frac {1}{5}\end{align*}

Hence continuing this way, we see that

\[ \Pr \left ( T=n\right ) =\frac {1}{n\left ( n-1\right ) } \]

Hence

\begin{align*} \Pr \left ( T<\infty \right ) & =\lim _{k\rightarrow \infty }{\displaystyle \sum \limits _{n=2}^{k}} \frac {1}{n\left ( n-1\right ) }\\ & =\lim _{k\rightarrow \infty }\left ( \frac {k-1}{k}\right ) \\ & =1 \end{align*}

and

\begin{align*} E\left ( T\right ) & =2\times \Pr \left ( T=2\right ) +3\times \Pr \left ( T=3\right ) +4\times \Pr \left ( T=4\right ) +\cdots \\ & =2\left ( \frac {1}{2}\right ) +3\left ( \frac {1}{2}\times \frac {1}{3}\right ) +4\left ( \frac {1}{3}\times \frac {1}{4}\right ) +\cdots \\ & =1+\frac {1}{2}+\frac {1}{3}+\frac {1}{4}+\cdots \\ & ={\displaystyle \sum \limits _{i=1}^{\infty }} \frac {1}{n}\\ & =\infty \end{align*}

Hence

\[ E\left ( T\right ) =\infty \]

l.367 — TeX4ht warning — \SaveEverypar’s: 3 at \begindocument and 4 \enddocument —