Expected Stopping Time of a Random Walk, by Simulation

"A walk starts at zero and stops at plus three or minus two. How long does it take on average?" is a staple of the trading interview, and the verbal answer is gambler's ruin. The follow-up is to check it by simulation, and what it tests is whether you can simulate a stopping time without a Python loop over steps. The same walk describes an inventory position that moves one lot at a time until it hits a risk limit on either side.

Implement expected_exit_time(up, down, p_bp, n_paths, seed).

• up and down: positive integers. The walk starts at level 0 and stops the first time it reaches +up or -down.
• p_bp: the probability of a +1 step in basis points, so each step is +1 with probability \( p = p_{bp} / 10000 \) and -1 otherwise.
• n_paths: how many independent paths to simulate.
• seed: the RNG seed.

Return (mean_exit_time, probability_of_exiting_up), both rounded to 4 decimals: the average number of steps a path took before it stopped, and the fraction of paths that stopped at +up.

The exact random stream matters, so follow this procedure. Create the generator with numpy.random.default_rng(seed). All paths start at level 0 and are live. While any path is live, let \( m \) be the number of live paths and draw one block rng.random((m, up + down)) < p in a single call: one row per live path, in index order, where True is a step of +1 and False a step of -1. Add the cumulative sum of each row to that path's current level. A path whose level reaches up or more, or -down or less, at some step of the block stops at the first such step: its exit time is the total number of steps it has taken, and it exits up if the level it stopped at is up. A path that reaches neither boundary keeps its level after the last step of the block and stays live for the next draw. Draw nothing for a path that has stopped.

Examples

expected_exit_time(3, 2, 5000, 20000, 1)
# (5.9588, 0.4023)

expected_exit_time(5, 5, 5500, 20000, 7)
# (23.0908, 0.7325)

The first is the symmetric walk from the opening question: gambler's ruin says exactly \( 3 \times 2 = 6 \) steps and a probability of \( 2 / 5 \) of exiting up. The second has a 55 percent drift up, which shortens the walk and tilts the exit.

Constraints

• \( 1 \le up, down \le 50 \), \( 0 \le p_{bp} \le 10000 \) and \( 1 \le n_{paths} \le 2 \times 10^5 \). At \( p_{bp} = 0 \) or \( 10000 \) the walk is a straight line and still stops.
• Round with round(float(x), 4) so the result is a plain Python float.
• A loop over steps in pure Python is the wrong shape: the hidden performance case runs 200,000 paths between boundaries 20 apart, about 80 million steps in total. A loop over blocks, vectorised over paths, finishes in under a second. A solution that draws its steps in any other order gets a valid estimate and the wrong digits.