Men in a bar - stoch. processes

Question

Hello everyone, I'm trying to solve a applied stochastic process problem and even the example is beautiful, I don't know how to approach it. Here the problem:

10 men want to get out of a bar, they do it in the following way: Initially they store all 10 umbrella in a basket next to the exit from the pub. They go all together and each one picks an umbrella at random. Those who picked their own umbrellas leave while those who picked a wrong umbrella, put it back and return to a pub for another glass of beer. After that they return to the basket and try once again. And so on. Let T be the number of rounds needed for all men to leave, and let N be the total number of beers consumed during the procedure. a) Compute E(T) b) Compute E(N)

Can someone help me, also in how to put this problem in a appropriate model.

Thank you

Answer 1

Let $t_m$ be the value of $\mathbf{E}(T)$ for the same problem but with $m$ men instead of $10$, and let $p_t$ be the probability that a random element of $S_m$ fixes exactly $m-t$ elements. The following formula follows from the law of total expectation: $$ t_m = 1 + t_0 p_0 + t_1 p_1 + \cdots + t_m p_m. $$ Note, however, by linearity of expectation, $$ 0 p_0 + 1 p_1 + \cdots + m p_m = m-1. $$ Indeed, the LHS counts the expected number of points which are not fixed by the permutation, and each individual point is not fixed with probability $(m-1)/m$. In any case, it follows from the previous two equations that $t_m = m$ by induction: $$ t_m - t_m p_m = 1 + 0 p_0 + \cdots (m-1)p_{m-1} = m - mp_m. $$ (Note $p_m<1$.) So for $m=10$, $\mathbf{E}(T) = 10$.

Answer 2

Here is an argument that shows that the expected number of drinks is $m^2/2$ for $m>1$, as noted by Barry Cipra. This is equivalent to saying that the expected number of drinks that an arbitrary person $A$ takes is $m/2$. Let $X_m$ be the expected number of drinks per person with $m$ participants. If $m\geq 2$, we get the equation $$X_m = \frac{m-1}m\left(1+a_2X_2+\cdots + a_mX_m\right),$$ where the factor $(m-1)/m$ is the probability that person $A$ picks somebody else's umbrella in the first round (otherwise he drinks nothing), the term 1 comes from the drink this causes him to take, and $a_k$ is the probability of exactly $k$ people picking someone else's umbrella in the first round, conditioning on $A$ doing so (trivially $a_0 = a_1 = 0$).

Since $a_m(m-1)/m\neq 1$, this equation uniquely determines $X_m$ if we know $X_2,\dots,X_{m-1}$. Therefore we have the right to commit the cardinal sin of assuming that the induction step does go through, and just check that the resulting equation is consistent!

Provided $X_k=k/2$ (linear!) for $k=2,\dots,m$, we can replace the terms $a_2X_2+\cdots + a_mX_m$ by $(m-1+1/(m-1))/2$, since the expected number of people who take their own umbrella, given that $A$ doesn't, is $1-1/(m-1)$ (it is 2 if he does). The equation then reads $$\frac{m}2 = \frac{m-1}m\left(1+\frac{m-1+\frac1{m-1}}{2}\right),$$ which simplifies to...I can't resist... $$0 = 0, \qquad \text{QED}.$$

Answer 3

This is essentially the same answer as Sean Eberhard's, without the rigor:

When you parcel out $m$ umbrellas to $m$ men, each man has a $1/m$ chance of getting his own umbrella, so the expected number of correctly matched umbrellas is $m \times 1/m = 1$. Hence on average one man (and his own umbrella) goes home each round. So if you start with $m$ men, it'll take, on average, $m$ rounds to empty the bar.

The expected number of drinks consumed appears to be $m^2/2$ (for $m>1$), but I don't have a clever derivation for this. Anybody?

Answer 4

Hello,

This seems to involve Rencontres numbers $D_{n,r}$, the number of permutations in symmetric group $S_n$ with $r$ fixed points, for example, see OEIS Rencontres numbers or this post, The number of cycles in a random permutation, in the blog of Professor Tao.

Let $P_n$ be the set of partitions of $10$ into $n$ (not necessarily distinct and not necessarily non-zero) components, where order matters. I.e,

$$ P_n = \{(a_1,a_2,\dots,a_n): \sum_{i}a_i = 10, 0 \leq a_i \leq 10\}. $$

Then the probability that $T=n$ is

$$ P(T=n) = \sum_{\pi = (a_i)\in P_n}\left(\frac{D_{10,a_1}}{10!}\right)\left(\frac{D_{10-a_1,a_2}}{(10-a_1)!}\right)\dots\left(\frac{D_{10-a_1-\dots-a_{n-1},a_n}}{(10-\sum_{i=1}^{n-1}a_i)!}\right). $$