📊 statistics

Causal Inference on Stopped Random Walks in Online Advertising

This paper proposes a causal inference framework for estimating long-term treatment effects in online advertising by modeling revenue as a stopped random walk under budget constraints, thereby relaxing the i.i.d. assumption and utilizing the Anscombe Theorem and Central Limit Theorem to construct valid confidence intervals.

Original authors: Jia Yuan Yu

Published 2026-02-06

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jia Yuan Yu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the manager of a massive, bustling digital town square (like Instagram or TikTok). Every day, thousands of people walk through, and you have a limited number of billboards to show them. You also have a group of shopkeepers (advertisers) who want to put their signs on those billboards, but each shopkeeper has a strict daily spending limit.

The paper you shared is about a tricky problem: How do you figure out if changing the price of your billboards will make you more money in the long run, without accidentally ruining the town's economy while you are testing it?

Here is the breakdown of their solution, using simple analogies.

1. The Problem: The "Traffic Cop" Paradox

In a normal experiment (like testing a new medicine), you give the drug to one group and a placebo to another, and you count the results. The people don't change their behavior just because they are being watched.

But in online advertising, the act of measuring changes the result.

If you raise the price of a billboard (the "treatment"), fewer people see ads.
Because fewer people see ads, the shopkeepers have leftover money at the end of the day.
Because they have leftover money, they might bid more aggressively the next day.
Also, if the ads are annoying or too expensive, people might leave the town square earlier, meaning there are fewer "opportunities" to show ads in the first place.

The authors call this a Stopped Random Walk. Imagine a drunk person walking down a street (the user session). They stop walking when they get home or get tired. The "treatment" (the ad price) doesn't just change how much money they spend on the way; it changes how far they walk before stopping. If you just count the money per step, you miss the fact that the person stopped walking sooner.

2. The Solution: The "Permutation Trick" (The Checkout Line)

The math behind this is incredibly complex because there are millions of users and hundreds of advertisers all interacting at once. It's like trying to track every single item on a thousand different checkout conveyor belts at a supermarket simultaneously. The data is too huge to analyze.

The authors introduce a clever trick called Permutation.

The Analogy: Imagine a supermarket where customers (users) are interleaved on a single conveyor belt. Customer A puts an item, then Customer B, then Customer A again.
The Trick: The authors say, "Let's pretend we rearranged the belt so that Customer A puts all their items down first, then Customer B puts all theirs down."
Why it works: They argue that as long as the shopkeepers (advertisers) have huge budgets that last for weeks, it doesn't matter if they pay for items in a jumbled order or a grouped order. The total money spent and the total items sold will be roughly the same. This allows them to simplify the math from a chaotic mess into a manageable, orderly line.

3. The Experiment: The "Budget Split"

To test if a new billboard price works, they can't just wait a year to see the results. That's too slow and costs too much money. Instead, they use a Budget-Splitting Experiment.

The Setup: They take the entire population of users and randomly split them into two groups: Group A and Group B.
The Twist: They also split the advertisers' budgets. If an advertiser has \ $100 to spend, they give \$ 50 worth of "budget power" to Group A and $50 to Group B.
The Test:
- Group A sees ads with a High Price.
- Group B sees ads with a Low Price.
The Measurement: They run this for a set time (say, a few days). They count:
1. How many ads were shown in each group? (Remember, the High Price group might show fewer ads because people leave the site faster).
2. How much money was made per ad?

4. The Result: The "Confidence Interval"

The paper provides a mathematical formula to calculate the answer. It tells the publisher: "Based on what happened in our short experiment, we are 95% sure that the new price will increase (or decrease) your total annual revenue by this specific amount."

