On average, where is the lift?

Question

This started as a computing problem with several variables, and I'd like to know if there's a closed form formula for the average position of the lift.

Context: there's a building with $N$ floors and $m$ people distributed randomly across them. If a person is on the floor where they live, they will take the lift to go straight down (no stopping) to the ground floor, and vice-versa.

At each step, one person is randomly selected and makes their move. At each step, then, the lift moves either once (already on the floor it's called from) or twice (goes to pick up the person first, then makes the requested move). Each new position of the lift is recorded.

On randomness: since this was first a question about a script in Python, the random.randint() method was used, where the documentation states

Almost all module functions depend on the basic function random(), which generates a random float uniformly in the semi-open range $[0.0, 1.0)$. Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of $2^{19937}-1$.

Question: after $k$ iterations, the algorithm stops and returns the average $\mathcal{A}$ of the recorded positions of the lift. Is it possible to predict either $\lim\limits_{k\to\infty}\mathcal{A}(N,m)$ or $\mathcal{A}(N,m,k)$?

Answer 1

It is difficult to interpret the question exactly, but one approach might be to say:

Each time the lift starts on the ground floor, with probability $\frac12$, or on a higher floor

• conditioned on the lift starting at the ground floor

  • with conditional probability $\frac1{2}$ the lift immediately picks up an ascending passenger and goes to one of the $N$ higher floors, recording this as a single new position at the higher floor
  • with conditional probability $\frac1{2}$ the lift ascends to one of the $N$ higher floors, and picks up a descending passenger and goes to the ground floor, recording this as two new positions at the higher floor and the ground floor

• conditioned on the lift starting at one of the $N$ higher floors

  • with conditional probability $\frac1{2N}$ the lift immediately picks up an descending passenger and goes to the ground floor, recording this as a single new position at the ground floor
  • with conditional probability $\frac{N-1}{2N}$ the lift moves to one of the $N-1$ other floors (not ground) and picks up a descending passenger and goes to the ground floor, recording this as two new positions at the new floor and the ground floor
  • with conditional probability $\frac1{2}$ the lift moves to the ground floor and picks up an ascending passenger and goes to one of the $N$ higher floors, recording this as a two new positions at the ground floor and the new higher floor

So the expected number of times per passenger that the lift records the ground floor is $\frac12 \times \frac1{2N} \times N + \frac1{2N}\times N = \frac34$, while the expected number of times per passenger that the lift records a higher particular floor is $\frac1{N} \times \left(\frac12 +\frac1{2}\times (\frac{N-1}{2N}+\frac{N}{2N})\right) =\frac{1}{N}-\frac1{4N^2}$

Thus, in a law of large numbers sense and taking account of the $m$ passengers each time, the limit of the average should be $\frac34 m$ positions recorded for the ground floor and $\left(\frac{1}{N}-\frac1{4N^2}\right)m$ visits recorded for each of the other floors.

As a check, when $N=1$ this gives $\frac34m$ each for recorded visits for the ground floor and the only higher floor, which makes sense from a symmetry argument.