Black Swans


9 points



Yeah what I mean is at least one pair, thank you for pointing that out, fixed!

Secret Santa Redux 🎅

Motivated by the puzzle Secret Santa 🎅, whose solution is quite well known, I propose a far harder puzzle (I think):

A group of $N$ people place their names into a hat. Each person draws a name at random to decide who they will give a gift to. What is the probability that at least one pair of people end up picking each other? What is the expected number of such pairs?

So for example, if $N = 2$, then there is a $\frac{1}{2}$ chance of such a pair occurring, as either each person picks themselves or they pick each other and create a pair. Therefore the expected number is also $\frac{1}{2}$.

If $N = 3$ it is possible to check that the probability is $\frac{1}{3}$, and the expected number of such pairs is $1$. (I am not sure of this, someone check it please)

In general, one might ask this for an arbitrary cycle, i.e. what is the probability and expected number of $k$ cycles of gifting occurring among $N$ people.

Well, first of all the normal distribution has many nice properties (i.e. any linear combination of normals is also normal, many results can be derived analytically) that make the normal distribution nice to work with.

It also provides a good approximation to other distributions largely due to the central limit theorem which states that for iid random variables $X_1, X_2 \dots X_n$ with finite mean and variance the random variable of the sum $X_1+X_2+\dots+X_n$ tends to a normal distribution as $n\rightarrow \infty$ (turns out these conditions can be relaxed a bit and the result is still normally distributed).

So for example if you have a lot of independent measurements (such as, for example the hemoglobin concentration in blood of a certain group of people) then (under some extra assumptions which are often true or at least close to true) the mean (i.e. the mean hemoglobin concentration of the group) is approximately normally distributed, which then allows us to use a wide variety of methods tailored to the normal.

Isnt it just $\frac{1}{2}$? Since the events are independent...