I want to know if I have used the optional stopping theorem correctly in this problem.
A parking-lot attendant has mixed up $n$ keys for $n$ cars. The $n$ car owners arrive together, and the attendant gives each owner a key according to a permutation chosen uniformly and random from all permutations. If an owner receives the key to his car, he takes it and leaves; otherwise he returns the key to the attendant. The attendant now repeats the process with the remaining keys and car owners. This continues until all owners receive the keys to their cars.
Let $R$ be the number of rounds until all car owners receive the keys to their cars. We want to compute $\mathbb{E}(R)$. Let $X_i$ be the number of owners who receive their car keys in the $i$th round. Prove that $$Y_i=\sum_{j=1}^i (X_j-\mathbb{E}[X_j|X_1, \cdots X_{j-1}])$$ is a martingale. Use the optional stopping theorem to compute $\mathbb{E}[R]$.
I have shown that $Y_i$ is indeed a martingale, and I think I have done correctly. Given that $Y_i$ is a martingale, I would like to use the optional stopping time theorem. We have $\sum_{i=1}^R X_i=n$, and $R$ is a stopping time. Then,
$$\mathbb{E}[Y_R]=\mathbb{E}[\sum_{j=1}^R(X_j-\mathbb{E}[X_j|X_1, \cdots X_{j-1}])]=n-\mathbb{E}[\sum_{j=1}^R \mathbb{E}[X_j|X_1, \cdots X_{j-1}]]$$
I first thought about interchanging the sum and the expectation, but as $R$ can be unbounded, I think there is no justification for it. Instead, I just calculated $\mathbb{E}[X_j|X_1, \cdots X_{j-1}]$. If $X_1, \cdots X_{j-1}$ are given, then there are $m:=n-\sum_{i=1}^{j-1}X_i$ people at the $j$th step. If we let $Y_i$ be the Bernoulli random varable that takes value $0$ when he doesn't get his own key, and $1$ when he gets it, then $\sum_{k=1}^m Y_k=X_j$. Take expectation each side, and in this case, $m$ is finite, so we can interchange the sum and the expectation. So, we get
$$\sum_{k=1}^m \mathbb{E}[Y_k]=\mathbb{E}[X_j]$$
where $\mathbb{E}[Y_k]=\mathrm{Pr}(Y_k=1)=\frac{1}{m}$, so we get $\mathbb{E}[X_j]=1$ in the case $X_1, \cdots X_{j-1}$ are given. That is, $\mathbb{E}[X_j|X_1, \cdots X_{j-1}]=1$. Plugging this value to the first equation, we get
$$\mathbb{E}[Y_R]=n-\mathbb{E}[R]$$
and since $\mathbb{E}[Y_1]=\mathbb{E}[X_1-\mathbb{E}[X_1|X_1]]=0$, we have $\mathbb{E}[R]=n$.
I have some questions about my proof.
- Is the proof correct?
- Is my justification for interchanging the expectation and the sum correct?
- Even though the assumptions for Wald's equation are not met(The distribution of $X_i$'s are not equal), it seems that the $\mathbb{E}[R]$ obtained from this case is equal to the one I found. $$\mathbb{E}[\sum_{j=1}^R X_j]=\mathbb{E}[R]\mathbb{E}[X_1]$$ As the left hand side is $n$, and $\mathbb{E}[X_1]=1$, so that $\mathbb{E}[R]=n$. Is this a coincidence, or can I actually use Wald's equation for it? In this case, even though the distributions of $X_i$'s are not equal, the expectation for each $X_i$'s are all $1$. Does this have some meaning?
Ok, I look at the book to see if I can see something useful, and indeed I find it. The exercise seems to rely in the definition of stopping time given in the book, what says that $T$ is a stopping time if the event $\{T=n\}$ is independent of $Z_{n+j}|Z_1,\ldots ,Z_n$ for $j\geqslant 1$, however this is not the common definition of stopping time, where the above conditional independence is not assumed.
Also, reading the chapter, in the book its assumed that the filtration respect to what the martingale and the stopping time are defined is the natural filtration of the sequence $\{X_n\}_{n\in\mathbb{N}}$.
The above could be a hint to solve the exercise, I mean, if we show that $R$ is conditionally independent of the $\{X_n\}_{n\in\mathbb{N}}$, that is if $R$ is an stopping time with the above definition, then we can try something. However its easy to see that $0=\Pr [X_{m+1}=1|X_1=0, R=m]\neq \Pr [X_{m+1}=1|X_1=0]>0$, so $R$ is not an stopping time for the natural filtration of $\{X_n\}_{n\in\mathbb{N}}$ with the definition given in the book.
I think that the exercise in the book doesn't make sense as written, its not well-posed.
An elementary solution to the exercise is as follow: first note that, by the definition of the $X_k$, we have that $\sum_{k\geqslant 1}X_k=n$ almost sure and if we set $S_m:=\sum_{k=1}^{m}X_k$ then the events $\{S_m=s\}:=\{\omega \in \Omega : S_m(\omega )=s\}$ for $s\in\{0,\ldots, n\}$ defines a partition of $\Omega $ for any chosen $m$, also observe that $\{S_m<n\}=\{R\geqslant m+1\}$.
Now using the law of total expectation we have that
$$ \begin{align*} \mathbb{E}[X_k]&=\sum_{s=0}^n \mathbb{E}[X_k|S_{k-1}=s]\Pr [S_{k-1}=s]\\ &=\sum_{s=0}^{n-1}1\cdot \Pr [S_{k-1}=s]+0\cdot \Pr [S_{k-1}=n]\\ &=\Pr [S_{k-1}<n]\\ &=\Pr [R\geqslant k] \end{align*} $$
as each $\mathbb{E}[X_k|S_{k-1}=s]$, for $s<n$, is the expectation of a sum of (not independent) $n-s$ Bernoulli r.v. with same parameter $p=\frac1{n-s}$ and $\mathbb{E}[X_k|S_{k-1}=n]=0$ because $\Pr [X_k>0|S_{k-1}=n]=0$.
To clarify a bit about $\mathbb{E}[X_k|S_{k-1}=s]=1$ when $s<n$: let $\Omega ':=\{S_{k-1}=s\}$ equipped with the induced probability measure defined by $P'(A):=\Pr [A|S_{k-1}=s]$ for any measurable $A\subset \Omega '$ and denote by $\mathbb{E}'$ the expectation in this probability space, then from the definition of $X_k$ we knows that $X_k|_{\Omega '}=\sum_{i=s+1}^n Y_i$ where each $Y_i\sim \operatorname{Ber}(\frac1{n-s})$, so
$$\mathbb{E}[X_k|S_{k-1}=s]=\mathbb{E}'[X_k|_{\Omega '}]=\sum_{k=s+1}^n \mathbb{E}'[Y_i]=1$$
Then from all the above we find that
$$ \mathbb{E}[R]=\sum_{k\geqslant 1}\Pr [R\geqslant k]=\sum_{k\geqslant 1}\mathbb{E}[X_k]=\mathbb{E}\left[\sum_{k\geqslant 1}X_k\right]=n $$
∎