They use advanced statistical tools (like the Central Limit Theorem and Wald's Equation) to account for the fact that:

The number of people walking through the town changed.
The shopkeepers' budgets ran out at different times.
The "stopping time" (when a user session ends) was different for each group.

Summary

The paper solves the problem of predicting long-term revenue in a system where the rules of the game change how the game is played.

Instead of getting confused by the chaos of millions of users and advertisers interacting, they:

Reordered the data (Permutation Trick) to make it mathematically solvable.
Split the budgets (Budget-Splitting) to run a fair, fast experiment.
Used a special formula to translate the short-term experiment results into a reliable prediction for the long-term annual revenue, even though the number of "customers" changed during the test.

It's a way to safely test a new policy in a complex, living ecosystem without breaking the ecosystem while you are watching it.

Technical Summary: Causal Inference on Stopped Random Walks in Online Advertising

Problem Statement
The paper addresses a causal inference challenge specific to online advertising platforms (publishers) where the goal is to estimate the long-term treatment effect of mechanism parameters, such as auction reserve prices. Unlike classical settings (e.g., drug trials) where the population size is fixed and independent of the treatment, online advertising involves a complex, interconnected system of publishers, users, and advertisers. In this environment:

Treatment affects the population size: A treatment (e.g., a higher reserve price) alters user interaction trajectories (session length) and advertiser bidding behaviors (constrained by finite budgets), thereby changing the total number of impression opportunities generated over a fixed time period.
Interference and Dynamics: The decision to measure treatment effects alters the system being measured. User sessions are modeled as Markov chains, and advertiser budgets evolve as another Markov chain dependent on past auction outcomes.
Measurement Scale Mismatch: The target metric is long-term revenue (e.g., over $k$ days), but the natural unit of observation is the individual ad impression. The number of impressions in a fixed time window is a random variable (a stopping time) dependent on the treatment.

The core difficulty is that standard Central Limit Theorem (CLT) approaches assuming independent and identically distributed (i.i.d.) measurements or fixed sample sizes are insufficient. The paper models the cumulative revenue as a stopped random walk, where the stopping time (total impressions in $k$ days) is random and treatment-dependent.

Methodology

1. Modeling Framework
The authors model the trilateral interaction between the publisher, users, and advertisers as a discrete-time Markov chain.

State Space: The state includes the profile of pages visited by all users ( $X_n$ ), the remaining budgets of all advertisers ( $\Omega_n$ ), and the index of the active user ( $I_n$ ).
Dynamics: User page transitions and advertiser budget updates are governed by stationary strategies (reserve price functions and bidding functions) and random variables representing user behavior and budget replenishment.
Revenue: The publisher's revenue is a non-linear, potentially discontinuous function of the reserve price and the winning bid (second-price auction logic).

2. Dimensionality Reduction: The Permutation Trick
A major hurdle is the exponential state space size when modeling $d$ users and $m$ advertisers simultaneously. To address this, the authors introduce a permutation trick:

Motivation: Based on the observation that the order of interleaving page transitions from different concurrent user sessions has a negligible effect on aggregate sales and cash flow, provided user session timescales are much smaller than advertiser campaign durations.
Mechanism: The authors define a permutation $\sigma$ that reorders the sequence of impressions to group all page transitions belonging to the same user session together.
Result: This transforms the original high-dimensional Markov chain into an approximate chain with a significantly smaller state space ( $\mathcal{X} \times \mathbb{R}^m \times [d]$ ), where entire user sessions are interleaved rather than individual page transitions. This approximation relies on Assumption 2.1, which posits that ad campaign budgets and durations are large relative to individual impression costs and session lengths.

3. Experimental Design: Budget Splitting
To estimate the treatment effect, the paper proposes a budget-splitting experimental design (inspired by [LMK21]):

Population Split: Users are randomly assigned to subpopulations $A$ and $B$ with probabilities $q$ and $1-q$ .
Treatment Assignment: Subpopulation $A$ receives treatment $v$ (reserve price $v$ ) and $B$ receives treatment $w$ .
Budget Splitting: Each advertiser's budget is split proportionally ( $q$ and $1-q$ ) between the two subpopulations. Advertisers in each group compete only within their assigned subpopulation's Markov chain.
Estimator: The estimator $\hat{\Delta}$ for the total treatment effect is constructed by scaling the observed average revenue and impression counts from the subpopulations by $1/q$ and $1/(1-q)$ respectively, effectively extrapolating the subpopulation results to the full population.

4. Theoretical Guarantees
The paper derives a confidence interval for the long-term treatment effect $\Delta$ using:

Markov Chain CLT: Applied to the permuted chains to establish asymptotic normality of the revenue sums.
Wald-like Equation: Used to handle the random stopping times (total impressions over $k$ days).
Anscombe Theorem: Employed to justify the convergence of the stopped random walk to a normal distribution despite the random sample size.
Ergodicity Assumptions: The analysis assumes the underlying Markov chains are Harris ergodic and geometrically ergodic, ensuring the existence of invariant distributions.

Key Contributions

Modeling: Introduction of a stopped random walk model for causal inference where the population size (number of impressions) is random and treatment-dependent. This generalizes classical causal inference which typically assumes a fixed population.
Analytical: Development of a permutation trick to reduce the dimensionality of the state space in multi-user, multi-advertiser Markovian systems, enabling tractable analysis under mild assumptions regarding time scales.
Statistical Inference: Derivation of confidence intervals for long-term treatment effects in this complex setting by combining a Markovian CLT, a Wald-like equation, and the Anscombe Theorem. This provides a theoretical basis for determining necessary experiment durations.

Results
The main result (Theorem 3.6) establishes that under assumptions of time-invariant strategies, ergodicity, and campaign scale, the proposed estimator $\hat{\Delta}$ converges to the true treatment effect $\Delta$ . Specifically, the paper proves that:
$\lim_{k \to \infty} P(|\hat{\Delta} - \Delta| \leq \epsilon) \geq 1 - 2\alpha$
where $\epsilon$ is a bound dependent on the asymptotic variances of the subpopulation chains and the difference between the subpopulation and full-population invariant distributions. The paper notes that in practice, with large user populations, these distributions are expected to be close, making the estimator effective.

Significance and Claims
The paper claims to provide a rigorous framework for causal inference in online advertising systems where the "unit of analysis" (the user session) and the "measurement unit" (the impression) operate on different scales, and where the treatment itself alters the volume of data generated.

It moves beyond the "finite population" assumption of classical causal inference to a random, treatment-dependent population.
It offers a practical solution to the "interference" problem in two-sided markets by explicitly modeling the dynamics of users and advertisers rather than relying solely on randomization techniques to control interference.
It provides actionable guidance on experiment duration by linking the confidence interval width to the asymptotic variances and the number of periods $k$ .

The authors acknowledge limitations, noting that the model assumes stationary strategies and does not explicitly handle non-stationary dynamics (e.g., new advertisers entering the system). They also suggest that while the budget-splitting design is effective, it may not correct for arbitrary interference effects not captured by the specific Markovian model.