Efficiency Of Exchangeability Martingales

Open.EfficiencyOfExchangeabilityMartingales History

Hide minor edits - Show changes to output

May 31, 2017, at 06:37 PM by Vovk - solution for singletons
Added line 20:
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$.
Changed line 10 from:
Let us consider the following singleton set $E$ consisting of one element: $k$ 1s followed by $(N - k)$ 0s.  (This is a toy version of the problem of [[Main/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
to:
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 [[Main/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
Changed line 10 from:
Let us consider the singleton set $E$ consisting of one element: $k$ 1s followed by $(N - k)$ 0s.  (This is a toy version of the problem of [[Main/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
to:
Let us consider the following singleton set $E$ consisting of one element: $k$ 1s followed by $(N - k)$ 0s.  (This is a toy version of the problem of [[Main/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
Changed line 6 from:
One specific version of the question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exist a nonnegative [[Main/testing | 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 [[Main/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 on the conformal martingale).  A weak formalization is to require that the condition holds on average over the internal coin tosses.
to:
One specific version of the question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exist a nonnegative [[Main/testing | 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 [[Main/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.
Changed line 23 from:
* Vladimir Vovk (1986). [[https://arxiv.org/abs/1612.08859 | On the concept of the Bernoulli property]]. Russian Mathematical Surveys 41:247-248.
to:
* Vladimir Vovk (1986). [[https://arxiv.org/abs/1612.08859 | On the concept of the Bernoulli property]]. ''Russian Mathematical Surveys'' 41:247-248.
Changed line 6 from:
One specific version of the question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exist a nonnegative [[Main/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 [[Main/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 on the conformal martingale).  A weak formalization is to require that the condition holds on average over the internal coin tosses.
to:
One specific version of the question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exist a nonnegative [[Main/testing | 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 [[Main/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 on the conformal martingale).  A weak formalization is to require that the condition holds on average over the internal coin tosses.
May 20, 2017, at 06:13 PM by Vovk - described a first step
Changed lines 6-20 from:
One specific version of this question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exists 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 [[Main/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 on the conformal martingale).  A weak formalization is to require that the condition holds on average over the internal coin tosses.
to:
One specific version of the question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exist a nonnegative [[Main/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 [[Main/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 on 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 singleton set $E$ consisting of one element: $k$ 1s followed by $(N - k)$ 0s.  (This is a toy version of the problem of [[Main/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$ and $p_n\le\frac{n-k}{n}$}\\
    0 & \text{if $n>k$ and $p_n>\frac{n-k}{n}$}.
  \end{cases}
\]

May 20, 2017, at 05:54 PM by Vovk - fixed the question
Added lines 5-6:

One specific version of this question is about testing the [[Main/exchangeable probability distribution | 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 [[Main/exchangeable probability distribution | exchangeable probability distribution]] on $\{0,1\}^N$.  Does there exists 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 [[Main/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 on the conformal martingale).  A weak formalization is to require that the condition holds on average over the internal coin tosses.
Changed lines 2-3 from:
* for testing the [[randomness assumption | assumption of randomness]]
* and for testing the [[exchangeable probability distribution | assumption of exchangeability]].
to:
* for testing the [[Main/randomness assumption | assumption of randomness]]
* and for testing the [[Main/exchangeable probability distribution | assumption of exchangeability]].
May 13, 2017, at 06:48 PM by Vovk - created the page
Added lines 1-7:
There are two different versions of this question:
* for testing the [[randomness assumption | assumption of randomness]]
* and for testing the [[exchangeable probability distribution | assumption of exchangeability]].
According to [[https://en.wikipedia.org/wiki/De_Finetti%27s_theorem | 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.

'''Bibliography'''
* Vladimir Vovk (1986). [[https://arxiv.org/abs/1612.08859 | On the concept of the Bernoulli property]]. Russian Mathematical Surveys 41:247-248.