{'fraction_non_alphanumeric': 0.05096639172719439, 'fraction_numerical': 0.019327834543887725, 'mean_word_length': 4.119092627599244, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Conformal testing: binary case with Markov alternatives

We continue study of conformal testing in binary model situations. In this note we consider Markov alternatives to the null hypothesis of exchangeability. We propose two new classes of conformal test martingales; one class is statistically efficient in our experiments, and the other class partially sacrifices statistical efficiency to gain computational efficiency.


Introduction
This note treats a problem similar to the one considered in [2]: we would like to test online the null hypothesis of exchangeability of binary observations under Markov alternatives.
The simplest way of online hypothesis testing is to use test martingales, which are defined as nonnegative processes with initial value 1 that are martingales under the null hypothesis; see, e.g., [3]. Such processes, for the null hypothesis of exchangeability, can be constructed using the method of conformal prediction [6], and we will refer to them as conformal test martingales. A previous paper [4] constructs custom-made conformal test martingales for different alternative hypotheses, those of a changepoint.
The method of [2], which is specifically devoted to Markov alternatives, is more general: instead of a test martingale the authors construct a "safe e-process" (to be defined in the next section). Safe e-processes are closely related to test martingales and admit a similar interpretation as the capital of a gambler trying to discredit the null hypothesis. Our methods give similar results to the methods of [2] in the model situations that we consider (following [2]). The advantage of our methods is that they extend easily to the usual setting of machine learning, where the observations are pairs (x, y) consisting of a potentially complex object x and its label y.
In this note we only design conformal test martingales for a simple alternative hypothesis (a specific probability measure). This is different from [2], who are interested in testing against the composite alternative Markov hypothesis. As in [2], we could mix our conformal test martingales over the possible alternative hypotheses, but we leave this step for future research.

Model situations
This section introduces the model situations considered in this paper, following [2,Section 4.2]. Our data consist of binary observations generated from a Markov model. We will use the notation Markov(π 1|0 , π 1|1 ) for the probability distribution of a Markov chain with the transition probabilities π 1|0 for transitions 0 → 1 and π 1|1 for transitions 1 → 1; the probability that the first observation is 1 will always be assumed 0.5. In the hard case, the model is Markov(0.4, 0.6), and in the easy case, the model is Markov(0.1, 0.9). The number of observations is N := 10 4 (as in [2]) or N := 10 3 or N := 10 2 ; we will refer to these scenarios as large, medium, and small, respectively.
In all our experiments we use 2021 as the seed for the NumPy pseudorandom number generator. (This, however, does not make the trajectories in our plots comparable between different scenarios.) The dependence on the seed will be explored in boxplots reported in Section 5; the seed affects not only the data but also the values of conformal martingales, which are randomized processes, given the data.
Ramdas et al. construct a safe e-process R = R n : namely, under any Ber(π), R is dominated by a test martingale M (π) n w.r. to Ber(π), in the sense that R n ≤ M (π) n for all n and π. The trajectories of their process for the two cases, hard and easy, are shown in Figure 1 (they coincides with those in Figure 4 in [2] apart from using base 10 logarithms and a different randomly generated dataset). The figure also shows trajectories of the Simple Jumper martingale (see, e.g., [5]) for various values of the jumping rate; it performs poorly in this    context.
The trajectories of the upper and lower benchmarks are shown in Figure 2 in red and green; the figure also shows the trajectory the R process discussed in the previous section, and the other two trajectories should be ignored for now. The two benchmarks coincide or almost coincide. Figure 3 should the same trajectories "under the lens", over the last 1000 observations.

Bayesian conformal testing
In this section we will use a Bayesian method that is statistically efficient in our experiments but whose computational efficiency will be greatly improved in the next section. The p-values p 1 , p 2 , . . . are generated as described in [4]; in particular, we are using the identity nonconformity measure (the nonconformity score of an observation z is z). Under the alternative hypothesis, the p-values are generated by a completely specified stochastic mechanism. According to [1,Theorem 2], the optimal (in the Kelly-type sense of that paper) betting functions f n are given by the density of the predictive distribution of p n conditional on knowing p 1 , . . . , p n−1 . Let us find these predictive distributions. We will use the notation U [a, b], where a < b, for the uniform probability distribution on the interval [a, b] (so that its density is 1/(b − a)).
We are in a typical situation of Bayesian statistics. The Bayesian parameter is the binary sequence (z 1 , z 2 , . . . ) ∈ {0, 1} ∞ of observations, and the prior distribution on the parameter is Markov(π 1|0 , π 1|1 ). The Bayesian observations are the conformal p-values p 1 , p 2 , . . . . Given the parameter, the distribution of p n is where k := z 1 + · · · + z n is the number of 1s among the first n observations. Let w n k,j , where n = 1, 2, . . . , k = 0, . . . , n, and j ∈ {0, 1}, be the total posterior probability of the parameter values z 1 , z 2 , . . . for which z 1 +· · ·+z n = k and z n = j; we will use them as the weights when computing the predictive distributions for the p-values. We can compute the weights w n k,j recursively in n as follows. We start from At each step n ≥ 2, first we compute the unnormalized weights w n k,0 := w n−1 k,0 π 0|0 + w n−1 k,1 π 1|0 l n−1 k (0, p n ), where l is the likelihood defined by Given the posterior weights for the previous step, we can find the predictive distribution for p n as where we use the shorthand π 0|j := 1 − π 1|j . Therefore, the betting functions for the resulting Bayes-Kelly conformal test martingale are For experimental results, see Figure 4, in addition to Figure 2. The Bayes-Kelly conformal test martingale appears to be very close to the two benchmarks. Its simplified version is described in the next section. The relatively poor performance of the R-process in the left panel of Figure 4 should not be interpreted as it being inferior to the Bayes-Kelly conformal test martingale: remember that R works against all Markov alternatives, whereas the other processes in

Simplified Bayesian conformal testing
In this section we consider a radical simplification of the Bayes-Kelly conformal test martingale (1). We still assume that the Markov chain is symmetric, as in our model situations. If we assume that the weights w n k,j , k = 0, . . . , n, are concentrated at k ≈ k + 1 ≈ n/2, (1) will simplify to f n (p) = 2π 1|j 1 p≤0.5 + 2π 0|j 1 p>0.5 .
(2) Figure 5 shows the weights (averaged over j ∈ {0, 1}) for the last step of the Bayes-Kelly conformal test martingale in the medium scenario (10 3 observations). They are indeed concentrated around values of k not so different from 0.5N = 500. As a second step, we make (2) straightforward to compute by setting j := 1 if p n−1 ≤ 0.5 0 if not.
(If k(n − 1) := z 1 + · · · + z n−1 ≈ (n − 1)/2, then j = z n−1 with high probability.) The performance of the simplified version is shown in Figures 2-4 and 6. It is usually worse than that of the Bayes-Kelly conformal test martingale and the two benchmarks, but is comparable on the log scale apart from the right panel of Figure 6. The right panel of Figure 6 and Figures 7 and 8 show that the statistical performance of the simplified Bayes-Kelly martingale particularly suffers in the easy case. The notches in the boxplots in Figures 7 and 8 indicate confidence intervals for the median.