Sequential Sampling and Renewal Applications of Wald’s Identities

Wald’s Identities in Sequential Sampling

In a sequential procedure, the number of observations is random because the data determine when sampling stops. A natural question is whether the expected accumulated score is the average score per observation multiplied by the expected number of observations. Wald’s first identity answers this under specific conditions. Its second identity gives a corresponding second-moment calculation for centered scores. The stopping rule and the information available when it is applied matter: a random sample size alone does not guarantee either identity.

Work on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Let \(Z_1,Z_2,\ldots\) be independent, identically distributed integrable random variables, and let \(\mathcal{F}_n=\sigma(Z_1,\ldots,Z_n)\), with \(\mathcal{F}_0=\{\varnothing,\Omega\}\). A random variable \(\tau\) taking values in \(\{0,1,2,\ldots\}\cup\{\infty\}\) is a stopping time for this filtration if \(\{\tau\le n\}\in\mathcal{F}_n\) for every \(n\). In particular, the decision to stop by time \(n\) can use observations through time \(n\), but not later observations.

For a sequential score, \(Z_k\) might represent the score on observation \(k\), the reward from a trial, or a centered deviation from a known mean. The first identity concerns the expected accumulated score; it does not say that the stopped sum and the sample size are independent. The second identity concerns a centered sum, not an arbitrary uncentered score. For an uncentered score \(Z_k\) with mean \(a\), apply the second identity to \(Z_k-a\) only if the resulting stopped sum and the required conditions are appropriate.

The first identity can also be justified directly by indicator sums, which makes its role in applications transparent. This argument is useful when checking a proposed sequential calculation.

Proof. For each \(k\ge1\), the event \(\{\tau\ge k\}\) belongs to \(\mathcal{F}_{k-1}\), because its complement is \(\{\tau\le k-1\}\). Thus whether observation \(k\) is taken is determined before \(Z_k\) is observed. Since \(Z_k\) is independent of \(\mathcal{F}_{k-1}\), \(\mathbb{E}[Z_k\mathbf{1}_{\{\tau\ge k\}}]=\mathbb{E}[Z_1]\mathbb{P}(\tau\ge k)\). Also, \(\sum_{k\ge1}\mathbb{E}[|Z_k|\mathbf{1}_{\{\tau\ge k\}}]=\mathbb{E}|Z_1|\sum_{k\ge1}\mathbb{P}(\tau\ge k)=\mathbb{E}|Z_1|\mathbb{E}\tau<\infty\). So the stopped sum is integrable and its expectation can be computed by summing the expectations of its terms. Therefore \(\mathbb{E}[\sum_{k=1}^{\tau}Z_k]=\mathbb{E}[Z_1]\sum_{k\ge1}\mathbb{P}(\tau\ge k)=\mathbb{E}[Z_1]\mathbb{E}\tau\), using the tail-sum formula for a nonnegative integer-valued random variable. \(\square\)

Scores Under a Capped Stopping Rule

A bounded stopping time is often especially convenient: its expectation is finite automatically, and a finite enumeration can check the answer independently. The rule must still be a stopping time. A decision to stop at the first success, or at a fixed maximum sample size if no success occurs, uses only observations already collected.

Renewal Counts and Rewards

In a renewal process, interarrival times \(X_1,X_2,\ldots\) are independent and identically distributed, with \(X_k>0\) almost surely and finite mean \(\mu=\mathbb{E}X_1\). Define arrival times \(S_n=\sum_{k=1}^n X_k\), \(S_0=0\), and the renewal count \(N(t)=\max\{n\ge0:S_n\le t\}\) for \(t\ge0\). The inequality in this definition is inclusive: an arrival exactly at \(t\) is counted. The index \(T=N(t)+1=\inf\{n\ge1:S_n>t\}\) is the first arrival strictly after \(t\). With \(\mathcal{F}_n=\sigma(X_1,\ldots,X_n)\), \(T\) is a stopping time because \(\{T\le n\}=\{S_n>t\}\).

