# Hard Question in Stochastic processes - variance Martingales

I got some hard challenge to solve and I am looking for a small clue/help.

My question goes like this:

10 Englishmen are trying to leave a pub in a rainy weather. They do it in the following way. Initially they store all 10 umbrellas in a basket next to the exit from the pub. They enter and drink a pint each. Then they return to the basket and each one picks an umbrella at random (random permutation). Those who picked their own umbrellas leave upset, while those who did pick a wrong umbrella, put it back and return to the pub for another pint of ale. After that they return to the basket and try once again. And so on.

Let $T$ be the number of rounds needed for all Englishmen to leave, and let $N$ be the total number of ales consumed during the procedure.
(a) Compute $E(T)$.
(b) Compute $E(N)$.

Hint: For $n = 0, 1, 2, \dots$, set $X_n$ to be the number of Englishmen in the pub after $n$-th round, and consider $M_n = (X_n + n) 1_{\{n<T\}}.$ To solve (b) think about variance martingales.

Any hint? Also, What are variance martingales and how they help here?

Thanks a lot.

• – shai horowitz May 22 '16 at 23:41
• a Martingale, stated as a bayes, is a prior that you have 100% certainty so it can't change. i.e. a known fair roulette real roles 6 reds in a row. what's the probability of the next being red? or a fair coin that is known fair that flips heads 20 times in a row what's the probability of the next being heads well its exactly (1÷2) – shai horowitz May 22 '16 at 23:51
• math.stackexchange.com/a/1794499/339356 this is brilliant – shai horowitz May 23 '16 at 2:29
• Let w and b be the number of white and black balls initially in the urn, and w+n_w the number of white balls currently in the urn after n draws. Then the sequence of values $\frac{w+n_w}{w+b+n}$ for n=1,2,3,...is a normalized version of the Beta-binomial distribution. It is a martingale and converges to the beta distribution when n → ∞. do you think I need to somehow use this beta binomial distribution (I know what a martingale is btw) – Lambda87 May 23 '16 at 6:34

## 1 Answer

In addition to the hints, we need the following identities related to derangements:

(1) $\displaystyle\sum_{i=0}^{n}\frac{!i}{i!~(n-i)!}=1,~(n\ge0),$

(2) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)}{i!~(n-i)!}=1,~(n\ge1),$

(3) $\displaystyle\sum_{i=0}^{n}\frac{!i~(n-i)~(n-i-1)}{i!~(n-i)!}=1,~(n\ge2),$

where I have adopted the subfactorial notation. The proof of (1) is by considering among all the possible permutations of $n$ distinct items, what the probability $p^{(n)}_{i}$ is of a random permutation in which exactly $n-i$ items are in their original ordered positions. It's easy to see $p^{(n)}_{i}$ is exactly the term within the summation. For (2), note we can change the upper bound of summation to $n-1$, cancel the $n-i$ term in the numerator with the factorial in the denominator then apply (1) by replacing $n$ with $n-1$. Similar proof for (3). We can now rewrite these identities as:

(1') $\sum_{i=0}^{n}p^{(n)}_{i}=1,~(n\ge0),$

(2') $\sum_{i=0}^{n}p^{(n)}_{i}i=n-1,~(n\ge1),$

(3') $\sum_{i=0}^{n}p^{(n)}_{i}i^2=(n-1)^2+1,~(n\ge2),$

where we have used (1) and (2) to get (2') and (1), (2) and (3) to get (3').

(a) Follow your hints, we use first step analysis on $X_n$:

$\mathbb{E}\left[X_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i=X_n-1,$

where $n<T$, i.e., $X_n>=2$. Therefore $(X_n+n)1_{n<T}$ is a martingale and by applying the optional stopping theorem, we get $\mathbb{E}[T]=X_0=10$, as $X_T=0$ is the stopping condition.

(b) I believe the hint is to consider the variance of $X_n$. We apply first step analysis on $X^2_n$:

$\mathbb{E}\left[X^2_{n+1}\mid X_n\right]=\sum_{i=0}^{X_n}p^{(X_n)}_{i}i^2=(X_n-1)^2+1.$

We also have

$\mathbb{E}\left[Y_{n+1}\mid Y_n,X_n\right]=Y_n+X_n,$

where $Y_n$ is the total number of ales consumed after $n$th round. Therefore $(Y_n+X^2_n/2+X_n)1_{n<T}$ is a martingale and $\mathbb{E}[N]=\mathbb{E}[Y_T]=X^2_0/2+X_0=60$.

• thanks for your comment. I think some steps are missing ( I dident get 3' as you did) do you know the solution from somewhere? If you have more detailed solution i'll be happy to see it. thanks a lot anyway. you helped me very much. – Lambda87 May 25 '16 at 7:07
• Do you agree with (3)? If so, just expand $(n-i)(n-i-1)=n(n-1)-(2n-1)i+i^2$, then split the sum into 3 terms. Use (1) for 1st, (2) for 2nd, then you get (3'). – Wiley May 25 '16 at 17:47