Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You are in a corridor which has N doors all of the doors are opened. Every time someone passes through the corridor, he closes randomly with equal probability a certain number of doors between 1 and the number of remaining opened doors. What is the expected number of people that need to pass before all the doors are closed? What about when they instead close 0 to N doors each time rather than 1 to N?

So currently I have:

Let $P_N$ = number of people needed to close N doors.

$$E(P_N) = 1 + \frac{1}{N}(\sum\limits_{i=1}^N E(P_{N-i}))$$

Since you add 1 for the one guy coming through, and then since each amount of doors happens of equal probability its just that summation term times the probability of each event happening (which is $1/N$).

I'm not quite sure how to continue to simplify this though...

Thanks for any help.

share|improve this question
1  
Have you tried working out the cases with 1, 2, 3 doors? –  Mark Bennet Jun 30 '12 at 19:38
    
This question looks related (although in a loose way): math.stackexchange.com/questions/164384/… –  D. Thomine Jun 30 '12 at 20:01
1  
You already did most of the work. Write down $E[P_{N-1}]$ and try to use both equations to cancel out the summation. –  madprob Jun 30 '12 at 20:02
add comment

1 Answer

up vote 4 down vote accepted

It is probably easier to write your expression as

$$E_N = 1 + \frac{1}{N}\sum\limits_{i=0}^{N-1} E_i$$ starting at $E_0=0$. This is the same as

$$N E_N = N + \sum\limits_{i=0}^{N-1} E_i.$$ But you also have

$$(N-1) E_{N-1} = N-1 + \sum\limits_{i=0}^{N-2} E_i$$ and taking the difference and tidying up gives a simple expression for $E_N - E_{N-1}$ and thus a known sequence for $E_N$.

For your alternative question you instead start with $$A_N = 1 + \frac{1}{N+1}\sum\limits_{i=0}^{N} A_i$$ and proceed in a similar way to get a similar but slightly different result. It is worth working $A_1$ out explicitly as you cannot calculate $\frac00$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.