Dodgy Lift 2

Probability Level 5

You are on the 3rd/top floor of a building and you wish to ride the elevator to the 0th/ground floor. Unfortunately the elevator is dodgy. You enter the lift and the doors behind you close. The lift then proceeds to:

Move up 1 floor.
Move down 1 floor.
Shake violently and then Open the doors.

Each movement lasts 10 seconds and at each floor each possible movement occurs with equal probability. (e.g. the first operation is either the opening of the lift, or moving down 1 floor, each with probability 0.5).

Let $P$ be the probability that the first time the doors open you are on the ground floor.

The doors end up opening first on the ground floor.

Let $E$ be the expected amount of time taken in minutes.

If $P = \frac{a}{b}$ for coprime $a,b$ , and $E = \frac{c}{d}$ for coprime $c,d$ .

Find $a + b + c + d$ .

Also see Dodgy Lift 1

The answer is 39.

2 solutions

Mark Hennings
Jun 4, 2019

Let $T$ be the number of times the lift has to move before the door opens, and let $G$ be the event that the door opens at floor 0. After an even number of moves, the lift must be at either floor 1 or floor 3. There are two ways the lift can go from floor 1 to floor 1 in two moves (1-0-1 and 1-2-1), while there is just one way of going from floor 1 to floor 3 in two moves (1-2-3) and one way of going from floor 3 to floor 1 in two moves (3-2-1) and just one way of going from floor 3 to floor 3 in two moves (3-2-3). Suppose that $p_n$ is the probability that the lift is at floor 1 after $2n$ moves (and the doors are still shut), and suppose that $q_n$ is the probability that the lift is at floor 3 after $2n$ moves (and the doors are still shut). Then $\left(\begin{array}{c} p_{n+1} \\ q_{n+1}\end{array}\right) \; = \; \left(\begin{array}{cc} \tfrac{5}{18} & \tfrac{1}{6} \\ \tfrac{1}{9} & \tfrac{1}{6}\end{array}\right)\left(\begin{array}{c} p_n \\ q_n \end{array}\right)$ Since this matrix has eigenvectors $\mathbf{v}_\pm \; = \; \left(\begin{array}{c} 3 \\ \pm\sqrt{7} - 1\end{array}\right)$ with associated eigenvalues $\lambda_\pm \;=\; \tfrac{1}{18}(4 \pm \sqrt{7})$ and since $\binom{p_0}{q_0} \,=\, \binom{0}{1}$ we deduce that $\left(\begin{array}{c} p_n \\ q_n\end{array}\right)\; = \; \tfrac{1}{2\sqrt{7}}\left[\lambda_+^n\mathbf{v}_+ - \lambda_-^n\mathbf{v}_-\right]$ and so, in particular $p_n \; = \; \tfrac{3}{2\sqrt{7}}\left[\lambda_+^n - \lambda_-^n\right]$ The doors can only open at floor $0$ if the lift has moved an odd number (greater than $1$ ) of times, and we note that $P[(T = 2n+1) \cap G] \; = \; p_n \times \tfrac13 \times \tfrac12 \; = \; \tfrac{1}{4\sqrt{7}}\left[\lambda_+^n - \lambda_-^n\right]$ (the lift has to be at floor 1 after $2n$ moves, with the doors shut, then it must move to floor 0, and the doors must open). Thus $P \; = \; P[G] \; = \; \sum_{n=1}^\infty P[(T=2n+1) \cap G] \; = \; \tfrac{1}{21}$ and hence $P[T=2n+1|G] \; = \; \tfrac{21}{4\sqrt{7}}\big[\lambda_+^n - \lambda_-^n\big] \hspace{2cm} n \ge 1$ while $P[T=m|G] = 0$ for all other integers $m$ . Thus $E[T|G] \; = \; \tfrac{21}{4\sqrt{7}}\sum_{n=1}^\infty (2n+1)\big[\lambda_+^n - \lambda_-^n\big] \; = \; \tfrac{13}{3}$ Assuming that it takes a further $10$ seconds for the lift doors to open, we deduce that $E \; = \; \tfrac16(E[T|G] + 1) \; = \; \tfrac89$ making the answer $1 + 21 + 8 + 9 = \boxed{39}$ .

I've been looking myself, but haven't been able to find a general form for a lift that goes up to the $n^{th}$ floor, for the probability part. I have a general form for the expected value, but I don't have a proof. Fancy helping me looking into this?

Alex Burgess - 2 years ago

