Katkat
Back

Expected Rounds Until a Shopping-Cart Line Empties Under Random Transfers

DRWQuantitative Researcher · Onsite
HardQuantitative ResearcherOnsiteStatistics & Math

Last updated

Tests modeling discrete-time Markov chains, formulating hitting-time difference equations, and solving symmetric random walk absorption problems analytically.

Problem Description

A retail store has two parallel checkout queues for returned shopping carts, Line A and Line B. Initially, Line A holds 6 carts and Line B holds 7 carts, for a total of 13 carts.

At each discrete round t = 1, 2, ...:

  1. A source line is selected uniformly at random from {Line A, Line B}.
  2. A destination line is selected uniformly at random from {Line A, Line B} independently of the source.
  3. If the source line and destination line differ, exactly one cart is transferred from the source line to the destination line.
  4. If the source line and destination line are identical, the selected cart stays in place (a self-transfer occurs), and the round still counts.

The process halts immediately as soon as either line has 0 carts remaining.

Questions to Answer

  1. Markov Chain Formulation: Define the state of the system as the number of carts in Line A, denoted by k. Identify the state space, the transition probabilities between states, and the absorbing states.
  2. Expected Hitting Time: Let E[k] be the expected number of rounds until the process terminates, given that Line A currently holds k carts (with total carts N = 13). Write down the recurrence relation satisfied by E[k] along with its boundary conditions.
  3. Closed-Form Derivation: Solve the recurrence relation for general N and starting state k.
  4. Numerical Evaluation: Compute the exact expected number of rounds until one of the lines empties given the starting state of 6 carts in Line A and 7 carts in Line B.
  5. Absorption Probability: Compute the probability that Line A empties before Line B.

Hints

Hint 1

Define the state by the number of carts in Line A, noting that the total number of carts N = 13 is invariant throughout the process.

Hint 2

Formulate the first-step analysis equation for E[k], accounting for the 1/2 probability of staying in the same state due to self-transfers.

Hint 3

The resulting second difference equation E[k+1] - 2*E[k] + E[k-1] = -4 has boundary conditions E[0] = 0 and E[N] = 0, suggesting a quadratic solution of the form C * k * (N - k).

Follow-up questions

  • How does the expected hitting time change if the cart to transfer is chosen uniformly at random from all remaining carts (Ehrenfest model) rather than selecting the line uniformly?
  • If self-transfers are disallowed (i.e., a cart must strictly move to the other line each round), how does the expected number of rounds scale?
  • What is the conditional expected number of rounds to absorption given that Line A is the one that empties first?