Efficiency Of Exchangeability Martingales

There are two different versions of this question:

According to de Finetti's theorem, the difference between the assumptions of randomness and exchangeability disappears (under very weak assumptions about the observation space ⚠ $\mathbf{Z}$) for infinite sequences of observations, since any exchangeable probability distribution is a mixture of IID distributions. For finite sequences of observations, however, there is a difference: e.g., in the case of binary sequences, ⚠ $\mathbf{Z}=\{0,1\}$, it was shown by Vovk (1986), using the language of Kolmogorov's theory of randomness, that a finite binary sequence is random with respect to the IID model if and only if it is exchangeable and the number of 1s in it is random with respect to the binomial model.

One specific version of the question is about testing the assumption of exchangeability for finite sequences of a given length ⚠ $N$. In the simplest version the sequences are binary. Consider a set ⚠ $E$ in ⚠ $\{0,1\}^N$ whose probability is at most ⚠ $\epsilon\in(0,1)$ under any exchangeable probability distribution on ⚠ $\{0,1\}^N$. Does there exist a nonnegative conformal martingale that starts from ⚠ $\epsilon$ (or a number not much greater than ⚠ $\epsilon$ for a small ⚠ $\epsilon$) and ends up with at least 1 on any sequence in ⚠ $E$. (Cf. the definition of game-theoretic probability.) Since conformal martingales are randomized, the condition that the final value is at least 1 can be formalized in different way. The strongest formalization is that it should hold almost surely (over the internal coin tosses of the conformal martingale). A weak formalization is to require that the condition holds on average over the internal coin tosses.

First step towards a solution

Let us consider the following singleton set ⚠ $E$: its only element is ⚠ $k$ 1s followed by ⚠ $(N - k)$ 0s. (This is a toy version of the problem of anomaly detection.) The supremum of ⚠ $P(E)$ over all exchangeable probability distributions is ⚠ $\epsilon:=1/\binom{N}{k}$. There is a deterministic nonnegative conformal martingale that starts from ⚠ $\epsilon$ and ends up with 1 on the event ⚠ $E$. Such a conformal martingale can be obtained from the conformity measure that always regards 0 as less typical than 1 and the base martingale ⚠ $F$ that starts from ⚠ $\epsilon$ and satisfies \[\frac{F(p_1,\ldots,p_{n-1},p_n)}{F(p_1,\ldots,p_{n-1})}:= \begin{cases} 1 & \text{if } n\le k
\frac{n}{n-k} & \text{if } n>k \text{ and } p_n\le\frac{n-k}{n}
0 & \text{if } n>k \text{ and } p_n>\frac{n-k}{n}.\end{cases}\] It is easy to check that all these statements remain true for any singleton ⚠ $E$, with ⚠ $k$ being the number of 1s in the only element of ⚠ $E$.

Bibliography