Suppose we have $N+1$ floors labelled $0,1,2,...,N$ . Let $p_n$ be the probability that the doors open on the ground floor ( $0$ th floor), given that the lift is currently at the $n$ th floor, and the doors are still shut. Then we have the recurrence relation $p_j \; = \; \tfrac13(p_{j-1} +p_{j+1}) \hspace{2cm} 1 \le j \le N-1$ together with the boundary conditions $p_0 \; = \; \tfrac12 + \tfrac12p_1 \hspace{2cm} p_N \; = \; \tfrac12p_{N-1}$ This is an easy enough recurrence relation to solve. What is nice is that we can then use Binet's Formula to deduce that $p_j \; = \; \frac{F_{2N-2j+1}}{F_{2N+2}} \hspace{2cm} 0 \le j \le N$ In particular we have $P \; =\; p_N \; = \; \frac{1}{F_{2N+2}}$ which matches the results of your two questions ( $\tfrac18$ when $N=2$ , and $\tfrac{1}{21}$ when $N=3$ ). I haven't worked it through yet, but I expect that we should be able to calculate $E$ by calculating the expected first hitting time of a Markov chain.

Mark Hennings - 2 years ago

Oh nice!

I tried to do it with hitting times, but I couldn't modify to work for the a problem with multiple sinks.

I believe I got that $E(N) = \frac{4(N+1)}{3}$ , which seems to hint that there should be a nice solution.

Alex Burgess - 1 year, 12 months ago

@Alex Burgess – I am afraid I do not agree with your formula of $\tfrac43(N+1)$ . It works for $N=1,2,3$ , but not beyond.

