Intereting Posts

Find the expected number of two consecutive 1's in a random binary string
$A/ I \otimes_A A/J \cong A/(I+J)$
Showing that $f = 0 $ a.e. if for any measurable set $E$, $\int_E f = 0$
Background for studying and understanding Stochastic differential equations
Putnam Exam Integral
Proof that the set of all possible curves is of cardinality $\aleph_2$?
A group is generated by two elements of order $2$ is infinite and non-abelian
Simplicity and isolation of the first eigenvalue associated with some differential operators
Solve $x^2$ $mod$ $23 = 7^2$
Why is $\sum_{k=1}^\infty (-1)^{k+1}\frac{ \text{csch}(\pi k)}{k} = \frac{1}{2}(\ln(64) – \pi)$?
Proving that the join of a path-connected space with an arbitrary space is simply-connected
To find area of the curves that are extension of ellipse
Evaluate $\int _0^{\infty }\frac{e^{-t^2}-e^{-4t^2}}{t^2}dt$
A topological vector space with countable local base is metrizable
Why are the differences between consecutive squares equal to the sequence of odd numbers?

Suppose $N$ men throw their hats in a room AND their coats in an other room.

Each man then randomly picks a hat and a coat.

What is the probability that:

- None of the men select his own hat and his own coat
- Exactly $k$ of the men select his own hat and his own coat.

More generally, if instead of $2$ items (hat and coat), the $N$ men threw $n$ items, how to find the probability mass function $P(k=0,1,2,\ldots,n)$ of the number of complete coincidences ($k$ men select their $n$ own items)?

- Probability of a substring occurring in a string
- How many combinations of $3$ natural numbers are there that add up to $30$?
- Number of non-negative whole number solutions if the coefficients of the variables are not equal to $1$
- Proof $\sum\limits_{k=1}^n \binom{n}{k}(-1)^k \log k = \log \log n + \gamma +\frac{\gamma}{\log n} +O\left(\frac1{\log^2 n}\right)$
- prove that $(n^2)!$ is divisible by $(n!)^{n+1}$, where $n\in \mathbb{N}$
- eigen decomposition of an interesting matrix (general case)

- If you draw two cards, what is the probability that the second card is a queen?
- Prove uniform distribution
- Monty hall problem with leftmost goat selection.
- permutation of $9$ digit
- If a 1 meter rope is cut at two uniformly randomly chosen points, what is the average length of the smallest piece?
- Integral Representation of Infinite series
- birthday problem - expected number of collisions
- Reviewing for exam: Chernoff bounds for a series of random variables
- Does finite expectation imply bounded random variable?
- Average Degree of a Random Geometric Graph

It is easier to work out the expected number of men with all their own items, namely $N^{-1}$ in the hat and coat case and $N^{1-n}$ in the more general case.

This is sampling without replacement, but as $N$ increases I would expect this to be asymptotically distributed like a Poisson distribution with the same expected values.

This asymptotic approximation is not bad even for small numbers. For 4 men and 2 items the expected number of men with the correct items is 0.25. The actual and Poisson probabilities, rounded to four decimal places, are

```
Correct actual Poisson
0 0.7865 0.7788
1 0.1806 0.1947
2 0.0313 0.0243
3 0.0000 0.0020
4 0.0017 0.0001
5+ 0 0.00001
```

You can derive the probability in a manner similar to that for the usual derivation of the derangement probabilities (the probability that none of the $N$ men get their own hat back).

There are a total of $N!^n$ ways that all of the items can be distributed among the $N$ men so that each has exactly one of each type of item. Let $A_i$ denote the event that the $i$th man obtains the $n$ items that belong to him. The number of ways this can happen is $|A_i| = (N-1)!^n$, as this involves distributing all items but those belonging to the $i$th man among the other $N-1$ men. Similarly, $|A_i \cap A_j| = (N-2)!^n$, and, in general, $|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}| = (N-j)!^n$. There are also $\binom{N}{j}$ ways to choose which $j$ men will receive their own $n$ items.

Let $D(N,n,k)$ denote the number of ways that exactly $k$ of the $N$ men receive all $n$ of their items back. By the principle of inclusion/exclusion, $$D(N,n,0) = \sum_{j=0}^N (-1)^j \binom{N}{j} (N-j)!^n = N! \sum_{j=0}^N (-1)^j \frac{(N-j)!^{n-1}}{j!}.$$

Now, $D(N,n,k) = \binom{N}{k} D(N-k,n,0)$, as this is the number of ways of choosing $k$ of the $N$ men to receive all of their items back times the number of ways that none of the remaining $N-k$ men receive all of their items back.

Thus $$D(N,n,k) = \binom{N}{k} (N-k)! \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!} = \frac{N!}{k!} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Dividing by $N!^n$, we have that the probability that exactly $k$ of the $N$ men receive all $n$ of their items back is

$$\frac{1}{k! N!^{n-1}} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Note that this formula agrees with the values obtained by Henry for the case $N = 4$, $n=2$.

*Added*: In fact, the Poisson approximation suggested by Henry appears to match up well with the exact values provided by the formula given here for small values of $k$. The accuracy of the Poisson approximation appears to deteriorate, *relatively speaking*, as $k$ increases. However, the Poisson approach still gives a good *absolute* approximation when $k$ is large because the probabilities are extremely small.

- $\operatorname{span}(x^0, x^1, x^2,\cdots)$ and the vector space of all real valued continuous functions on $\Bbb R$
- Extension Thoerem for the Sobolev Space $W^{1, \infty}(U)$
- Evaluate $\int \cos(3x) \sin(2x) \, dx$.
- Cardinal number subtraction
- Is a function that maps every compact set to a compact set continuous?
- The value of a Dirichlet $L$-function (and its derivative) at $s=0$
- Do we gain anything interesting if the stabilizer subgroup of a point is normal?
- Is it possible to simplify $\frac{\Gamma\left(\frac{1}{10}\right)}{\Gamma\left(\frac{2}{15}\right)\ \Gamma\left(\frac{7}{15}\right)}$?
- Need help with calculating this sum: $\sum_{n=0}^\infty\frac{1}{2^n}\tan\frac{1}{2^n}$
- Galois group command for Magma online calculator?
- Evaluate $\lim_{n \rightarrow \infty} \frac {^{1/n}}{n}$
- Find all limit points of $M=\left \{ \frac{1}{n}+\frac{1}{m}+\frac{1}{k} : m,n,k \in \mathbb{N} \right \}$ in space $(M,\rho_{e})$
- Convergence of test-functions is not induced by any metric.
- Finite Subgroups of GL(n,R)
- Poisson Process Conditional Probability Question