Variance of the stopping time. Matching Problem I have a following problem:
$N$ guests leave their hats in a heap and collect them in random order. Those who by chance get back their own hats happily go home. The remaining ones yet again throw their hats in a heap and collect them randomly. Those who get back their own hats happily go home. ...This continues until the stopping time $T$, when all gentlemen go home with their own hats on. 
Find $E[T]$ and $Var[T]$
My progress:
I've successfully proved that if $X_n$ is the number of guests present after the $n$-th round, then $X_n$$+$$n$ is a martingale. 
According to the optimal stopping theorem $E$[$X_T$$+$$T$]=$E$[$X_0$]=$N$ and therefore $E[T]$=$N$
But I am now stuck on finding the variance. My guess is that I should consider something like $X_n^2$ + (something that depends on n), prove that it's a martingale too and then somehow find the variance from this.
If someone can help me with this last part I would be very grateful.
 A: You have the right idea. The trick is that, if $\{M_n\}$ is a martingale, and you define
$$Q_0:=0, \quad Q_n:=\sum_{i=1}^n E\big[(M_i-M_{i-1})^2|\mathcal F_{i-1}\big],$$
then $\{M_n^2-Q_n\}$ is also a martingale. (You can easily check this.) In our case, $M_n=X_n+n$; in order to calculate $Q_n$, it will be helpful to discuss our underlying distribution a little more. In your original set-up, let $D_N$ denote the distribution of the number of people who get their hat back on the first try. If $Z\sim D_N$, then you can write
$$Z = \sum_{i=1}^N1_{A_i},$$
where $A_i$ is the event $\{\text{Person }i\text{ gets their hat back}\}$. Since $P(A_i)=\frac1N$ for all $i$, you have $E[Z] = \sum_{i=1}^N\frac1N=1$. (You would have had to do a similar calculation to show $\{X_n+n\}$ is a martingale.) This representation also allows us to calculate the second moment: for $i\neq j$, one has $P(A_i\cap A_j) = \
\frac1{N(N-1)}$, and so
$$E[Z] = E\left[ \sum_{i=1}^N 1_{A_i} + 2\sum_{1\le i<j \le N}1_{A_i\cap A_j}\right] = 1 + 2\sum_{1\le i<j\le N}\frac1{N(N-1)} = 1+1 = 2.$$
Back to our problem: one has $M_i-M_{i-1} = X_i - X_{i-1} + 1$ and so
$$(M_i-M_{i-1})^2 = (X_{i-1}-X_i)^2 - 2(X_{i-1}-X_i) + 1.$$
This is great, because conditional on $\mathcal F_{i-1}$, $X_{i-1}-X_i \sim D_{X_{i-1}}$, and so
$$E[(M_i-M_{i-1})^2|\mathcal F_{i-1}] = 2 - 2 + 1 = 1,$$
which implies $Q_n=n$. We have shown
$$ M_n^2 - n = X_n^2 + 2X_n + n^2 - n $$
is a martingale. Applying the optional stopping theorem (this needs justification in both cases, by the way - you should do this), we find
$$N^2+2N = E[M_0^2] = E[M_T^2 - T] = E[T^2-T] = E[T^2] - N.$$
Rearranging, we deduce $E[T^2] = N^2 + 3N$, and hence $\operatorname{Var}(T) = E[T^2] - E[T]^2 = 3N$.
