Win rates at first-passage times for biased simple random walks
Abstract
We study the win rate $R_{N_d}/N_d$ of a biased simple random walk $S_n$ on $\mathbb{Z}$ at the first-passage time $N_d=\inf\{n\ge 0:S_n=d\}$, with $p=P[X_1=+1]\in[1/2,1)$. Using generating-function techniques and integral representations, we derive explicit formulas for the expectation and variance of $R_{N_d}/N_d$ along with monotonicity properties in the threshold $d$ and the bias $p$. We also provide closed-form expressions and use them to design unbiased coin-flipping estimators of $π$ based on first-passage sampling; the resulting schemes illustrate how biasing the coin can dramatically improve both approximation accuracy and computational cost.
Summary
This paper investigates the win rate of a biased simple random walk on the integers at the first-passage time to a target level *d*. The research focuses on understanding the statistical properties of the win rate *R_N_d / N_d*, where *R_N_d* is the number of positive steps taken until the random walk reaches level *d* at time *N_d*. The authors use generating-function techniques and integral representations to derive explicit formulas for the expectation and variance of the win rate. They also explore monotonicity properties with respect to the bias *p* and the target level *d*. A key application of these theoretical results is the design of unbiased coin-flipping estimators for approximating π and ln(2). The paper demonstrates how biasing the coin (adjusting *p*) can significantly improve both the approximation accuracy and the computational cost of these estimators. The motivation for this work stems from the need to quantify the bias introduced by "stop upon success" rules in sequential procedures. Classical martingale theory doesn't directly address nonlinear statistics like the ratio of wins to total steps when the sample size is path-dependent. By analyzing the expectation and variance of *R_N_d / N_d*, the authors provide insights into how optional stopping distorts empirical proportions. The paper's findings demonstrate that while the win rate is a biased estimator of *p* for any finite *d*, it converges to *p* in probability as *d* approaches infinity, ensuring consistency. Moreover, by providing closed-form expressions for the expectation of the win rate, the authors are able to construct efficient algorithms for approximating irrational constants.
Key Insights
- •Explicit integral representations are derived for both the expectation and variance of the win rate *R_N_d / N_d* (Theorem 2.1).
- •Closed-form expressions for the expectation of *R_N_d / N_d* are provided, distinguishing between odd and even values of *d* (Theorem 3.1).
- •The expectation of *R_N_d / N_d* is strictly decreasing in *d* and strictly increasing in *p* (Corollary 2.2 and 2.3).
- •The variance of *R_N_d / N_d* is not monotone in either *d* or *p*.
- •The authors demonstrate that *R_N_d / N_d* is a positively biased estimator of *p* for any finite *d*, but it is asymptotically unbiased as *d* approaches infinity (Corollary 2.2).
- •Biasing the coin (adjusting *p*) in the coin-flipping estimators of π and ln(2) can dramatically reduce the computational cost (expected number of flips) without sacrificing accuracy.
- •For approximating π using the first-passage time estimator with a biased coin (p=3/4) and *d*=45, the probability that the approximation error is less than 10^-9 is above 1-10^-6.
Practical Implications
- •The research provides a framework for quantifying the bias introduced by goal-based stopping rules in various applications, such as financial analysis, clinical trials, and A/B testing.
- •The coin-flipping estimators of π and ln(2) based on first-passage sampling can be used in scenarios where randomness is readily available (e.g., simulations, cryptography). The estimators can be tuned for accuracy and computational cost by adjusting the bias *p* of the coin.
- •The results can be used to design sequential procedures that minimize the distortion of empirical proportions caused by optional stopping.
- •The paper opens up avenues for future research, including extending the analysis to other base processes (e.g., Brownian motion, Poisson processes) and investigating multiple stopping-time problems.
- •The framework could be extended to address optimality questions in related sequential decision-making problems.