2021/01/31 by Aaditya Ramdas, Ramdas, Aaditya, Johannes Ruf +5 · 5 citations
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Game Theory and Voting Systems #Italy: Economic History and Contemporary Issues
paper · pdf · doi:10.48550/arxiv.2102.00630
Suppose we observe an infinite series of coin flips X1,X2,\…, and\nwish to sequentially test the null that these binary random variables are\nexchangeable. Nonnegative supermartingales (NSMs) are a workhorse of sequential\ninference, but we prove that they are powerless for this problem. First,\nutilizing a geometric concept called fork-convexity (a sequential analog of\nconvexity), we show that any process that is an NSM under a set of\ndistributions, is also necessarily an NSM under their "fork-convex hull".\nSecond, we demonstrate that the fork-convex hull of the exchangeable null\nconsists of all possible laws over binary sequences; this implies that any NSM\nunder exchangeability is necessarily nonincreasing, hence always yields a\npowerless test for any alternative. Since testing arbitrary deviations from\nexchangeability is information theoretically impossible, we focus on Markovian\nalternatives. We combine ideas from universal inference and the method of\nmixtures to derive a "safe e-process", which is a nonnegative process with\nexpectation at most one under the null at any stopping time, and is upper\nbounded by a martingale, but is not itself an NSM. This in turn yields a level\n\α sequential test that is consistent; regret bounds from universal\ncoding also demonstrate rate-optimal power. We present ways to extend these\nresults to any finite alphabet and to Markovian alternatives of any order using\na "double mixture" approach. We provide an array of simulations, and give\ngeneral approaches based on betting for unstructured or ill-specified\nalternatives. Finally, inspired by Shafer, Vovk, and Ville, we provide\ngame-theoretic interpretations of our e-processes and pathwise results.\n