First to reach $n$ game

This paper analyzes the overall net profits of two players in a "first to reach $n$" game governed by an urn model, demonstrating that the statistical properties of the game's outcomes differ drastically across three distinct regimes involving sampling without replacement, sampling with replacement plus reinforcement, and a third unspecified regime.

The Gist

Imagine you are watching a high-stakes tournament. Two players, let's call them Alice and Bob, are competing. The rule is simple: whoever wins $n$ rounds first takes home the grand prize.

But here's the twist: the game isn't just about skill; it's about luck, and the rules of luck change depending on which "universe" (or model) we are playing in. The paper you shared explores three different ways this luck can be determined, using a magical Urn of Balls as a metaphor.

Here is the breakdown of the three worlds, explained simply.

The Setup: The Urn of Fate

Imagine a giant jar (an urn) filled with two colors of balls: Red (for Alice) and Blue (for Bob).

• Every round, a ball is pulled out.
• If it's Red, Alice wins the round.
• If it's Blue, Bob wins the round.
• The game stops the moment one person has won $n$ rounds.
• The Prize isn't just a trophy; it's a score based on the "margin of victory." If Alice wins 10 rounds and Bob only wins 2, Alice's net profit is huge. If she wins 10 and Bob wins 9, her profit is tiny.

The paper asks: How much money (or points) can we expect the winner to make? And how does the way we pull the balls change the outcome?

---

World 1: The "Constant" Game (The Fair Coin Flip)

The Rule: Every time you pull a ball, you put it back, and the jar stays exactly the same. If Alice has a 60% chance of winning the first round, she has a 60% chance of winning the 100th round too.

The Metaphor: This is like flipping a slightly weighted coin. If the coin is biased toward Alice, she will almost certainly win. The paper calculates exactly how much she will win by the time the game ends.

The Big Discovery:

• If the game is fair (50/50): The winner doesn't win by a huge margin. The victory is usually close. The paper proves that the "profit" grows slowly, roughly like the square root of the target number ($\sqrt{n}$). It's a tight race.
• If the game is biased (Alice is better): Alice wins easily, and her profit grows linearly (straight line). The paper gives a fancy formula involving Catalan numbers (a sequence of numbers that pops up in many counting puzzles) to predict the exact average profit.

Takeaway: In a standard game, if you are slightly better, you win big. If you are equal, the game is a nail-biter.

---

World 2: The "Polya" Game (The Rich Get Richer)

The Rule: When you pull a ball, you don't just put it back. You put it back plus one extra ball of the same color.

• If Alice wins a round (Red ball), the jar gets more Red balls.
• If Bob wins, the jar gets more Blue balls.

The Metaphor: This is the "Snowball Effect" or "The Rich Get Richer."
Imagine Alice wins the first round. Suddenly, the jar is slightly more filled with Red balls. Now she has an even better chance of winning the next round. If she wins again, the jar becomes even more Red.
Once a player gets a small lead, the game essentially locks them in. It becomes very hard for the other player to catch up.

The Big Discovery:

• The winner is determined very early. The moment one player gets a slight edge, the probabilities shift so heavily in their favor that they almost certainly win the whole thing.
• The paper calculates the probability of who wins based on the starting number of balls. It turns out the final score distribution is a bit wild and unpredictable compared to the first model, but the "winner-take-all" nature is extreme.

Takeaway: In this world, momentum is everything. A tiny early lead guarantees a massive victory.

---

