Question

Let \(X_{1}, X_{2}, \ldots\) be a sequence of independent identically distributed continuous random variables. We say that a record occurs at time \(n\) if \(X_{n}>\max \left(X_{1}, \ldots, X_{n-1}\right)\) That is, \(X_{n}\) is a record if it is larger than each of \(X_{1}, \ldots, X_{n-1}\). Show (a) \(P(\) a record occurs at time \(n\\}=1 / n ;\) (b) \(E[\) number of records by time \(n]=\sum_{i=1}^{n} 1 / i ;\) (c) \(\operatorname{Var}(\) number of records by time \(n)=\sum_{i=1}^{n}(i-1) / i^{2}\); (d) Let \(N=\min (n: n>1\) and a record occurs at time \(n] .\) Show \(E[N]=\infty\). Hint: For (ii) and (iii) represent the number of records as the sum of indicator (that is, Bernoulli) random variables.

Short answer

The probability of a record occurring at time n is given by \(P(A_n) = \frac{1}{n}\). The expected number of records by time n is given by \(E[\text{number of records by time }n] = \sum_{i=1}^{n} \frac{1}{i}\). The variance of the number of records by time n is given by \(\operatorname{Var}(\text{number of records by time }n) = \sum_{i=1}^{n} \frac{i-1}{i^2}\). Finally, the expected value of N, where N is the minimum n such that a record occurs at time n, is equal to infinity: \(E[N] =\infty\).

Step-by-step solution

(a) Probability of a record occurring at time n

Let A_i be the event that a record occurs at time i. Then: \(P(A_i) = P(X_i > \max(X_1,\dots,X_{i-1}))\) Now we can use the fact that the random variables are independent and identically distributed. By symmetry (due to identical distributions), the probability that X_i is the largest among the first i observations is equal to \(1/i\), since each observation has the same chance of being the largest. Therefore, for all i, we have: \(P(A_i) = \frac{1}{i}\) Now, we can simplify this for the special case of n: \(P(A_n) = \frac{1}{n}\)

(b) Expected number of records by time n

Let B_i be the Bernoulli (indicator) random variable such that: \(B_i = \begin{cases} 1, & \text{if a record occurs at time }i \\ 0, & \text{otherwise} \end{cases}\) So, by the definition of expectation and the linearity of expectation: \(E[\text{number of records by time }n] = E[\sum_{i=1}^{n}B_i] =\sum_{i=1}^{n} E[B_i]\) We know that for a Bernoulli random variable, \(E[B_i] = P(A_i)\). From part (a), we have that \(P(A_i) = \frac{1}{i}\). Therefore, we can simplify this to: \(E[\text{number of records by time }n] = \sum_{i=1}^n \frac{1}{i}\)

(c) Variance of the number of records by time n

By the definition of variance and the linearity of variance for independent random variables, we have: \(\operatorname{Var}(\text{number of records by time }n) = \operatorname{Var}(\sum_{i=1}^{n}B_i) = \sum_{i=1}^{n}\operatorname{Var}(B_i)\) For a Bernoulli random variable, \( \operatorname{Var}(B_i)\) is given by \(\operatorname{Var}(B_i) = P(A_i)(1 - P(A_i))\). From part (a), we know that \(P(A_i) = \frac{1}{i}\). Substituting this, we have: \(\operatorname{Var}(\text{number of records by time }n) = \sum_{i=1}^{n}\operatorname{Var}(B_i)= \sum_{i=1}^{n} \frac{1}{i}(1 - \frac{1}{i}) = \sum_{i=1}^{n} \frac{i-1}{i^2}\)

(d) Expected value of N

Let W_i={{N=n}} be the indicator function for the event that the first record occurs at time i. Then \(E[W_i] = P(W_i)= P(N=i)\) which from part (a) translates to \(P(N=i) = P(A_{i})P^{c}(A_{1})\dots P^{c}(A_{i-1}) \) and substituting values \(E[W_i] = \frac{1}{i}(1-\frac{1}{2})\dots(1-\frac{1}{i-1})\) Now, for the expected value of N, we have: \(E[N] = \sum_{i=2}^{\infty}iE[W_i] = \sum_{i=2}^{\infty} i\frac{1}{i}(1-\frac{1}{2})\dots(1-\frac{1}{i-1})\) It is clear that the series doesn't converge as it is a harmonic series, meaning that the sum goes to infinity as the number of terms increases: \(E[N] =\sum_{i=2}^{\infty} (1-\frac{1}{2})\dots(1-\frac{1}{i-1}) = \infty\)