Let $X$ be the number of lift operations until the door opens, and let $G$ be the even that the door opens at the ground floor. Let $T_0$ be the starting floor of the lift, and define $Q_{k,j} \; = \; P[(X = k) \cap G \,|\, T_0=j] \hspace{2cm} k \ge 1\,,\,0 \le j\le N$ Note that $\sum_{k \ge 1} Q_{k,j} \; = \; P[G|T_0=j] \; = \; p_j \hspace{2cm} 0 \le j \le N$ Conditional probability thoughts tell us that $Q_{1,j} = \tfrac12\delta_{j,0}$ for $0 \le j \le N$ , while $Q_{k,j} \; = \; \left\{ \begin{array}{lll} \tfrac13[Q_{k-1,j+1} + Q_{k-1,j-1}] & \hspace{1cm} & 1 \le j \le N-1 \\ \tfrac12Q_{k-1,1} & & j = 0 \\ \tfrac12Q_{k-1,N-1} & & j = N \end{array}\right.$ for $k \ge 2$ . If we define $E_j \; = \; \sum_{k=1}^\infty kQ_{k,j} \hspace{2cm} 0 \le j \le N$ then it follows from the above that $E_j \; =\; \tfrac13(E_{j+1} + E_{j-1}) + p_j \hspace{2cm} 1 \le j \le N-1$ while $E_0 \; = \; \tfrac12E_1 + p_0 \hspace{2cm} E_n \; = \; \tfrac12E_{N-1} + p_N$ The general solution of the recurrence relation $E_j \; = \; \tfrac13(E_{j+1} + E_{j-1}) + p_j \hspace{2cm} 1 \le j \le N-1$ is $E_j \; = \; \frac{3j}{5F_{2N+2}}L_{2N-2j+1} + \alpha L_{2N-2j+1} + \beta F_{2N-2j+1} \hspace{2cm} 0 \le j \le N$ for some constants $\alpha,\beta$ (using the Fibonacci numbers and the Lucas numbers). To ensure that $E_N = \tfrac12E_{N-1} + p_N$ we require that $\alpha \; = \; \frac{1-3N}{5F_{2n+2}}$ To additionally ensure that $E_0 = \tfrac12E_1 +p_0$ we require $\beta \; = \; \frac{3NL_{2N+2} + 4L_{2N+1}}{5F_{2N+2}^2}$ which leads to the result $E \; = \; E[X|G \cap (T_0=N)] \; = \; \frac{E_N}{p_N} \; = \; \frac{3NL_{2N+2} + 4L_{2N+1} + F_{2N+2}}{5F_{2N+2}}$ which agrees with the expression $\tfrac43(N+1)$ for $N=1,2,3$ , but not thereafter.

Mark Hennings - 1 year, 12 months ago

@Mark Hennings – Thanks. I had only run some simulations up to $N = 10$ , but was only able to run it about $10^9$ times, so with the $p_N$ being so small, the results seemed to vary quite a bit, so I had assumed the formula based on the first 3 following the pattern. At $N=10$ it only differed by $0.06$ which was beyond the accuracy of the program.

I was trying to convince myself that $E_j = \frac{1}{3}( E_{j+1} + E_{j-1} ) + p_j$ made intuitive sense yesterday, but didn't get any further.

How did you get to the general solution? I worked through the first one with $p_j$ , and whilst it wasn't particularly hard, it was rather long with the method I was using, even when using $\phi^2 and \phi^{-2}$ .

That seems than even crazier solution than $F_N$ popping up in the probabilities.

Alex Burgess - 1 year, 12 months ago

@Alex Burgess – To obtain the recurrence relations, note that, for $1 \le j \le N-1$ , $\begin{aligned} E_j & = \; \sum_{k \ge 1} kQ_{k,j} \; = \;\sum_{k\ge 2}kQ_{k,j} \; = \; \sum_{k \ge 2}\tfrac13k[Q_{k-1,j+1} + Q_{k-1,j-1}] \\ & = \; \tfrac13\sum_{k \ge 1}(k+1)[Q_{k,j+1}+Q_{k,j-1}] \; = \; \tfrac13(E_{j+1}+E_{j-1}) + \tfrac13\sum_{k\ ge 1}[Q_{k,j+1} + Q_{k,j-1}] \\ & = \; \tfrac13(E_{j+1} + E_{j-1}) + \tfrac13(p_{j+1}+p_{j-1}) \; = \; \tfrac13(E_{j+1}+E_{j-1}) + p_j \end{aligned}$ for example.

Since $L_{n+2} + L_{n-2} = 3L_n$ and $F_{n+2} + F_{n-2} = 3F_n$ for all $n$ , the general solution of the recurrence relation $E_j \; = \; \tfrac13(E_{j+1} + E_{j-1}) \hspace{2cm} 1 \le j \le N-1$ is $E_j \; = \; \alpha L_{2N-2j+1} + \beta F_{2N-2j+1} \hspace{2cm} 0 \le j \le N$ To solve the nonhomogenous recurrence relation, we need a "particular integral". The one I gave follows from the known formula for $p_j$ and the fact that $L_{n+2} - L_{n-2} = 5F_n$ for all $n$ .

Of course, my general solution for $E_j$ could have been expressed (perhaps more naturally) in terms of $F_{2j}$ and $L_{2j}$ , but the known form of $p_j$ led to the $F_{2N-2j-1}$ type of terms.

We can apply the same approach to obtaining the basic formula for $p_j$ . Since the $p_j$ satisfy the basic homogenous recurrence relation, we know that $p_j \; = \; \gamma L_{2N-2j+1} + \delta F_{2N-2j+1} \hspace{2cm} 0 \le j \le N$ and the boundary conditions $p_N = \tfrac12p_{N-1}$ and $p_0 = \tfrac12 + \tfrac12p_1$ can be used to deduce that $\gamma =0$ and $\delta = F_{2N+2}^{-1}$ .

Mark Hennings - 1 year, 12 months ago

@Mark Hennings – Wow, that's pretty cool.

Alex Burgess - 1 year, 12 months ago

Alex Burgess
Jun 3, 2019

Let $P_n$ be the probability the door opens first on the ground floor | given that you are currently on the $n^{th}$ floor.

$\begin{matrix} P_3 &=&\frac{1}{2} P_2&+&(\frac{1}{2} 0)\\ P_2 &=&\frac{1}{3} P_3 &+&\frac{1}{3} P_1&+&(\frac{1}{3} 0) \\ P_1 &=&\frac{1}{3} P_2 &+&\frac{1}{3} P_0&+&(\frac{1}{3} 0) \\ P_0 &=&\frac{1}{2} P_1&+&\frac{1}{2} 1\\ \end{matrix}$

Hence,

$\begin{matrix} P_2 &=&\frac{1}{6} P_2 &+&\frac{1}{3} P_1 \\ P_1 &=&\frac{1}{3} P_2 &+&\frac{1}{6} P_1&+&\frac{1}{6} \\ \end{matrix}$

So,

$5 P_2 = 2 P_1$ ,

$5 P_1 = 2 P_2 + 1$ .

$25 P_2 = 10 P_1 = 4 P_2 + 2$

Therefore,

$P_2 = \frac{2}{21}$ , and $P = P_3 = \frac{1}{21}$ .

The expected amount of lift operations is $\frac{16}{3}$ .

Hence, $E = \frac{160}{180} = \frac{8}{9}$ .

$a + b + c + d = 1 + 21 + 8 + 9 = 39$ .

Dodgy Lift 2

The answer is 39.

2 solutions

0 pending reports