{'fraction_non_alphanumeric': 0.03818129661503156, 'fraction_numerical': 0.01491681009753299, 'mean_word_length': 4.358284660313557, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 8, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sequential Testing of Multinomial Hypotheses with Applications to Detecting Implementation Errors and Missing Data in Randomized Experiments

Simply randomized designs are one of the most common controlled experiments used to study causal effects. Failure of the assignment mechanism, to provide proper randomization of units across treatments, or the data collection mechanism, when data is missing not at random, can render subsequent analysis invalid if not properly identified. In this paper we demonstrate that such practical implementation errors can often be identified, fortunately, through consideration of the total unit counts resulting in each treatment group. Based on this observation, we introduce a sequential hypothesis test constructed from Bayesian multinomial-Dirichlet families for detecting practical implementation errors in simply randomized experiments. By establishing a Martingale property of the posterior odds under the null hypothesis, frequentist Type-I error is controlled under both optional stopping and continuation via maximal inequalities, preventing practitioners from potentially inflating false positive probabilities through continuous monitoring. In contrast to other statistical tests that are performed once all data collection is completed, the proposed test is sequential - frequently rejecting the null during the process of data collection itself, saving further units from entering an improperly-executed experiment. We illustrate the utility of this test in the context of online controlled experiments (OCEs), where the assignment is automated through code and data collected through complex processing pipelines, often in the presence of unintended bugs and logical errors. Confidence sequences possessing desired sequential frequentist coverage probabilities are provided and their connection to the Bayesian support interval is examined. The differences between pure Bayesian and sequential frequentist testing procedures are finally discussed through a conditional frequentist testing perspective.


Introduction
Randomized treatment assignment satisfies many purposes in controlled experiments (see Kempthorne (1977), Cox (2009) and Rubin (1978)). Arguably the least controversial justification is the attempt to remove any personal, systematic, or selection bias in the treatment assignment mechanism, although this is neither without criticism nor without alternative (see Lindley (1982) and Kadane and Seidenfeld (1990)). Consider, for example, a medical researcher who administers a preferred experimental drug to only the patients most likely to recover. Without explicitly conditioning on this information in the assignment mechanism, causal estimands such as the average treatment effect may be biased and overestimate the efficacy of the new drug (Berry (2004)). Simply randomized experiments attempt to remove the possibility of bias by randomly assigning experimental units independently to treatment groups. This design is useful in contexts where units enter the experiment sequentially, as opposed to all being simultaneously available like in completely randomized designs, and are often used in the technology industry to run online controlled experiments (OCEs) (Kohavi et al. (2013)). Formally, let there be d treatment groups, let d denote the d-dimensional simplex, let θ 0 ∈ d be a probability vector where element θ 0,i denotes the probability of any unit being assigned to treatment group i, and x j a random variable denoting the assignment outcome of the jth experimental unit. We use boldface to emphasize vectors. The simply randomized design can then be summarized by the following probabilistic assignment mechanism The statistician may not be personally involved with the data collection process and may simply be told the assignment mechanism after being presented with the data for analysis and has a right for concern when they are provided with data that does not support the purported assignment mechanism. For simply randomized experiments, the total unit counts assigned to each treatment group can provide evidence that the model Equation 1 is not true. Indeed, this is a strong indicator that the experiment has not been conducted as expected; for example, the assignment mechanism could be biased, there could be systematic data loss, or generally when the data can be considered "missing not at random" (MNAR) (Rubin, 1976). Such observations occur frequently in OCEs and are colloquially referred to as sample ratio mismatches (SRMs). OCEs automate the assignment mechanism, data collection and data cleaning through code, which often introduces bugs and logical errors. It is unsurprising, therefore, that Fabijan et al. (2019) report that 6% of all experiments performed in a year at Microsoft contained bugs which were revealed by SRMs. The authors describe in detail the engineering architecture required for assignment and data collection in OCEs and highlight how SRMs frequently reveal bugs therein. They further provide a simple example of an experiment to study user engagement on an improved version of a web page is provided. Not all visitors to a web page are human, however, and data must be cleaned to remove non-human interactions with the page, such as from web crawlers and scrapers. Unfortunately, the classification between human and non-human visitors is performed algorithmically, and some users in the treatment group were so engaged with the new page that they were accidentally classified as non-human and removed prior to the analysis -essentially removing units most in favor of the treatment, resulting in fewer units than expected being reported in the treatment group. This is not an issue with the assignment mechanism but in the data collection. It is an example of a censoring missing data mechanism, a special case of MNAR.
Noncompliance (Imbens and Rubin (1997)) can also be revealed through SRMs. For example, Zhao et al. (2016) describe an example in which the user identifier becomes lost, preventing users from receiving a consistent experience over time, with some users initially assigned to the treatment becoming exposed to and recorded in the control.
Many other practical abnormalities can be revealed by considering the total counts in each treatment group after collection. For this reason, industry practitioners now consider performing a χ 2 test against the null in Equation 1 best practice (Chen et al., 2018); such a test can identify an SRM. We would like to underscore, however, one strong criticism of this practice, specifically, the difficulty in knowing when exactly to perform the test. While it is most common to perform this test after data collection and before analysis, this has the obvious shortcoming of surfacing a problem in the data collecting process only after the data collection has completed. As there is always a cost associated with performing experiments, one would ideally have problems detected early, as there is a large opportunity cost in allowing further experimental units to enter a faulty experiment. On the other hand, it is also fairly common to perform the test at the outset, perhaps on an initial set of experimental units, to "validate" the experiment implementation. If the test is performed too early, however, then the test may lack sufficient power to detect such problems. The tension between running the test early enough to prevent wasted units but late enough to have sufficient power has led to widespread misuse in the online experimentation space. Practitioners incorrectly continuously monitor their experiments by repeatedly performing significance tests, usually in an ad hoc fashion, without any multiplicity correction, resulting in increased Type-I error rates. As an example, Armitage et al. (1969) demonstrated for χ 2 tests configured at the 0.05 level that the Type-I error probability can increase up to 0.14 with as few as 5 repeated usages. This follows from the inability of the χ 2 test to preserve Type-I error guarantees under optional stopping and optional continuation. Optional stopping refers to the practice of performing a significance test on the data collected so far, and using the outcome to determine whether to continue. Such behavior is often observed when a practitioner believes there is an underlying issue in the implementation, and performs an unplanned χ 2 test to investigate, which may become one of many. Optional continuation, on the other hand, refers to the practice of letting the decision to perform a new test depend on the outcome of a previous test. This is often seen when the outcome of an early "validation" test is inconclusive, and so another unplanned test is sought. Many classical tests, such as the χ 2 test and the likelihood ratio test, do not preserve Type-I error guarantees under optional stopping/continuation, and will result in dramatically higher false-positive rates without proper multiplicity adjustments. Moreover, for many classical tests it is possible to sample to a foregone conclusion under optional continuation -rejecting the null almost surely when the null is in fact true Anscombe (1972). In section 4 we will demonstrate that the Type-I error probability of a χ 2 test configured at the Type-I error level of 0.05 can rise in excess of 0.44 when used to continuously monitor a running experiment. See Schönbrodt et al. (2015) and Grünwald et al. (2020) for further discussions on these issues.
A sequential hypothesis test, in contrast, preserves Type-I error guarantees under both optional stopping and continuation, allowing experiments to be continuously monitored for significance -even after every datapoint. The advantages are at least twofold. Firstly, it prevents the pitfalls mentioned in the preceding paragraph, providing maximum flexibility for performing significance tests. Secondly, significance tests can be executed after every datapoint, allowing SRMs in the current application to be detected as soon as possible. In this paper, we propose such a sequential test inspired by Bayesian methods. Bayesian methods are a natural choice for sequential procedures as most satisfy the stopping rule principle, that that statistical conclusions provided by a hypothesis test should be independent of the reason for stopping the experiment, which is a direct consequence of the likelihood principle (Berger et al., 1988).
The contributions of this paper focus, however, on obtaining frequentist properties of such a sequential test. The paper is outlined as follows. Section 2 defines a common Bayesian test through conjugate multinomial-Dirichlet models. Section 3 establishes the Martingale properties of the posterior odds under the null hypothesis, enabling a modified test to be developed which allows control of the frequentist Type-I error probabilities under both optional stopping and continuation. This safely permits the online testing of hypothesis Equation 1 after every single observation, without inflating frequentist Type-I error, with the obvious advantage of being able to safely reject the null and discover a practical implementation error early in the beginning of an experiment -preventing experimental units being wasted on a faulty experiment. Instance-specific upper-bounds on time-to-rejection are provided in terms of the KL divergence between θ 0 and the actual generating distribution of the samples. This sequential test is then inverted to define confidence sequences that possess desired frequentist coverage probabilities. Section 4 presents several simulation studies illustrating how false-positive probabilities are dramatically inflated through the repeated significance testing using a χ 2 test compared to the guarantees afforded by the proposed test. We also study the number of samples needed to reject the null when the null is invalid. The final section 5 connects these contributions with existing literature. In particular, the confidence sequence defined in Theorem 3.1 is identified as the Bayesian support interval of Wagenmakers et al. (2020) through an application of the Savage-Dickey density ratio. The differences between the pure Bayesian test and the proposed test are discussed from the perspective of conditional frequentist testing (Berger et al., 1994(Berger et al., , 1997Dass and Berger, 2003).
The sequentially recorded observations may differ from the null hypothesis, which we will denote M 0 , if there is an unintended bias in the assignment mechanism or if an unknown missing data mechanism, as discussed in section 1. We therefore wish to test the null hypothesis θ = θ 0 vs. θ = d \ θ 0 . To develop a Bayesian hypothesis test, it is necessary to specify an alternative model for the data, denoted M 1 . Consider the following model studied in Good (1967), Prior mass is concentrated around θ 0 by specifying α 0,i = kθ 0,i for concentration parameter k ∈ R + , in line with a "Jeffreys-type" testing procedure -if the null were not at least somewhat plausible, then a statistical test would not be needed. The Bayes factor comparing models M 1 to M 0 is analytically tractable and is given by which, when combined with the prior odds, yields the posterior odds of model M 1 to M 0 . To assist with the exposition, we introduce the following notation. Let S n i = n j=1 x j,i and S n = (S n 1 , . . . , S n d ) ∈ R d so that the MLE can be easily be defined asθ n := S n /n. In addition, we will use |v| = i v i to denote the elementwise sum of a vector v, v w = i v w i i to denote elementwise exponentiation of two vectors v and w, and the multivariate Beta function Beta(v) : can then be succinctly expressed as It is helpful to consider the posterior odds as computed sequentially through the following recursive definition, where α n = α n−1 + x n and O 0 (θ 0 ) = p(M 1 )/p(M 0 ) (see appendix section A). In the rest of this paper, we will always assume that the prior odds are unity, and so the posterior odds are interchangeable with the Bayes factor. Recursive definitions require an initial value and for that reason we choose to work with the posterior odds. The dependence of O n (θ 0 ) on the observed data x 1:n is implicit in this notation, yet the null value θ 0 being tested is made explicit to aid the discussion of confidence sequences in Theorem 3.1. If α 0 is integer-valued, and noting that all but one of the x n,j is 1 with the others 0, then the recursive definition simplifies substantially to where the last line follows from the mean of the Dirichlet posterior predictive distribution. This multiplicative update has some intuitive appeal -it is the expected probability, based on our current Bayesian belief, divided by the null probability of the event that occurred. A pure Bayesian analysis could proceed by rejecting the null when O n (θ 0 ) ≥ c and reporting a posterior error probability of less than 1/(1 + c) (Bernardo and Smith, 1998, Chapter 5). Many find the pure Bayesian approach unsettling as it is difficult to form a sensible prior belief on θ under the alternative model. We instead develop a test based on O n (θ 0 ) which controls the frequentist Type-I error under optional stopping and continuation, regardless of the choice of α 0 .

Theoretical Results
A time-uniform bound, such as the one presented below in Theorem 3.1, controls the deviations of a stochastic process for all n simultaneously. Time-uniform bounds under the null hypothesis are essential for proving the correctness of sequential tests and verifying the optional stopping and optional continuation properties.
for all u ∈ [0, 1] and for all choices of α 0 .
The uniform condition in Equation 8 suggests that a valid decision rule is to reject the null at time τ = inf{n ∈ N : O n (θ 0 ) ≥ 1/u}. Simply stated, a practitioner who rejects the null hypothesis as soon as the posterior odds become larger than 1/u incurs a frequentist type-I error probability of at most u. The proof, based on Martingale maximal inequalities, can be found in appendix section B. Results of this form can be found in the literature as early as Ville (1939). An alternative and succinct proof, with applications to the special case of Binomial-Uniform families, can be found in section 1 of Robbins (1970). Furthermore, the posterior odds are equal to the Bayes factor under prior odds of unity, and so Theorem 3.1 can also be established as a corollary of mixture sequential probability ratio test (mSPRT) of Wald (1945). The test statistic in the mSPRT is formed by integrating the alternative likelihood divided by the null likelihood w.r.t. a weight function over the unknown parameter, and the hypothesis is rejected as soon as this test statistic exceeds 1/u. When the weight function is equal to the prior distribution, the mSPRT test statistic is simply the Bayes factor, and results of this form can be established for other Bayesian simple null vs. composite alternative hypothesis tests. In the language of Johari et al. (2015) one can define a conservative sequential p-value process by p 0 = 1 and which satisfies the following sequential analogue of a conservative p-value, Further connections between sequential p-value processes and Bayes factors are discussed in Shafer et al. (2011). Similar to how p-values can be used to derive confidence intervals, sequential p-values can be used to derive confidence sequences. A confidence sequence for a parameter is a sequence of intervals that, with probability at least 1-u, contains the true parameter for all sample sizes simultaneously. Fortunately, obtaining such a confidence sequence follows easily from their duality with sequential p-values.
Each I n (u) is a convex subset of d (convexity following from concavity of the multinomial log-likelihood).
In practice, however, one may find it easier to work with confidence sequences on the individual components of θ, which can be found by projecting I n (u) onto the coordinate axis Remark 3.1. For I n (u) as in Theorem 3.1, let These intervals can easily be obtained through convex programming and possess the desired frequentist coverage probability for all time n over all components simultaneously. Control over Type-I error probabilities would be of little value if the test were not able to reject the null when θ = θ 0 . We prove that the test rejects the null when θ = θ 0 almost surely, or that the test is asymptotically power one in the words of Robbins (1970). We first establish the following result for the consistency of the posterior odds.
When θ = θ 0 , we must have D KL (p(·|θ )||p(·|θ 0 )) > 0, and so Theorem 3.2 can be restated as O n (θ 0 ) → ∞ almost surely as n → ∞, which consequently rejects the null almost surely for any choice of Type-I error probability u. The formal proof is given in appendix section C, which relies on Theorem 1 of Walker et al. (2004). Conceptually, the proof proceeds by expressing the Bayes factor comparing M 1 to M 0 in terms of two separate Bayes factors. The first compares M to M 1 , and the second compares M to M 0 as follows 1 n logBF 10 (x 1: where p(x i |M ) is the density of a Multinomial(1, θ ) distribution. When the x i are independently distributed according to Multinomial(1, θ ), i.e. under model M , then the second term converges to the Kullback-Leibler divergence between models M and M 0 by the strong law of large numbers. To address the first term, note that as n becomes large the Dirichlet posterior p(θ|x 1:n , M 1 ) concentrates mass on θ , consequently bringing the posterior predictive p(x n+1 |x 1:n , M 1 ) = p(x n+1 |θ, M 1 ), p(θ|x 1:n , M 1 )dθ closer to the "true" density p(x n+1 |M ). For n large the logarithm of the fraction of densities becomes zero, and these zero terms then overwhelm the earlier non-zero terms in the sum.
To facilitate the discussion of how quickly the null is rejected, we define the rejection region at time n for a given u > 0 as R n = {x 1:n : O n (θ 0 ) ≥ u}, and the complementary indifference region as I n = {x 1:n : O n (θ 0 ) < u}. The rejection region in this form is a little cumbersome to work with, and so our first result is to provide an R n ⊆ R n which more amenable to computation.
Lemma 3.1. For every n > 0, u > 0, and α 0 define the set where andθ(x 1:n ) is the maximum likelihood estimate. Then R n ⊆ R n .
The proof of this lemma is found in appendix section D. This lemma is then used to establish the following result. Let τ = inf{n ∈ N : O n (θ 0 ) ≥ 1/u} be the random stopping time at which the null is rejected and define N = min{n ∈ N : θ − θ 0 1 ≥ 2D n (u, α)}, then for all n ≥ N This theorem provides a lower bound on the probability of rejecting the null by time n as a function of θ − θ 0 1 , u and α 0 . The proof is given in appendix section E.

False Positive Control Compared to χ 2 Test
In the following simulation we demonstrate the control over false positives provided by the proposed test.
In addition, we demonstrate how continuously monitoring experiments can result in an incredibly large number of false positives when misusing a χ 2 test. Although the proposed method is completely general and holds for any number of treatments, we demonstrate the following for the special case of a single treatment i.e. an A/B test. This is easiest to visualize and helps to develop an intuitive understanding of the differences between our test and the χ 2 test. Let the probability of assignment to the treatment group be denoted ρ. The assignment is therefore a Bernoulli(ρ) random variable, but sticking with the general framework developed earlier, the assignment outcome is Multinomial(1, θ) random variable with θ = [(1 − ρ) ρ]. It is common and natural to consider the difference between the empirical estimateρ(x 1:n ) = 1/n n i=1 x i,1 and the ρ 0 of the null hypothesis. Both the χ 2 test and the proposed test define an interval at each time n around ρ 0 , outside of which to reject the null hypothesis for the test statisticρ(x 1:n ). To see this, note that the Bayes factor can be expressed as BF 10 (x 1:n ) = Γ(α 0,0 + α 0,1 ) Γ(α 0,0 + α 0,1 + n) Γ(α 0,0 + n − nρ(x 1:n ))Γ(α 0,1 + nρ(x 1:n )) Γ(α 0,0 ) + Γ(α 0,1 )
(15) Rejection of the null when the posterior odds O n (θ 0 ) exceeds 1/u, is equivalent to rejecting the null whenever the test statisticρ(x 1:n ) falls outside a certain interval covering ρ 0 . This interval for θ 0 = [ 1 2 1 2 ], α 0 = 100θ 0 , and u = 0.05 is shown along with the interval for the χ 2 test is shown in figure 1. An important observation is that the rejection region at any time n for the proposed test is a subset of that of the χ 2 test. In other words, the χ 2 test would declare a result "significant" at the u = 0.05 level "sooner" than the proposed test. This has to be the case, for if the proposed test were significant as often as the χ 2 test, then the proposed test would have just as many false positives under continuous monitoring.
To illustrate this point further, 100 datasets were simulated under the null hypothesis up to t = 1000. The χ 2 (u = 0.05) test was applied after every observation and by t = 1000 44 out of the 100 datasets resulted in the erroneous rejection of the null hypothesis. If left to run for longer, the total number of false positives would surely increase beyond 44. This is shown in figure 2. The simulation can be repeated, using the same random number seed, to demonstrate the control over false positives of the proposed test. Under identical conditions, the proposed test resulted in 2 out of 100 false positives, illustrated in figure 3. Together, these examples clearly illustrate that repeated significance testing with a χ 2 test, without multiplicity adjustments, dramatically increases the chances of false positives, whereas the proposed sequential test controls the false positive probability under the desired value.

Stopping Time
We now turn our attention to visualizing the main value add of the proposed test, namely, to reject the null hypothesis quickly. Suppose an experiment has been designed and a sample size calculation has determined that 1000 datapoints must be collected. The intended treatment assignment probability is 0.5, yet due to a bug in the code introducing bias in the assignment mechanism, or a missing data mechanism for the control group, the probability of recording an observation from the treatment is in fact 0.6. Ideally, one would like to be alerted to this issue as soon as possible so as to remedy the problem before new units enter the experiment. While the χ 2 test can only safely be used at the end of the experiment, figure 4 demonstrates that the proposed test rapidly rejects the null considerably sooner than the end of the experiment, saving further units from entering an incorrectly executed experiment. Figure 4: Simulation Study of time to reject the null under the proposed test. The magenta curve is the same as in figure 1. Each blue trace is an independent simulation ofρ(x 1:n ) up until t = 1000 or the first n for which it crosses the rejection boundary of the χ 2 test,visualized with a red dot, whichever comes sooner.
To add some intuition to figure 4, it can be shown that while the rejection region at time n converges to [0, 1] \ ρ 0 , the MLEρ(x 1:n ) → ρ = ρ 0 a.s. as n → ∞ by the strong law of large numbers, and is hence guaranteed to cross the rejection boundary. This provides an alternative proof strategy to Theorem 3.2. In this specific example, the region of indifference degenerates onto {0.5}, yet the sample paths ofρ(x 1:n ) are converging toward 0.6 and ultimately encounter the rejection boundary.

Asymptotic Properties of Posterior Odds
In this small section we illustrate the conclusion of Theorem 3.2 with a simulation study.

Discussion
The main purpose of this paper was to provide a tool that can be used sequentially to detect practical implementation errors in an experiment, such as identifying biased assignment mechanisms or surfacing missing data mechanisms which are frequently observed in online controlled experiments. The proposed test permits optional stopping and continuation, allowing experiments to be continuously monitored. The hypothesis can be tested, therefore, after every single data point so as to detect errors as quickly as possible. While Bayesian in construction, we provided sequential guarantees of the frequentist Type-I error probability, proved that it rejects the null almost surely when the null is incorrect, and also studied the stopping time of this test through a combination of theoretical results and simulation studies. While our application of detecting errors in simply randomized experiments focused on a specific Multinomial-Dirichlet test, the same mathematical techniques can be obviously used to generalize these results to other Bayesian tests. With generalization in mind, there are some remaining comments and ideas for future work.
We first address the differences in the purely Bayesian approach and the test proposed here. For instance, under the same stopping rule of rejecting the null when the posterior odds exceed 1/u, a Bayesian would report a (Bayesian) Type-I error probability of u/(1 + u), whereas a frequentist would report a slightly larger (frequentist) Type-1 error probability of u. One important distinction is that the latter does not depend at all on the realized data, whereas the former depends on the data actually observed. In this sense, the Bayesian answer is a data dependent error probability. The intuition that one is less likely to believe an outcome is a false positive as the test statistic becomes more extreme leads to the notion of conditional frequentist testing (Kiefer (1977)). In conditional frequentist testing one reports the data dependent Type-I error probability α(s) = P(Type I error|S(X) = s) for a suitable conditioning statistic S(X). The challenge in conditional frequentist testing is to find an appropriate conditioning statistic S(X). Dass and Berger (2003) showed that the Bayesian Type I error probabilities are equal to the conditional frequentist Type I error probabilities by choosing the conditioning statistic to be a function of the Bayes factor.
We note that the confidence sequences described in Theorem 3.1 share a connection with other Bayesian intervals discussed in the literature. To see this it is necessary to express the Bayes factor in terms of the Savage-Dickey density ratio (Dickey (1971)) as BF (x 1:n |θ 0 ) = p(θ 0 |M 1 ) p(θ 0 |x 1:n , M 1 ) .
This, with O 0 (θ 0 ) = 1, implies that I n (u) = {θ ∈ d : O n (θ) ≤ 1/u} = {θ ∈ d : p(θ|M 1 ) ≤ p(θ|x 1:n , M 1 )/u}, which is identified as the Bayesian support interval proposed by Wagenmakers et al. (2020). The authors proposed this as an alternative to the more commonly reported Bayesian credible intervals, arguing that the support interval is based on evidence in the data (how the data changes belief), whereas credible intervals are based on posterior belief directly. These intervals have some intuitive appeal as they are the parameter values for which their posterior density has increased beyond some factor of their prior density after observing the data. We are the first, however, to identify the sequential frequentist coverage probabilities, in the sense of Theorem 3.1, of these support intervals.

Acknowledgements
This research was performed while both authors were employed at Optimizely.
It is helpful to introduce some further notation to explicitly express the sequential nature inherent to the problem. The Posterior odds in favor of M 1 to M 0 after observing x 1:n is defined as = p(x n |x 1:n−1 , M 1 ) p(x n |x 1:n−1 , M 0 ) p(M 1 |x 1:n−1 ) p(M 0 |x 1:n−1 ) , = p(x n |θ, x 1:n−1 , M 1 )p(θ|x 1:n−1 , M 1 )dθ p(x n |x 1:n−1 , M 0 ) p(M 1 |x 1:n−1 ) p(M 0 |x 1:n−1 ) , where the last expression stresses the recursive definition of the Posterior odds factor in terms of products of posterior predictive densities. The posterior distribution of θ|x 1:n , M 1 ∼ Dirichlet(α n ) where α n = α n−1 + x n with α 0 the initial prior parameter choice. The posterior predictive densities are easily computed as p(x n |x 1:n−1 , M 1 ) = Γ( i x n,i + 1) i Γ(x n,i + 1) and p(x n |x 1:n−1 , M 0 ) = Γ( i x n,i + 1) It will be useful later on to introduce the following notation for the posterior odds at time n as O n (θ 0 ), which explicitly states the value of θ under the null hypothesis. The recursive definition of the posterior odds can then be expressed as with α n = α n−1 + x n .
and initial value

B Uniform Bounds on the Type-I Error
To result follows from the application of the following two lemmas. Proof.
If Z n is a non-negative supermartingale with respect to the filtration F n , then Proof. See Proof 6.1 of Howard et al. (2020) The result of the Theorem is obtained by using Lemma B.1 to establish that the posterior odds O n (θ 0 ) are a nonnnegative supermartingale under the null hypothesis, and using this observation in Lemma B.2 together with O 0 (θ 0 ) = 1 to obtain the main inequality of the Theorem.
With the Kullback Leibler property of the prior it follows that lim inf 1 n log p(x 1:n |M j ) p(x 1:n |M ) ≥ −δ j a.s.
Combining this result for models M 1 and M 0 completes the proof.

D Manipulating the Rejection Region
Our goal is to find some event R n ⊆ R n that is more amenable to computation; this allows us to obtain a lower bound on the rejection probability since P(R n ) ≥ P(R n ). The proof is by explicit construction, and we begin by deriving a lower bound on Beta(α+Sn) Beta(α) θ −Sn The first inequality follows from the lower bound derived in Lemma D.1. The second inequality follows from so long as α i ≥ 1/2 for each i. Now consider the simpler rejection region It is reassuring to observe that |α| always appears in combination with n. Recall if we choose α = kθ 0 , then |α| = k is interpreted as the prior sample size in a Multinomial-Dirichlet model. The sum |α| + n can be interpreted as the total samples, from the data and the prior.

E Lower Bounding the Stopping Time CDF
In order to assess how quickly the proposed test is able to reject the null, we would like to obtain, or at least lower bound, the probability or rejecting the null hypothesis by a time n. Denote the random stopping time of rejecting the null hypothesis as τ = inf{n : O n (θ 0 ) ≥ 1/u} = inf{n : x 1:n ∈ R n }. A simple lower bound can be obtained as follows P θ [τ ≤ n] ≥ P θ [∃i ≤ n : x 1:i ∈ R i ] ≥ P θ [x 1:n ∈ R n ] ≥ P θ [x 1:n ∈ R n ].
The second inequality is simply stating that the probability of rejecting the null hypothesis is higher if we apply the test after every data point up to and including time n, than simply applying the test at time n. This makes sense, as there are simply more opportunities for the null to be rejected. The last inequality follows from Lemma 3.1. Note that the rejection region R n depends on x 1:n only through the MLEθ(x 1:n ). In what follows it is helpful to considerθ(x 1:n ) as a test statistic at time n, and define a corresponding rejection region as a subset of d at time n. Let this rejection region in d be denoted T n = {θ ∈ d : D KL (θ||θ 0 ) ≥ D n (u, α)}, thenθ(x 1:n ) ∈ T n implies x 1:n ∈ R n . We now combine this with the concentration inequality of Weissman et al. (2003) for the MLE of a multinomial model P θ [θ n ∈ C δ n ] ≥ 1 − δ, where C δ n = {θ ∈ d : θ − θ 1 ≤ 4log 2 δ n }. At any time we now have two sets in d . The first is a rejection set which converges to d \ θ 0 as n → ∞, the second a set which concentrates around the true parameter θ as n → ∞. If the MLE is in the latter with high probability, and this set is totally contained inside the rejection set, then the test statistic is in the rejection set with high probability. This is only possible for large enough n so that θ ∈ T n , after which one chooses the smallest δ satisfying C δ n ⊂ T n , yielding 1 − δ lower bound on the probability of rejection. Because the rejection set T n is defined in terms of the KL divergence, while the concentration set C δ n is defined in terms of the L1-norm, we define T n = {θ ∈ d : θ−θ 0 1 ≥ 2D n (u, α)} ⊆ T n . That T n ⊆ T n follows from a combination two observations. Firstly, by Pinsker's inequality δ(x, θ) ≤ (1/2)D KL (x||θ), where δ(x, θ) denotes the total variation norm of two Multinomial distributions with parameters x and θ. Secondly, the fact that δ(x, θ) = (1/2) x − θ 1 for two multinomial distributions with parameters x and θ. Let N = min{n ∈ N : θ ∈ T n }, this ensures that the the true parameter is in the rejection region T n for all subsequent n, around which a C δ n can be placed for suitably small δ. Let It follows for θ ∈ C δ n , ≥ 2D n (u, α), and therefore that θ ∈ T n . Hence for all n ≥ N P θ [τ ≤ n] ≥ P θ [∃i ≤ n : x 1:i ∈ R i ] ≥ P θ [x 1:n ∈ R n ] ≥ P θ [x 1:n ∈ R n ] = P θ [θ(x 1:n ) ∈ T n ]