Expected Time Until One Shopping-Cart Line Becomes Empty

Quick Overview

Compute shopping-cart redistribution absorption time with a lazy random walk, including no-change rounds and a quadratic expected-time recurrence.

Expected Time Until One Shopping-Cart Line Becomes Empty

Company: DRW

Role: Quantitative Researcher

Category: Statistics & Math

Difficulty: medium

Interview Round: Online Assessment

Two lines initially contain 6 and 7 shopping carts. In each round, choose one line uniformly, remove one cart, and return that cart to an independently uniformly chosen line. Stop when either line is empty at the end of a round. Find the expected number of rounds. ### Clarifying Questions to Ask - Is the destination line chosen independently of the source? - Can a cart return to the same line, leaving the state unchanged? ```hint Include rounds with no net movement The number of carts in one line performs a random walk with a self-loop, not an ordinary always-moving walk. ``` ### What a Strong Answer Covers - States 0 through 13 and absorbing boundaries. - Probabilities 1/4, 1/2, 1/4 for decreasing, staying, and increasing. - A second-difference recurrence or equivalent lazy-walk argument. ### Follow-up Questions - How would the answer change if a removed cart always went to the other line? - What is the formula for initial split i and N-i?

Overview: Compute shopping-cart redistribution absorption time with a lazy random walk, including no-change rounds and a quadratic expected-time recurrence.

Read the full DRW Quantitative Researcher interview experience this question came from

DRW logo
DRW
Nov 21, 2026
mediumQuantitative ResearcherOnline AssessmentStatistics & Math
0
0

Two lines initially contain 6 and 7 shopping carts. In each round, choose one line uniformly, remove one cart, and return that cart to an independently uniformly chosen line. Stop when either line is empty at the end of a round. Find the expected number of rounds.

Clarifying Questions to Ask Guidance

  • Is the destination line chosen independently of the source?
  • Can a cart return to the same line, leaving the state unchanged?

What a Strong Answer Covers Guidance

  • States 0 through 13 and absorbing boundaries.
  • Probabilities 1/4, 1/2, 1/4 for decreasing, staying, and increasing.
  • A second-difference recurrence or equivalent lazy-walk argument.

Follow-up Questions Guidance

  • How would the answer change if a removed cart always went to the other line?
  • What is the formula for initial split i and N-i?