Hat Matching Problem Expectation I have an interesting problem in the context of the hat matching problem:
There are $n$ people with hats at a party.
Each person randomly grabs a hat.
A match occurs if a person gets his own hat.
I'd like to know three things:
i) The probability that no one gets their hat
ii) How often we expect someone to get their hat
iii) If we let the n men choose their hats every minute, how much time do we expect until the first match (that is at minute 1, man 1 picks his hat, at minute 2, man 2 picks his hat, etc...)
I got number i) using inclusion exclusion, and ii) using linearity of expectation but I'm stuck on iii)
Here's what I've done so far.
Essentially we're trying to find the number of random permutations $\{x_1 , ... , x_n\}$ of $\{1, ... , n\}$ such that :
$x_i = i\;$ AND $\;x_j != j$ for all $j < i$
Since if we know this, then we know the probability of  match occurring at any given time.
Intuitively, this is the same number of ways of getting $x_1 = 1, x_2 != 2, ..., x_i != i$
But I can't see how to compute this since the number of ways of having $x_k != k$, for example, depends on wether or not $k$ was placed earlier in our permutation.
Thanks!
 A: Here are  some observations. Start  with the species  $\mathcal{Q}$ of
permutations with fixed points marked, so that we have
$$\mathcal{Q} = \mathfrak{P}
\left(\mathcal{U}\mathcal{Z}
+ \mathfrak{C}_{=2}(\mathcal{Z})
+ \mathfrak{C}_{=3}(\mathcal{Z})
+ \mathfrak{C}_{=4}(\mathcal{Z})
+ \cdots\right).$$
Translating to generating functions we obtain
$$Q(z, u) = \exp\left(
uz + \frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \cdots \right)
\\= \exp\left(uz -z + \log\frac{1}{1-z}\right)
= \frac{e^{-z}}{1-z} e^{uz}.$$
The probability that no one gets  their hat is computed from the count
of permutations with no fixed points,
$$D_n = n! [z^n] [u^0] Q(z, u)
= n! [z^n] \frac{e^{-z}}{1-z}
= n! \sum_{k=0}^n \frac{(-1)^k}{k!} \approx \frac{n!}{e}.$$
It follows that the probability is $1/e.$

For the expected value of people getting their hat we obtain
$$[z^n] \left. \frac{d}{du} Q(z, u)\right|_{u=1}
= [z^n] \left. \frac{z e^{-z}}{1-z} e^{uz}\right|_{u=1}
= [z^n] \frac{z}{1-z} = 1$$
and thus there is an average of one fixed point per permutation.

As for  the location of  the smallest fixed  point call it $q$  we can
reason as follows. Take any permutation $\sigma$ of the $n-q$ elements
that are  larger than  $q$ and factor  it into cycles.   Partition the
$q-1$  elements smaller  than $q$  into a  derangement  containing $p$
elements and distribute the remaining $q-1-p$ elements onto the cycles
of the permutation  $\sigma$ of $n-q$, which will  assure that none of
them becomes a fixed point and $q$ is the smallest fixed point because
the elements less than $q$ are either in the derangement of $p$ elements
or on the cycles of $\sigma,$ where none of them is a singleton.
This gives for $p$ fixed the value
$$(n-q)! \times {q-1\choose p} \times D_p \times 
(n-q)(n-q+1)(n-q+2)\\ \cdots (n-q+(q-1-p-1))
\\= (n-q)! \times {q-1\choose p} \times D_p \times 
(n-q)(n-q+1)(n-q+2)\ldots (n-p-2)
\\= (n-q)! \times {q-1\choose p} \times D_p \times 
{n-p-2\choose q-1-p} (q-1-p)!$$
When $q<n$ this can also be written as
$$(n-q)! \times {q-1\choose p} \times D_p \times 
\frac{(n-p-2)!}{(n-q-1)!}$$
or
$$(n-q)  \times {q-1\choose p} \times D_p \times (n-p-2)!$$
The  fourth term  in the  product above  on the  first line  i.e.  the
product at the end represents the fact that we have $n-q$ choices when
placing the first  element from the $q-1-p$ elements  on the cycles of
$\sigma,$ and $n-q+1$ choices for the next one and so on. 
The first binomial coeffcient represents the choice of $p$ elements for 
the derangement. 

The total contribution which is  the desired sum of the smallest fixed
point over all permutations is thus given by
$$\sum_{q=1}^n q\times (n-q)!  \times
\sum_{p=0}^{q-1} {q-1\choose p} \times D_p \times 
{n-p-2\choose q-1-p} (q-1-p)!$$
or alternatively
$$n\times D_{n-1} + \sum_{q=1}^{n-1} q\times (n-q)\times
\sum_{p=0}^{q-1} {q-1\choose p} \times D_p \times (n-p-2)!$$
where we have used the fact that if $n$ is the first fixed point it must have been preceded by a derangement of the first $n-1$ elements.

This yields the sequence
$$1, 1, 7, 31, 191, 1331, 10655, 95887, 958879, 10547659, \ldots$$
which  points  us  to OEIS  A155521  where
additional material awaits and which would appear to confirm the above
calculation.

The  following admittedly simple Maple program  was used  to  confirm the
above formulae for small $n:$

P := proc(n)
local gf, p, pos;
option remember;
    gf := 0;
    for p in combinat:-permute(n) do
        for pos to n do if p[pos] = pos then break end if end do;
        if pos <= n then gf := gf + z^pos end if
    end do;
    gf
end proc

Addendum. 
(Inspired by the work of @YuvalFilmus.)
We learn  from the OEIS entry that  by a combinatorial bijection the
sequence above is the number  of permutations on $n+1$ elements having
at least two fixed points. This has EGF
$$Q_{\ge 2}(z) =
\left. (Q(z, u) - [u^0] Q(z, u) - [u^1] Q(z, u))\right|_{u=1}
= \frac{1}{1-z} 
- \frac{e^{-z}}{1-z}
- \frac{ze^{-z}}{1-z}.$$
Extracting coefficients we get
$$n! [z^n] Q_{\ge 2}(z) = 
n! \left(1 - \sum_{k=0}^n \frac{(-1)^k}{k!}
- \sum_{k=0}^{n-1} \frac{(-1)^k}{k!}\right)
 \approx n! \left(1-\frac{2}{e}\right)$$
Dividing by the count of non-derangements we obtain
$$\frac{(n+1)!(1-2/e)}{n!(1-1/e)} = 
(n+1) \times \frac{e-2}{e-1}.$$
A: Here is how to solve this problem. Let $p_k$ be the probability that there are $k$ matches, given that there is at least one. We can estimate these probabilities as a Poisson random variable with expectation 1 conditioned on being positive. Given that there are $k$ matches, the matches are distributed uniformly, and the expected minimal match is known;  it is roughly $n/(k+1) $. So your expectation is roughly
$$ n\sum_{k\geq1} \frac{p_k}{k+1} \approx \frac{n}{e-1}\sum_{k\geq1} \frac{1}{(k+1)!}=\frac{e-2}{e-1}n.$$
