Compute winning probability on 1D dice walk

Q: Compute winning probability on 1D dice walk

This question evaluates understanding of probability theory and discrete stochastic processes, specifically reasoning about random walks and event probabilities over (potentially infinite) state spaces.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are on an infinite 1D number line starting at position 0. Repeatedly roll a fair die that returns an integer uniformly at random from 1 to K (inclusive), and move forward by that many steps.

You win if you ever land on a position within the target interval $[mn, mx]$ (inclusive). You lose if you jump past the interval, i.e., your position becomes $> mx$ without ever landing in $[mn, mx]$ .

Given integers $K$ , $mn$ , and $mx$ (with $1 \le mn \le mx$ ), compute the probability of winning starting from position 0.

Return the probability as a floating-point value (or as an exact fraction if you prefer), with acceptable error $\le 1e{-6}$ .

Compute winning probability on 1D dice walk

Quick Overview

Comments (0)