Katkat
Back

Solve probability and expectation problems

OptiverData Scientist · Online Assessment
HardData ScientistOnline AssessmentStatistics & Math

Last updated

This problem tests your ability to calculate expected stopping times in a discrete random walk and your understanding of conditional expectation and symmetry in probability.

Part 1: The Asymmetric Gambler

Consider a gambler starting with $0$ dollars. In each round, they win $1$ dollar with probability $p$ and lose $1$ dollar with probability $q = 1-p$. The game stops when the gambler reaches either $N$ dollars (a win) or $-M$ dollars (a loss), where $N, M > 0$. Calculate the probability of the gambler reaching $N$ before $-M$.

Part 2: Expected Time

Assume $p = q = 0.5$ (a symmetric walk). Let $E[T]$ be the expected number of rounds until the gambler reaches either $N$ or $-M$. Derive a formula for $E[T]$ in terms of $N$ and $M$.

Example

For Part 1: If $p=0.5$, $N=2$, and $M=2$, the probability of reaching $2$ before $-2$ is $0.5$. For Part 2: If $N=2$ and $M=2$, the expected number of steps $E[T]$ is $4$.

Constraints

  • $p, q$ are constants such that $p+q=1$.
  • $N, M$ are positive integers.
  • Show your derivation for the general case.

Hints

Hint 1

For Part 1, let $P_i$ be the probability of reaching $N$ starting from $i$. Set up a recurrence relation $P_i = p P_{i+1} + q P_{i-1}$ with boundary conditions $P_{-M} = 0$ and $P_N = 1$.

Hint 2

For Part 2, define $E_i$ as the expected time to reach the boundaries starting from $i$. The recurrence is $E_i = 1 + 0.5 E_{i+1} + 0.5 E_{i-1}$ with $E_{-M} = 0$ and $E_N = 0$.

Hint 3

Consider using the property of martingales or recognizing that $E_i = -i^2 + C_1 i + C_2$ satisfies the second-order linear recurrence for the symmetric case.

Follow-up questions

  • How does the probability change if the gambler is allowed an infinite number of rounds but $p < q$?
  • If the game is modified such that the gambler can choose to stop at any time $k < T$ to collect their current winnings, what is the optimal stopping strategy?
  • How would you approach this problem if the step sizes were not fixed at $+1$ or $-1$, but were instead drawn from a distribution with mean $\mu$ and variance $\sigma^2$?