# 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.