In which I talked about Olszewksi and Sandroni’s paper `Manipulability of future independent tests’ and coupling of stochastic processes.
Recap Every day Nature randomizes the weather for that day ( for rain, for no rain). An Expert delivers a forecast which he claims governs Nature’s selection, so that the expert claims that is the probability of rain at day when the weather in previous days was . We denote by the set of all forecasts. We compare the expert’s forecast to the actual infinite realization of weather. A test function is given by . An expert who provided a forecast is rejected if . We say that the test does not reject the true expert with probability if for every forecast , where is the distribution over realizations induced by .
We now look at a special class of tests, which are sequential and also reject the expert on finite times. Such tests are given by a set of finite sequences of predictions and outcomes: Let be the outcome of day and be the prediction about day generated by the forecast . Then the expert fails if after some day it turns out that . Thus,
Note that it is possible (for some choices of — see comment below) that the expert is never off the hook — there is always the potential that he will fail the test. (On the other hand, in Sandroni’s Theorem with set of realizations at day there is a final verdict, either the expert pass or failed.)
Theorem 1 (Olszewski and Sandroni (2009)) Let be a test of the form (1) that does not reject the true expert with probability . Then for every there exists such that
Again, if the expert randomizes his forecasts according to a distribution , he is unlikely to fail the test regardless of the actual realization . In fact, Olszewksi and Sandroni state and prove their theorem under weaker condition on the test, which they call `future independence’. The proof is the same as the proof given below, so I can skip the definition the future independence without depriving you of any math.
The proof of the theorem follows the idea of the proof of Sandroni’s Theorem for the case of finite set of realizations. We define a game between two players, Nature and Expert: Nature chooses a realization and Expert chooses a forecast , and the payoff that Expert pays Nature is given by , where is the indicator function of . In order to use Fan’s Theorem we will need a small twist on the game: We are going to restrict the Expert’s pure strategies set in the game to be such that the prediction of day is in some finite grid. (it is a good idea at this point to figure out for yourself what goes wrong if we don’t add this restriction):
Fix . We denote by the set of forecasts defined below, in which the experts predictions are restricted at every day to a finite grid in :
The following Lemma, which I will prove later, will imply that the Expert player in the game does not lose much if we restrict his strategy set to .
— Proof of Theorem —
Consider a two-player zero sum games between Nature and Expert: Nature chooses a realization and Expert, simultaneously and independently, chooses a forecast . Then Expert pays Nature an amount .
We first claim that the maximin of the game is at most . Indeed, let be a mixed strategy of Nature. Then for some . Let satisfy (3). If Nature plays and Expert responds with then the expected payoff that Expert pays Nature is
where the equality follows from the definition of , the first inequality from Lemma 2 and the second inequality from the fact that does not reject the truth with probability .
If we can show that the minimax is smaller than then an optimal mixed strategy of the Expert in the game will satisfy (2). All is left to do is to check that the conditions of Fan’s Theorem are satisifed, so that the minimax equals the maximin. Indeed, the set of pure strategies of the Expert is compact as a countable product of finite sets, each equipped with the discrete topology. Moreover, in this topology is l.s.c. for every (Skip the next paragraph if this is obvious).
Lower semi-continuity means that whenever . For the case of indicator functions the inequality means that if then for sufficiently large . So let and assume that . Then for some where . Convergence of to in the product topology is pointwise convergence, so for every . Since for every the last limit means that for sufficiently large . Take large enough so that the equality is satisfied for every of length or smaller. Then for such the predictions made by along equal those made by until day . It follows that , as desired.
— Weather coupling —
The best way I know to prove Lemma 2 is by using coupling. This is a powerful technique to prove relations between two random variables by embedding them in the same probability space.
Imagine that Zeus randomizes the weather in Athens according to and Baal randomizes the weather in Askelon according to .
One way Zeus can perform the randomization task is using a sequence of i.i.d random variables distributed uniformly on : After he decided on the weather Zeus makes the -th rainy (i.e. decide that ) iff . Assume now that Baal uses the same technique only with instead of to randomize the weather in Askelon and that Baal uses the same sequence of i.i.d uniform random variables that Zeus uses.
Then the distribution of the weather in Askelon is . Moreover because of (3), the weather in Askelon is likely to be the same as the weather in Athens. In fact the probability that the weather will differ at some day is at most ! Now is the probability that the realized weather sequence in Athens is in and is the probability that the realized weather sequence in Askelon is in . Since the probability that these sequences differ is smaller than it follows that , as desired.