Proof. First, \(T\) is integrable. Since \(\mathbb{E}X_1>0\), there is an \(\varepsilon>0\) with \(q=\mathbb{P}(X_1\ge\varepsilon)>0\); otherwise \(X_1=0\) almost surely, contradicting its positive mean. Put \(r=\lfloor t/\varepsilon\rfloor+1\), so \(r\varepsilon>t\). The time needed to observe \(r\) interarrivals of size at least \(\varepsilon\) has mean \(r/q<\infty\), as it is a sum of \(r\) geometric waiting times of mean \(1/q\). By that time the accumulated interarrival sum exceeds \(t\), so \(T\) is no larger and has finite mean. Wald’s first identity applied to \(X_k\) gives \(\mathbb{E}S_T=\mu\mathbb{E}T\). By the definition of \(T\), \(S_{T-1}\le t<S_T\); and \(X_T\le b\), so \(S_T=S_{T-1}+X_T\le t+b\). Taking expectations gives \(t<\mathbb{E}S_T\le t+b\). Substituting \(T=N(t)+1\) proves the bound. \(\square\)

For renewal rewards, attach a reward \(R_k\) to renewal \(k\). Suppose the pairs \((X_k,R_k)\) are independent and identically distributed, \(\mathbb{E}|R_1|<\infty\), and the entire reward sequence is independent of the entire interarrival sequence. This last condition is stronger than merely having identically distributed pairs: it ensures that whether renewal \(k\) occurs by time \(t\) does not bias its reward.

Proof. The preceding integrability argument shows \(\mathbb{E}N(t)<\infty\). For each \(k\), the event \(\{S_k\le t\}\) depends only on interarrival times and is independent of \(R_k\). Therefore \(\mathbb{E}[R_k\mathbf{1}_{\{S_k\le t\}}]=\mathbb{E}R_1\,\mathbb{P}(S_k\le t)\). Moreover, \(\sum_{k\ge1}\mathbb{E}[|R_k|\mathbf{1}_{\{S_k\le t\}}]=\mathbb{E}|R_1|\sum_{k\ge1}\mathbb{P}(S_k\le t)=\mathbb{E}|R_1|\mathbb{E}N(t)<\infty\). Thus the expected reward sum can be computed term by term. Summing the preceding identities gives \(\mathbb{E}[\sum_{k=1}^{N(t)}R_k]=\mathbb{E}R_1\sum_{k\ge1}\mathbb{P}(S_k\le t)=\mathbb{E}R_1\,\mathbb{E}N(t)\), using the tail-sum expression for \(N(t)\). \(\square\)

Assumptions and a Common Error

The stopping-time condition prevents the sampling decision from using future observations. Integrability prevents an expected value from being treated as finite when it need not be. For the first identity, independence and identical distribution ensure that each included observation has the same mean as \(Z_1\); the indicator-sum proof shows why the decision to include observation \(k\) must be made using information available before \(Z_k\) is seen. For renewal rewards, independence between rewards and interarrival times is what allows the event that a renewal occurs by \(t\) to separate from its reward.

Common mistake: applying Wald’s identity to a non-stopping sample size. Let \(X_1,X_2\) be independent fair Bernoulli variables, with \(\mathcal{F}_n=\sigma(X_1,\ldots,X_n)\), and define \(\tau=1\) if \(X_2=1\), and \(\tau=2\) if \(X_2=0\). Then \(\mathbb{E}\tau=\tfrac12(1)+\tfrac12(2)=\tfrac32\). A tempting but wrong calculation gives \(\mathbb{E}[\sum_{k=1}^{\tau}X_k]=\mathbb{E}X_1\,\mathbb{E}\tau=\tfrac12\cdot\tfrac32=\tfrac34\). But \(\{\tau\le1\}=\{X_2=1\}\notin\mathcal{F}_1\), so \(\tau\) is not a stopping time. In fact, \(\sum_{k=1}^{\tau}X_k=X_1+\mathbf{1}_{\{X_2=0\}}X_2=X_1\), and its expectation is \(\tfrac12\), not \(\tfrac34\). Check the information condition before using Wald’s identities; a finite expected sample size alone is not enough.