# Conformal testing

The main property of validity of conformal transducers is that they output a sequence of p-values `⚠ $p_1,p_2,\ldots$`

that are independent and uniformly distributed on `⚠ ${0,1]}$`

; therefore, the whole sequence is uniformly distributed on `⚠ ${[0,1]}^{\infty}$`

. This can be used for testing the assumption of randomness (or a different on-line compression model) on-line. Namely, fix a martingale `⚠ $S$`

on the probability space `⚠ ${[0,1]}^{\infty}$`

with the uniform distribution (and standard filtration: `⚠ $\mathcal{F}_n$`

is the `⚠ $\sigma$`

-algebra generated by the first `⚠ $n$`

coordinates of `⚠ ${[0,1]}^{\infty}$`

); we will say that `⚠ $S$`

is a *test martingale* if it is non-negative, `⚠ $S_n\ge0$`

for all `⚠ $n$`

, and starts from 1, `⚠ $S_0=1$`

. Therefore, `⚠ $S_n$`

only depends on the first `⚠ $n$`

numbers `⚠ $p_1,\ldots,p_n$`

of its argument `⚠ $(p_1,p_2,\ldots)\in[0,1]^{\infty}$`

. The *base martingale* `⚠ $S$`

and the conformal transducer then define the process `⚠ $M_n:=S_n(p_1,\ldots,p_n)$`

that is an *exchangeability martingale*, i.e., a martingale with respect to any exchangeable distribution on `⚠ $\mathbf{Z}^{\infty}$`

. Such processes `⚠ $M_n$`

are called *conformal exchangeability martingales*. They are randomized in that `⚠ $M_n$`

depends not only on the first `⚠ $n$`

observations `⚠ $z_1,\ldots,z_n$`

but also on the internal coin tosses of the conformal transducer. We say that a conformal exchangeability martingale is a *test conformal martingale* if its base martingale is a test martingale. More generally, a *test exchangeability martingale* is a nonnegative exchangeability martingale with initial value 1.

Conformal exchangeability martingales are a natural tool for anomaly detection.

There is an unrelated notion of a conformal martingale in stochastic calculus: see, e.g., Revuz and Yor (1999), Section V.2. Therefore, it is best to avoid dropping "exchangeability" in "conformal exchangeability martingale" (and there is a hope that the conformal exchangeability martingales are the only exchangeability martingales, in which case the term "conformal exchangeability martingales" will become redundant).

### Open questions

- Investigating the efficiency of exchangeability martingales as a tool for testing the assumption of randomness remains an unexplored direction of further research. A similar question can also be asked about other on-line compression models.
- Universality of conformal exchangeability martingales.

**Bibliography**

- Valentina Fedorova, Ilia Nouretdinov, Alex Gammerman, and Vladimir Vovk (2012). Plug-in martingales for testing exchangeability on-line. In:
*Proceedings of the Twenty Ninth International Conference on Machine Learning*, pp. 1639-1646. Omnipress. - Daniel Revuz and Mark Yor (1999).
*Continuous Martingales and Brownian Motion*. Springer, Berlin. - Vladimir Vovk, Alexander Gammerman, and Glenn Shafer (2005).
*Algorithmic learning in a random world*. Springer, New York. - Vladimir Vovk, Ilia Nouretdinov, and Alex Gammerman (2003). Testing exchangeability on-line. In:
*Proceedings of the Twentieth International Conference on Machine Learning*, pp. 768-775. AAAI Press, Menlo Park, CA.