In a Secret Santa game, a group of N friends each write their name on a slip of paper and place these slips in a bowl. The slips are mixed and each person draws a slip from the bowl. If anyone draws their own name then the whole process is repeated until each person draws some other person's name. Now that each person has another person's name, this is the name of the recipient of a gift from their Secret Santa. What is the probability that this process can be effected in 3 or fewer tries? Lex $X_i=1$ if person i does not draw their own name and $X_i=0$ if person i does draw their name. Do this for each $i=1,2,...,N$. What is $E[X]$? What is $E[X_1X_2]$? What is $E[X_1+...+X_N]$ for large N (i.e. as N goes to inf)?
It may help to envision this process as a random directed graph. This is a graph with a finite vertex set V. There is also a collection of arrows that is a subset of V x V. IIf (u,v) is in this subset then we draw an arrow from vertex u to vertex v. Notice that the rules imply that every vertex has an arrow departing from it and each vertex has an arrow pointing toward it. Use this representation to prove what the probability is.
I honestly have no idea where to star with this or what I'm even supposed to do... Any help is appreciated.
Hint: You are picking a random permutation and success is when you get a derangement. The chance of that is essentially $\frac 1e$