World 3: The "Anti-OK Corral" Game (The Underdog's Revenge)

The Rule: You pull a ball, but you do not put it back. The ball is gone forever.

• If Alice wins (Red ball), there is one less Red ball in the jar.
• If Bob wins, there is one less Blue ball.

The Metaphor: This is the opposite of the Snowball Effect. This is the "Underdog's Revenge."
Imagine Alice is winning. She keeps pulling Red balls. But because she isn't putting them back, the jar is slowly running out of Red balls! Meanwhile, the Blue balls are still there, untouched.
As Alice gets closer to winning, the jar becomes "Blue-heavy." The more she wins, the harder it becomes for her to win the next round. The game naturally pushes back against the leader.

The Big Discovery:

• This is the most surprising result. In this "Anti-OK Corral" model, the game tends to drag on until the very last possible moment.
• The paper shows that as the game gets longer, the winner's margin of victory becomes very small. The winner is just as likely to win by 1 point as they are to win by a huge amount (following a specific "Geometric" pattern).
• It's a game of "survival of the fittest" where the leader is constantly being hunted down by the lack of resources.

Takeaway: In this world, leading is dangerous. The more you win, the more likely you are to run out of "fuel," making the game incredibly close and competitive.

---

Summary: Why Does This Matter?

The authors (Stanislav Volkov and Magnus Wiktorsson) are essentially studying how different rules of chance affect the final outcome of a competition.

1. Constant Model: Standard sports. If you are better, you win comfortably.
2. Polya Model: Social media or viral trends. If you get a little famous, you get more famous, and the gap between you and the rest widens instantly.
3. Anti-OK Corral: Resource wars or depletion. If you use up your resources too fast to win, you leave yourself vulnerable, and the game stays tight until the very end.

The paper uses advanced math (Martingales, Poisson processes, and Gamma distributions) to prove these intuitive ideas, showing that the "rules of the urn" completely change the psychology and mathematics of winning.

Technical Summary

Here is a detailed technical summary of the paper "First to reach n game" by Stanislav Volkov and Magnus Wiktorsson.

1. Problem Statement

The paper investigates a probabilistic game involving two players competing to be the first to win exactly $n$ rounds. The game ends immediately upon a player reaching $n$ wins. The core objective is to analyze the properties of two random variables:

• $W_{n,p}$: The number of wins accumulated by the losing player when the game ends.
• $Z_{n,p}$: The net profit of Player 1, defined as the difference between their wins and the opponent's wins.
  • If Player 1 wins: $Z_{n,p} = n - W_{n,p}$.
  • If Player 2 wins: $Z_{n,p} = W_{n,p} - n$.

The authors study this game under three distinct regimes governing the probability of winning a round ($p_i$):

1. Constant Model: The probability $p$ is fixed for all rounds (standard Bernoulli trials).
2. Pólya Model: Probabilities are governed by a Pólya urn scheme (reinforcement), where the probability of winning increases with the number of previous wins.
3. Anti-OK Corral Model: Probabilities are governed by sampling without replacement from a finite urn, creating a "negative reinforcement" effect where the player with fewer remaining balls is more likely to win the next round.

2. Methodology

The authors employ a combination of probabilistic techniques, including:

• Martingale Theory: Used primarily in the Constant model to derive bounds on expected stopping times and net profits. They construct martingales such as $M_k = X_k - \mu k$ (where $X_k$ is the win difference) and apply the Optional Stopping Theorem.
• Combinatorial Analysis: Direct calculation of probabilities using binomial coefficients and Catalan numbers, particularly for the Constant and Anti-OK Corral models.
• Poisson Process Embedding (Rubin's Construction): A powerful technique used to analyze the asymptotic behavior ($n \to \infty$). The discrete game is embedded into continuous-time independent Poisson processes with rates $1$and$\lambda = q/p$. This allows the use of Gamma and Negative Binomial distributions to approximate the game dynamics.
• Asymptotic Analysis: Utilization of Stirling's approximation and Central Limit Theorems (CLT) to determine limiting distributions for large $n$.
• Beta-Pólya Representation: For the Pólya model, the authors utilize the representation of the urn process as a mixture of Bernoulli trials with a random probability parameter $\xi \sim \text{Beta}(N_1, N_2)$.

3. Key Results by Regime

A. The Constant Model ($p_i \equiv p$)

This is the primary focus of the paper.

• Exact Expectation: The authors derive an exact explicit formula for the expected net profit $E_{n,p} = E[Z_{n,p}]$:
  $$E_{n,p} = n\mu \sum_{j=0}^{n-1} C_j z^j$$
  where $\mu = p-q$, $z = pq$, and $C_j$ are the Catalan numbers.
• Asymptotic Behavior:
  • For $p > 1/2$, the distribution of the loser's wins $W_{n,p}$ converges to a Negative Binomial distribution.
  • The net profit $Z_{n,p}$ satisfies a Central Limit Theorem:
    $$\frac{Z_{n,p} - \mu n}{\sqrt{n}q} \xrightarrow{d} N(0, 1)$$
  • Symmetric Case ($p=1/2$): The expected profit of the winner scales asymptotically as $\approx 2\sqrt{n/\pi} \approx 1.13\sqrt{n}$. This is derived via martingale bounds and confirmed by the Poisson embedding.

B. The Pólya Model (Reinforcement)

• Winning Probability: The probability that Player 1 wins overall is given by an integral involving the Beta function:
  $$P(\text{Player 1 wins}) = \frac{\Gamma(N_1 + N_2)}{\Gamma(N_1)\Gamma(N_2)} \int_0^1 \frac{(1-x)^{N_2-1}}{(2-x)^{N_1+N_2}} dx$$
• Limiting Distribution: As $n \to \infty$, the normalized net profit $Z_n/n$ converges in distribution to a random variable $\zeta$ with a specific density function derived from the initial Beta distribution of the urn.
• Special Case ($N_1=N_2$): The asymptotic expected profit behaves similarly to the constant case ($\approx 2\sqrt{n/\pi}$), as the reinforcement effect diminishes relative to the total number of rounds for large $n$.

C. The Anti-OK Corral Model (Without Replacement)

• Mechanism: The urn starts with $n$ balls of each type. Balls are drawn without replacement.
• Counter-Intuitive Result: Unlike the classic OK Corral problem (where the stronger team wins), here the player with fewer remaining balls has a higher probability of winning the next round.
• Limiting Distribution: As $n \to \infty$, the probability that the winner wins by a margin of $k$ (i.e., the loser wins $n-k$ rounds) converges to:
  $$P(\text{Margin} = k) \to \frac{1}{2^{k+1}}$$
  The net profit follows a mixture of two Geometric(1/2) distributions. This indicates a much "tighter" game compared to the Constant model, where the winner usually dominates significantly.

4. Significance and Contributions

1. Unification of Models: The paper provides a unified framework for analyzing "first to reach $n$" games under three distinct probabilistic regimes, highlighting how the mechanism of probability evolution (constant, reinforcement, or depletion) drastically alters the outcome distribution.
2. Exact Formulas: The derivation of the exact expected net profit in the Constant model using Catalan numbers is a significant analytical contribution, bridging combinatorics and stochastic processes.
3. Asymptotic Precision: The paper rigorously establishes the Central Limit Theorem for the net profit in the Constant model and characterizes the limiting distributions for the other two models, offering precise scaling laws (e.g., $\sqrt{n}$ vs. constant margin).
4. Methodological Demonstration: The effective use of Rubin's construction (Poisson embedding) to solve a discrete stopping-time problem serves as a robust example of how continuous-time processes can simplify the analysis of complex discrete games.
5. Real-World Applicability: The models are directly applicable to sports and competitive formats (tennis, fighting games, chess) where the "first to $n$" rule is standard, providing theoretical bounds on expected score margins and the likelihood of upsets.

In summary, the paper demonstrates that while the "first to $n$" structure is constant, the underlying probabilistic mechanism (urn dynamics) fundamentally changes the statistical properties of the game's conclusion, ranging from Gaussian fluctuations in the constant case to geometric tails in the depletion case.