Men in a bar - stoch. processes

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

-
Exercise? Homework? – Yemon Choi Jan 18 '12 at 7:32
Rencontres numbers! – Timothy Foo Jan 18 '12 at 7:35
Imagine what happens if at some point somebody by mistake leaves with someone else's umbrella. What a nightmare. – Johan Wästlund Jan 18 '12 at 10:10
@Johan: Your comment made my day. – Liviu Nicolaescu Jan 18 '12 at 13:19
I read this as "Men in a bar - scotch processes". – Tom Church Jan 18 '12 at 19:13

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$.

-
Dear Sean, thank you for this wonderful answer. It helps me very much. Unfortunately I don't understand how to get a precise derivation of the first formula. Could you help me there again? – Peter Jan 20 '12 at 8:38
It follows from en.wikipedia.org/wiki/Law_of_total_expectation. Suppose there are $m$ men remaining, and that they all go to fetch their umbrellas. This adds 1 to the rounds-count, hence the initial 1. After the round, with probability $p_k$, there are exactly $k$ men remaining, and the expected number of rounds to get rid of them all is $t_k$. – Sean Eberhard Jan 20 '12 at 18:06

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}.$$

-
Johan, very nice! There ought to be a slick argument along the lines of, If the process sends one man home per round on average and hence takes, on average, $m$ rounds to empty the bar, then the average tippler survives (to drink again) through $m/2$ rounds, for a total, on average, of $m \times m/2$ drinks. But that just feels like it's playing too fast and loose with the law(s) of averages. – Barry Cipra Jan 19 '12 at 15:24

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?

-

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).$$

-