E-variables and tests of randomness for distribution classes Georgii Potapov, Yuri Kalnishkan Abstract E E -variables are a relatively new approach for testing statistical hypotheses that has been experiencing major development during the last several years. In this paper we introduce the method of e e -variable-approximability and use it to develop a general approximation technique allowing us to construct e e -variables for popular distribution classes important for applications. E E -variables were originally based on a concept of Levin’s (average-bounded) randomness tests from Algorithmic Information Theory. We show that our construction of e e -variables can be used to provide an explicit construction for a randomness test with respect to a class of distributions. 1 Introductions 1.1 History The problem of statistical hypothesis testing, that is, the problem of deciding whether given data can be described by a certain hypothesis, is naturally important in scientific research as well as applications. Traditionally, hypothesis testing is done using p -values. Intuitively, a p -value is the probability under the null hypothesis that a chosen statistic on the given data is at least as extreme as its observed value. This defines a derivative statistic that we would call p -variable. Despite being widely used, p -values lack certain “natural” properties (for example, the value of a p -variable on a randomly chosen initial segment of the data, in general, is not a p -variable itself), making them easy to accidentally misuse. E -variables are statistical tests that can be viewed as a flexible and versatile alternative to p -variables for statistical hypothesis testing. Formally, an e -variable is a non-negative statistical test with expected value at most 1 ( [ 15 ] ). Their use allows for a flexible experiment design that allows to test against the null for given alternative hypothesis and lacks many disadvantages of the commonly used p -values. E -variables are easy to combine, which simplifies meta-analysis, and running product of e -variables on independent bathces of data is a supermartingale, and thus continues to be an e -variable at random stopping time ( [ 13 , 4 ] ). In this work we revisit the conceptual origin of e -variables — randomness deficiency . Randomness deficiency, introduced by Levin ( [ 8 ] , [ 7 ] ) is a concept from Algorithmic Information Theory, which can be loosely defined as an optimal test of randomness which exponent is an e -variable. Informally speaking, randomness deficiency is a function that counts number of regularities of its argument, a random object, and serves as a measure of how implausible an outcome of an experiment is ( [ 10 ] ). The papers [ 5 ] and [ 14 ] give different but related definitions of a random “Bernoulli bit sequence” in terms of algorithmic randomness. The differences in these definitions correspond to differences between distributions of sequences with i.i.d. bits and exchangeable distributions, and can be quantified using randomness deficiency of number of 1 s in the sequence. One of the results of papers [ 14 ] and [ 12 ] , mentioned in our paper as Theorem 2 , states that, in terms of randomness deficiency, it is approximately as plausible for an integer k between 0 and n to be obtained from some binomial distribution as it would be plausible for k to be obtained from the uniform distribution on integer intervals [s_{j}:s_{j+1}-1]\ni k , where \{s_{1}0 , returns an \varepsilon -appoximation of the object. An \varepsilon -approximation of a probability measure \mathbb{P} would be a measure \mathbb{P}_{\varepsilon}=\sum_{i=1}^{n}p_{i}\delta_{x_{i}} concentrated on a finite number of rational points x_{i} and assigning them rational probabilities p_{i} , such that \mathbb{P}_{\varepsilon} is \varepsilon -close to \mathbb{P} in Lévy–Prokhorov metric, that is, for all measurable sets A we have \mathbb{P}(A)<\mathbb{P}_{\varepsilon}(A^{\varepsilon})+\varepsilon,~~~\mathbb{P}(A^{\varepsilon})>\mathbb{P}_{\varepsilon}(A)-\varepsilon, where A^{\varepsilon} is the \varepsilon -neighbourhood of A . 2.3 Randomness tests Definition 2.5 (Randomness test) . For a measurable space \mathcal{X} , consider a function f(\cdot|\cdot,\cdot):\mathcal{X}\times\mathfrak{P}(\mathcal{X})\times\mathcal{Y}\to[0,\infty] , which takes as its arguments an object x\in\mathcal{X} , a probability distribution \mathbb{P} on \mathcal{X} and an auxiliary object in y\in\mathcal{Y} . We say that f is a uniform randomness test (or a test of randomness in a sense of Levin), if it is: 1. a lower semicomputable function (assuming an appropriate computable structure on \mathcal{X},\mathfrak{P}(\mathcal{X}) and \mathcal{Y} ), 2. for all probability measures \mathbb{P} and all strings y the function f(\cdot\mid\mathbb{P},y) is an e -variable for the simple hypothesis \{\mathbb{P}\} . From a practical point of view, lower semi-computability is a very mild restriction that allows us to construct a universal test of randomness (described below). Philosophically, lower semi-computability represents the idea that, if an e -variable rejects the null with a chosen significance level, than this must be eventually established from the data measured with high enough but finite precision. The next theorem-definition is a well known result. Theorem 1 (existence and definition of a universal uniform test ( [ 8 , 2 , 11 ] )) . For \mathcal{X} that is of the form \{0,1\}^{*},\{0,1\}^{\omega},\mathbb{R}^{n} and \mathcal{Y} that is either one of these sets or the set of bounded measures on such sets, there exists a uniform randomness test \mathbf{t} such that for any uniform randomness test f there is a constant C_{f}>0 , depending only on \mathbf{t} and f , for which the inequality \mathbf{t}(x\mid\mathbb{P},y)\geq C_{f}f(x\mid\mathbb{P},y) holds for any x,\mathbb{P},y . Any such test is called a universal uniform randomness test , or simply a universal test . From now on we are going to use symbols =^{+},\leq^{+} , \geq^{+} , =^{\times} , \leq^{\times} , \geq^{\times} to denote that an (in)equality holds up to an additive or a multiplicative constant. For any universal tests \mathbf{t}_{1} and \mathbf{t}_{2} we have \mathbf{t}_{1}=^{\times}\mathbf{t}_{2} , so for the rest of the paper we fix an arbitrary universal test and refer to it as \mathbf{t} . The current paper is mainly concerned with studying the following object. Definition 2.6 . For a family of probability distributions \mathcal{P} , we define randomness test relative to \mathcal{P} as the \inf -projection \mathbf{t}^{\mathcal{P}}(x\mid y)=\inf_{\mathbb{P}\in\mathcal{P}}\mathbf{t}(x\mid\mathbb{P},y). In this paper we are concerned with finding explicit expressions for \inf -projections, thus directly proving that randomness test for a class is a l.s.c. function. We will show this for many important families of distributions \mathcal{P} , listed below. Our technique generalises and extends the approach of [ 12 , 14 ] , where the following theorem is proved. Theorem 2 ( [ 12 , 14 ] ) . For any natural number n let \operatorname{Bern}_{n}=\{\operatorname{Bern}(n,p)\}_{p\in[0,1]} be the family of distributions on \{0,1\}^{n} with i.i.d. bits, and \operatorname{Bin}_{n}=\{\operatorname{Bin}(n,p)\}_{p\in[0,1]} be the family of binomial distributions on [0:n]=\{0,1,\ldots,n\} . Then for any string x\in\{0,1\}^{n} and any number k\in[0:n] \displaystyle\mathbf{t}^{\operatorname{Bern}_{n}}(x) \displaystyle=^{\times}\mathbf{t}(x\mid\operatorname{Bern}(n,\hat{p}(|x|_{1}/n))), \displaystyle\mathbf{t}^{\operatorname{Bin}_{n}}(k) \displaystyle=^{\times}\mathbf{t}(k\mid\operatorname{Bern}(n,\hat{p}(k/n))) \displaystyle=^{\times}\mathbf{t}\left(k\mid\ \mathcal{U}\left(\hat{p}^{-1}(\hat{p}(k/n)\right)\right), where \hat{p} is a computable function that maps a rational number of the form m/n , {m\in[0:1]} , to the nearest element of the “net” {\left\{\sin^{2}\left(\frac{\pi t}{2\lfloor\sqrt{n}\rfloor}\right)\right\}_{t\in[1:\lfloor\sqrt{n}\rfloor]}} . We are going to prove similar results for the following families of distributions: • Uniform distribution on [0:n]=\{0,1,\ldots,n\} , \{\mathcal{U}([0:n])\}_{n\in\mathbb{N}} , • Poisson distributions, \{\operatorname{Pois}(\lambda)\}_{\lambda>0} , • uniform distributions on real intervals, \{\mathcal{U}([0,\theta])\}_{\theta>0} , • normal distributions with fixed variance \{\mathcal{N}(\mu,1)\}_{\mu\in\mathbb{R}} , • normal distributions with fixed mean value \{\mathcal{N}(0,\sigma^{2})\}_{\sigma^{2}>0} , • Cauchy distributions with fixed scale \{\operatorname{Cauchy}(x_{0},1)\}_{x_{0}\in\mathbb{R}} . Our methods differ significantly from those in [ 12 , 14 ] . We are going to prove our results (formulated precisely in section 4 ) by showing that all the distribution families in question are what we call e -variable-approximable, which by itself mean that they admit a certain construction of e -variable for the family from e -variables for individual distributions. 2.4 Organisation In section 3 , we are going to formulate a number of technical results on e -variables that do not include any computability requirements: subsection 3 states the definition of e -variable-approximability and lists the main results about this notion, subssection 3.2 describes continuously interpolated versions of e -variables constructed in subsection 3 , which we would need for making our functions l.s.c. in section 4 . In section 4 , we will use these results for e -variables to construct l.s.c. approximations of \inf -projections for the claimed families of distributions. Most of the proofs are deferred to the appendix. In section 5 we discuss our choice of definitions, scale of applicability of our results and perspectives for further research. All non-standard notation is listed in the appendix. 3 E -variable-approximability 3.1 Main results on e -variable-approximability Here we introduce one of the main concepts in our work, the notion of e -variable approximability of a distribution family. Definition 3.1 . We say that a family \mathcal{H} of distributions is e -variable approximable (from the net \mathcal{S} ) (with factor C ) , if there exists an at most countable set \mathcal{S} , called a net , a set of distributions \{\mathbb{P}_{s}\}_{s\in\mathcal{S}}\subset\mathcal{H} , a function \hat{s}:\mathbb{R}\to\mathcal{S} that we would call an estimator and a constant C>0 such that for any family of non-negative statistical tests \{e_{s}\}_{s\in\mathcal{S}} , if for all s the test e_{s} is an e -variable under the simple hypothesis \{\mathbb{P}_{s}\} , then the test e(x)=\frac{1}{C}e_{\hat{s}(x)}(x) is an e -variable under the hypothesis \mathcal{H} . This definition might seem somewhat artificial at first, and so we provide some argumentation and examples in Section 5 . The following lemmas provide easily verifiable conditions for establishing e -variable approximability. Lemma 1 . Let \mathcal{H}=\{\mathbb{P}_{\theta}\}_{\theta\in\Theta} be a family of distributions on \mathbb{R}^{n} with densities \{p_{\theta}\}_{\theta\in\Theta} , parametrised by the elements of \Theta\subseteq\mathbb{R} , and let \mathcal{S}\subseteq\Theta be an at most countable set such that \operatorname{succ}_{\mathcal{S}}(\theta)=\min\{s\in\mathcal{S}\mid\theta0\} we have that \log\frac{p_{\theta}(x)}{p_{s}(x)}=d(g(x)\|s)-d(g(x)\|\theta); (p ii) there is a constant c^{\prime}>0 such that for any s\in\mathcal{S} and any x for which x\in\hat{s}^{-1}(s) we have d(g(x)\|s)0 such that for all \theta_{1},\theta_{2}\in\Theta,\theta_{1}<\theta_{)} , it holds that d(\theta_{1}\|\theta_{2})\geq(1+\alpha)\log(k-1),~~~d(\theta_{2}\|\theta_{1})\geq(1+\alpha)\log(k-1), for k=\left|\mathcal{S}\cap(\theta_{1},\theta_{2})\right| 1 1 1 for this statement, we treat the logarithm of non-positive numbers as -\infty . If all the properties (p i) – (p iv) of the data (\mathcal{H},\mathcal{S},\Theta,\hat{s},g,d) hold, then \mathcal{H} is e -variable approximable from the net \mathcal{S} and the estimator \hat{s} , and the constant factor C can be taken as C=\exp(c^{\prime})\left(7+2/\alpha\right) . Lemma 2 . In lemma 1 , condition (p iv) follows from the following two conditions: (p i’) if \theta_{1}\leq\theta_{2}\leq\theta_{3} or \theta_{1}\geq\theta_{2}\geq\theta_{3} , then d(\theta_{1}\|\theta_{3})\geq d(\theta_{1}\|\theta_{2})+d(\theta_{2}\|\theta_{3}); (p ii’) there is a constant c>0 such that for any consecutive s,s^{\prime}\in\mathcal{S} , it holds that d(s\|s^{\prime})>c,\quad d(s^{\prime}\|s)>c. If all the properties (p i) – (p iii) of the data (\mathcal{H},\mathcal{S},\Theta,\hat{s},g,d) in lemma 1 hold, together with (p i’) and (p ii’) , then \mathcal{H} is e -variable approximable from the net \mathcal{S} and the estimator \hat{s} , and the constant factor C can be chosen as C=\exp(c^{\prime})\left(5+\frac{2}{\mathrm{e}^{c}-1}\right) . Both lemmas are proven by carefully estimating the terms in the right-hand side of \mathbb{E}_{\theta}e_{\hat{s}(X)}(X)=\sum_{s\in\mathcal{S}}\int_{\hat{s}^{-1}(s)}e_{s}(x)\frac{p_{\theta}(x)}{p_{s}(x)}p_{s}(x){\rm d}x to provide a uniform upper bound on the sum. We will see that in many cases checking the conditions of either of two lemmas is straightforward. In particular, it can be easily checked for many standard exponential families. Lemma 3 . Let \{\mathbb{P}_{\eta}\}_{\eta\in H} , with H an open (possibly infinite) interval in \mathbb{R} , be an exponential family canonically parametrised by \eta with support D\subset\mathbb{R}^{n} and densities p_{\eta}(x)=h(x)\exp\left(\eta T(x)-A(\eta)\right) . 1. If there is a function \hat{\eta}:D\to H that solves the likelihood equation T(x)=\mathbb{E}_{\hat{\eta}(x)}T(X) , for all x\in D , then condition of (p i) of lemma 1 holds for d=\operatorname{kl} and g=\hat{\eta} . 2. The condition (p i’) of lemma 2 holds for d=\operatorname{kl} . Theorem 3 . The following families of distributions are e -variable-approximable. The function \hat{s} is omited whenever \hat{s}=\operatorname{round}_{\mathcal{S}} . • \{\operatorname{Bin}(n,p)\}_{p\in(0,1)} , from the net \mathcal{S}=\left\{\sin^{2}\left(\frac{\pi t}{2\lfloor\sqrt{n}\rfloor}\right)\right\}_{00}} , from the net \{t^{2}\}_{t\in\mathbb{N}} . The following families of continuous distributions are also e -variable-approximable: • \{\mathcal{U}([0,\theta])\}_{\theta>0} , from the net \mathcal{S}=\{2^{n}\}_{n\in\mathbb{Z}} , \hat{s}(x)=2^{\lceil\log_{2}x\rceil} • \{\mathcal{N}(\mu,1)^{\otimes n}\}_{\mu\in\mathbb{R}} , from the net \mathcal{S}=\frac{\alpha}{\sqrt{n}}\mathbb{Z} for \alpha>0 , \hat{s}(x_{1:n})=\operatorname{round}_{\mathcal{S}}\left(\frac{1}{n}\sum_{k}x_{k}\right) , the factor may depend on \alpha but does not depend on n ; • \{\mathcal{N}(0,\sigma^{2})^{\otimes n}\}_{\sigma\in\mathbb{R}_{>0}} , from the net \mathcal{S}=\left\{\left(1+\frac{1}{\sqrt{n}}\right)^{k}\right\}_{k\in\mathbb{Z}} , \hat{s}(x)=\operatorname{round}_{\mathcal{S}}\left(\frac{\|x\|^{2}}{n}\right) , the factor does not depend on n ; • \{\operatorname{Cauchy}(x_{0},1)\}_{x_{0}\in\mathbb{R}} , from the net \mathcal{S}=\mathbb{Z} . For any \varepsilon\leq 1/5 and let r^{\varepsilon} be any function defined on \mathbb{R}\setminus\left(\mathbb{Z}+0.5\right)^{\varepsilon} as \operatorname{round}_{\mathbb{Z}} , and on for each \varepsilon -neighbourhood of a half-integer n+0.5 defined as either n or n+1 (maybe differently for each n ), then \{\mathcal{N}(\mu,1)\}_{\mu\in\mathbb{R}} and \{\operatorname{Cauchy}(x_{0},1)\}_{x_{0}\in\mathbb{R}} are both e -variable approximable from \mathcal{S}=\mathbb{Z} and \hat{s}=r^{\varepsilon} . Corollary . For all n and x_{1:n}\in\mathbb{R}^{n} , let r_{n}(x_{1:n})=\operatorname{round}_{\frac{1}{\sqrt{n}}\mathbb{Z}}\left(\frac{1}{n}\sum_{k}x_{k}\right) . For some constant C>0 , the following holds. For any \{e_{\mu}\}_{\mu\in\mathbb{R}} , a family of measurable functions, such that each e_{\mu} is an e -variable w.r.t. \{\mathcal{N}(\mu,1)\} , the function e(x_{1:n})=\frac{1}{C}\prod_{k=1}^{n}e_{r_{n}(x_{1:n})}(x_{k}) is an e -variable for \{\mathcal{N}(\mu,1)^{\otimes n}\}_{\mu\in\mathbb{R}} . The corollary immediately follows from Theorem 3 and the fact that a product of e -variables is an e -variable for the product distribution. 3.2 Interpolating approximation Discontinuity of \operatorname{round}_{\mathcal{S}} makes this function uncomputable for distributions on real numbers, which prevents us from applying our results directly to randomness deficiency. For \operatorname{round}_{\mathbb{R}} we would like to “smoothen” the transition between n and n+1 , and similarly for \operatorname{round}_{\mathcal{S}} in general. Definition 3.2 . We say that the family \{\mathbb{P}_{\theta}\}_{\theta\in\Theta} is continuously e -variable-approximable from the net \mathcal{S}\subset\Theta if there is a set of functions \{\hat{s}(\cdot,s)\}_{s\in\mathcal{S}} , constituting a partition of unity, and a constant C>0 such that a function e defined as e(x)=\frac{1}{C}\sum_{s\in\mathcal{S}}e_{s}(x)\hat{s}(x,s) is an e -variable for \mathcal{P} whenever all e_{s} are e -variables for corresponding \{\mathbb{P}_{s}\} . Theorem 4 . For \mathcal{P}=\{\mathbb{P}_{\theta}\}=\{\mathcal{N}(\theta,1)\}_{\theta\in\mathbb{R}} or \{\operatorname{Cauchy}(\theta,1)\}_{\theta\in\mathbb{R}} , for any \{e_{n}\}_{n\in\mathbb{Z}} such that e_{n} is an e -variable for \{\mathbb{P}_{n}\} , there is a constant C>0 such that for any \varepsilon\leq 1/5 the function e^{\varepsilon}(x)=\frac{1}{C}\sum_{n=-\infty}^{\infty}e_{n}(x)\mathbb{I}_{\left[n-\frac{1}{2}+\varepsilon,n+\frac{1}{2}-\varepsilon\right]}^{2\varepsilon}(x) is an e -variable for \mathcal{P} . Note that for any x at most two terms in the sum are non-zero. The proof illustrates flexibility of e -variable approximability property. Proof. Notice that an e -variable multiplied by a continuous [0,1] -valued function is also an e -variable For a given family \{e_{n}\}_{n\in\mathbb{Z}} , define two new families: \{e_{n}^{\textrm{even}}\}_{n\in\mathbb{Z}} and \{e_{n}^{\textrm{odd}}\}_{n\in\mathbb{Z}} in the following way. Let e_{n}^{\textrm{even}} be equal to e_{n}\cdot\mathbb{I}^{2\varepsilon}_{[n-0.5-\varepsilon,n+0.5+\varepsilon]} for even n , and equal to 0 for odd n ; similarly for e_{n}^{\textrm{odd}} . Let \hat{s}_{\textrm{even}} be the rounding function \operatorname{round}_{\mathbb{Z}} , redefined on \varepsilon -neighbourhoods of half-integers to round to the nearest even number. We define \hat{s}_{\textrm{odd}} in a similar way. Then there is some C_{0}>0 such that both e^{\textrm{even}}(x)=\frac{1}{C_{0}}e^{\textrm{even}}_{\hat{s}_{\textrm{even}}(x)}(x) and e^{\textrm{odd}}(x)=\frac{1}{C_{0}}e^{\textrm{odd}}_{\hat{s}_{\textrm{even}}(x)}(x) are e -variables with respect to \mathcal{P} . Arithmetic mean of two e -variables is trivially an e -variable, and so for C=2C_{0} we obtain that e^{\varepsilon}(x)=\frac{e^{\textrm{even}}(x)+e^{\textrm{odd}}(x)}{2}=\frac{1}{C}\sum_{n=-\infty}^{\infty}e_{n}(x)\mathbb{I}_{\left[n-\frac{1}{2}+\varepsilon,n+\frac{1}{2}-\varepsilon\right]}^{2\varepsilon}(x) is also an e -variable w.r.t. \mathcal{P} . ∎ 4 Lower semicomputable approximations of randomness deficiency \inf -projection We say that a family of distributions \{\mathbb{P}_{\theta}\}_{\theta\in\Theta} is computable if the function (\theta\mapsto\mathbb{P}_{\theta}) is computable. Lemma 4 . For a computable family of distributions \mathcal{P}=\{\mathbb{P}_{\theta}\}_{\theta\in\Theta} on a discrete set \mathcal{X} that is e -variable-approximable from a net \mathcal{S} with a computable estimator \hat{s} and factor C , then there is a randomness test f:\mathcal{X}\times\mathfrak{P}(\mathcal{X})\times\mathcal{Y}\to[0,\infty] such that f(x\mid\mathbb{P}_{\theta},y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y) for all \theta\in\Theta . Sketch of the proof. The proof technique is standard for the field. Lower semi-computability of \mathbf{t} together with computability of \mathbb{P} allows us to enumerate a list of bounded continuous piece-wise linear functions 0=g_{0}\leq g_{1}\leq\ldots with finite description, with g_{n}(x,y)\uparrow\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y) . For these function we can estimate integrals \int g_{n}(x,y)\mathbb{P}({\rm d}x) . Without loss of generality, we say that C\geq 1 and rational. We can then define f(x\mid\mathbb{P},y)=\frac{1}{2}\sup_{n}\left\{g_{n}(x,y)\mid\int g_{n}(x,y)\mathbb{P}({\rm d}x)<2C\right\}. From e -variable-approximability it follows that the condition on integral being less than 2C is always true for \mathbb{P}\in\mathcal{P} , and thus f=^{\times}\mathbf{t} in this case. ∎ Theorem 5 . For a computable family \mathcal{P}=\{\mathbb{P}_{\theta}\}_{\theta\in\Theta} that is e -variable-approximable with a computable estimator \hat{s} , it holds that \mathbf{t}^{\mathcal{P}}(x\mid y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y). Proof. Let f be the uniform test from lemma 4 . For any \theta f(x\mid\mathbb{P}_{\theta},y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y), where the right hand term does not depend on \theta . We get then, that for any \theta f(x\mid\mathbb{P}_{\theta},y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y)\geq\mathbf{t}^{\mathcal{P}}(x\mid y). From optimality of randomness deficiency we also obtain that \mathbf{t}(x\mid\mathbb{P}_{\theta},y)\geq^{\times}f(x\mid\mathbb{P}_{\theta},y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y). Since constants under \geq^{\times},=^{\times} do not depend on x,\theta,y , we can take the infimum over all \theta and get \mathbf{t}^{\mathcal{P}}(x\mid y)\geq^{\times}\mathbf{t}(x\mid\mathbb{P}_{\hat{s}(x)},y), which concludes the proof. ∎ Lemma 5 . For a computable family of distributions \mathcal{P}=\{\mathbb{P}_{\theta}\}_{\theta\in\Theta} that is continuously e -variable-approximable from a uniformely computable net \mathcal{S}=\{s_{i}\}_{i\in\mathcal{I}} , \mathcal{I}\subset\mathbb{N} with \hat{s} being l.s.c. uniformely in both arguments, and factor C , then there is a randomness test f:\mathcal{X}\times\mathfrak{P}(\mathcal{X})\times\mathcal{Y}\to[0,\infty] such that f(x\mid\mathbb{P}_{\theta},y)=^{\times}\sum_{s\in\mathcal{S}}\mathbf{t}(x\mid\mathbb{P}_{s},y)\hat{s}(x,s) for all \theta\in\Theta . Lemma 6 . Let \mathcal{P}=\{\mathbb{P}_{\theta}\}_{\theta\in\mathbb{R}} be either \{\mathcal{N}(\theta,1)\}_{\theta\in\mathbb{R}} or \{\operatorname{Cauchy}(\theta,1)\}_{\theta\in\mathbb{R}} . Let n be an integer and x\in[n,n+1] . Then \mathbf{t}(x\mid\mathbb{P}_{n},y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{n+1},y). This lemma can be proven using the same technique as lemma 4 after noticing that there is a computable function on distribution that on the elements of \mathcal{P} recovers the parameter. An example of such function would be a function that computes \mathbb{E}_{\mathbb{P}}\arctan(X) for given \mathbb{P} and recovers the would-be parameter by assuming that \mathbb{P} is from \mathcal{P} . Theorem 6 . Let \mathcal{P}=\{\mathbb{P}_{\theta}\}_{\theta\in\mathbb{R}} be either \{\mathcal{N}(\theta,1)\}_{\theta\in\mathbb{R}} or \{\operatorname{Cauchy}(\theta,1)\}_{\theta\in\mathbb{R}} . Then \mathbf{t}^{\mathcal{P}}(x\mid y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor},y). Proof. Let f be the uniform test from lemma 5 and \hat{s}(x,n)=\mathbb{I}^{0.2}_{[n-0.4,n+0.4]}(x) in accordance with theorem 4 . Then, just as in the proof of theorem 5 we can claim that \mathbf{t}^{\mathcal{P}}(x\mid y)=^{\times}\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor},y)\hat{s}(x,\lfloor x\rfloor)+\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor+1},y)\hat{s}(x,\lfloor x\rfloor+1). Now, from lemma 6 we obtain that \mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor},y)\hat{s}(x,\lfloor x\rfloor)+\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor+1},y)\hat{s}(x,\lfloor x\rfloor+1)\geq^{\times}\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor},y), and so \mathbf{t}^{\mathcal{P}}(x\mid y)\geq^{\times}\mathbf{t}(x\mid\mathbb{P}_{\lfloor x\rfloor},y)\geq\mathbf{t}(x\mid y). ∎ 5 Discussions 5.1 Discussion of definition 3.1 In Section 3 we introduced the notion of e -variable approximability. This notion might not seem very intuitive, so let us consider a few examples when seemingly more intuitive ways to combine e -variables fail. First, we will demonstrate that using a simple \inf -projection ( x\mapsto\inf_{\theta}e_{\theta}(x) ) might lead to non-measurable functions. Example 1 . Let us consider a family of normal distributions \{\mathcal{N}(\mu,1)\}_{\mu\in\mathbb{R}} and some non-measurable set L\subset\mathbb{R} . For each \mu\in L let e_{\mu}(x)=\mathbb{I}\{x\neq\mu\} , and for all \mu\notin L let e_{\mu}\equiv 1 . Then all the functions e_{\mu} are measurable with \mathbb{E}_{\mu}e_{\mu}(X)=1 , but the function \inf_{\mu}e_{\mu}(x)=\mathbb{I}\{x\notin L\} is not measurable and thus cannot serve as a statistical test. Remark . Taking an infimum over a countable set would preserve measurability, but it is weaker (up to a multiplicative constant) than our proposed approach and, what is also important for us, does not preserve lower semi-computability. The next two example shows that for non-trivial families we cannot use maximum likelihood estimator for \hat{s} Example 2 . Let us consider a family of normal distributions \{\mathcal{N}(\mu,1)\}_{\mu\in\mathbb{R}} and an arbitrary constant C>) . For each value of \mu we define a function e_{\mu}(x)=C\cdot 10^{100}\mathbb{I}\{x=\mu\} . Then, obviously, each e_{\mu} is measurable and \mathbb{E}_{\mu}e_{\mu}(X)=0\leq 1 , hence all e_{\mu} are e -variables, but at the same time for all \mu we have \mathbb{E}_{\mu}\frac{1}{C}e_{\operatorname{MLE}(x)}(x)=\frac{1}{C}\mathbb{E}_{\mu}e_{x}(x)=10^{100}>1 . Example 3 . Let us consider a family of Poisson distributions \{\operatorname{Pois}(\lambda)\}_{\lambda>0} , then \operatorname{MLE}(x)=x . For each natural number n define a function e_{n}(x)=\frac{1}{\operatorname{Pois}(n)(\{n\})}\mathbb{I}\{x=n\}=\exp(n)\frac{n!}{n^{n}}\mathbb{I}\{x=n\} . Then each e_{n} is measurable and \mathbb{E}_{n}e_{n}(X)=1 , hence all e_{n} are e -variables, but at the same time for all \lambda>0 we have \mathbb{E}_{\lambda}e_{\operatorname{MLE}(X)}(X)=\mathbb{E}_{\lambda}e_{X}(X)=\exp(X)\frac{X!}{X^{X}}>1 . Moreover, since \exp(x)\frac{x!}{x^{x}}\sim\sqrt{2\pi x} , for any C>0 there will be a large enough \lambda for which \mathbb{E}_{\lambda}\frac{1}{C}e_{X}(X)>1 . 5.2 Further research There are several directions which we think are worth investigating further. In theorem 3 we see that there may be many different nets for the same family of distributions and even many different estimators for the same net. This naturally leads to the question of characterising the nets and finding which nets and estimators allow the optimal normalising factor. Estimators in our work are based on the idea that the data represents information about the distribution that is distorted by random noise, so we need to “trim” the data in order to reduce the impact of the noise while leaving useful information. This view is closely related to the Minimum Description Length principle, and it might be interesting to explore further how theory behind MDL principle can be used to improve our results. Appendix A Notaion • \mathrm{e} stands for the constant \mathrm{e}=2.71\ldots to distinguish from e , which we will use in namings of e -variables • |A| and \#A are interchangeable and stand for the cardinality of a set A • |x| stands for the absolute value of a number x • \|x\| stands for the Euclidean norm of a point x\in\mathbb{R}^{n} • x_{1:n} stands for a point in \mathbb{R}^{n} with coordinates x_{1},x_{2},\ldots,x_{n} . • a\leq^{+}b stands for a\leq b+C for some numerical constant C , similarly for \geq^{+} • a\leq^{\times}b stands for a\leq Cb for some numerical constant C>0 , similarly for \geq^{\times} • a=^{+}b means that both a\leq^{+}b and b\leq^{+}a hold, similarly for a=^{\times}b • [l:r] stands for the set \{n\in\mathbb{Z}\mid l\leq n\leq r\} • A^{\varepsilon} is the \varepsilon -neighbourhood of a set A • \mathbb{I}_{A} stands for the indicator function of a set A • \mathbb{I}_{A}^{\varepsilon} stands for the bounded continuous approximation of \mathbb{I}_{A} which is 1 on A , 0 on the complement of A^{\varepsilon} and linearly interpolates between 1 and 0 on A^{\varepsilon}\setminus A • \operatorname{round}_{\mathcal{S}} stands for the function that maps a real number to the closest element of a discrete set \mathcal{S}\subset\mathbb{R} ; when there are two such elements, \operatorname{round}_{\mathcal{S}} could be either of those for the purposes of our paper • \operatorname{kl}(\theta_{1}\|\theta_{2}) stands for the Kullback–Leibler divergence \operatorname{KL}(\mathbb{P}_{\theta_{1}}\|\mathbb{P}_{\theta_{2}}) when the family \{\mathbb{P}_{\theta}\}_{\theta\in\Theta} is uniquely determined by the context • \mathbb{E}_{\theta} stands for \mathbb{E}_{\mathbb{P}_{\theta}} when the family \{\mathbb{P}_{\theta}\}_{\theta\in\Theta} is uniquely determined by the context • \mathfrak{P}(\mathcal{X}) stands for the set of all probability measures on \mathcal{X} • \mathbf{t} denotes a universal uniform randomness test, arbitrarily chosen and fixed for this paper • the index set is always specified in an indexed set notation to prevent confusion with singleton sets, that is, notation \{\mathbb{P}_{\theta}\} always stands for a singleton set and is never an abbreviation of \{\mathbb{P}_{\theta}\}_{\theta\in\Theta} Appendix B Proofs about e -variable-approximability B.1 Proofs of lemmas Proof of lemma 1 . We want to show that \frac{1}{C}e_{\hat{s}(X)}(X) is an e -variable. That is, we need to show that, for all \theta\in\Theta \int_{\mathbb{R}^{n}}e_{\hat{s}(x)}(x)\mathbb{P}_{\theta}({\rm d}x)\leq C. First, for each s\in\mathcal{S} we denote \mathcal{X}_{s}=\hat{s}^{-1}(s)\subseteq\mathbb{R}^{n} . Now, \displaystyle\int_{\mathbb{R}^{n}}e_{\hat{s}(x)}(x)\mathbb{P}_{\theta}({\rm d}x) \displaystyle=\sum_{s\in\mathcal{S}}\int_{\mathcal{X}_{s}}e_{s}(x)p_{\theta}(x){\rm d}x \displaystyle=\sum_{s\in\mathcal{S}}\int_{\mathcal{X}_{s}}\frac{p_{\theta}(x)}{p_{s}(x)}e_{s}(x)p_{s}(x){\rm d}x \displaystyle\overset{\text{by \ref{prop:loglike-to-d}}}{=}\sum_{s\in\mathcal{S}}\int_{\mathcal{X}_{s}}\exp\Big[d(g(x)\|s)-d(g(x)\|\theta)\Big]e_{s}(x)p_{s}(x){\rm d}x denote C_{s}=C_{s,\theta}=\sup_{x\in\mathcal{X}_{s}}d(g(x)\|s)-d(g(x)\|\theta) \displaystyle\leq\sum_{s\in\mathcal{S}}\exp(C_{s})\int_{\mathcal{X}_{s}}e_{s}(x)p_{s}(x){\rm d}x \displaystyle\leq\sum_{s\in\mathcal{S}}\exp(C_{s})\underbrace{\int_{\mathbb{R}^{n}}e_{s}(x)p_{s}(x){\rm d}x}_{\leq 1,\textrm{ by def. of $e$-var.}} \displaystyle\leq\sum_{s\in\mathcal{S}}\exp(C_{s}). We now have to estimate the sum \sum_{s\in\mathcal{S}}\exp(C_{s}). By (p ii) we have C_{s,\theta}\leq c^{\prime}-\inf_{x\in\mathcal{X}_{s}}d(g(x)\|\theta), and, from non-negativity of d , it follows that C_{s}\leq c^{\prime}. Whenever s\geq\operatorname{succ}_{\mathcal{S}}^{(k+1)}(\theta) for some k , then \operatorname{pred}_{\mathcal{S}}(s)\geq\operatorname{succ}_{\mathcal{S}}^{(k)}(\theta) , and, by (p iii) for all x\in\mathcal{X}_{s} : g(x)>\operatorname{pred}_{\mathcal{S}}(g(x))\geq\operatorname{pred}_{\mathcal{S}}(s)\geq\operatorname{succ}_{\mathcal{S}}^{(k)}(\theta)>\theta, and \left|\mathcal{S}\cap(g(x),\theta)\right|\geq k , and, by (p iv) we have: d(g(x)\|\theta)\geq(1+\alpha)\log(k-1),~~\forall x\in\mathcal{X}_{s}, and so, in this case C_{s,\theta}\leq c^{\prime}-(1+\alpha)\log(k-1) . Similarly, we get the same bound for s\leq\operatorname{pred}_{\mathcal{S}}^{(k+1)}(\theta) . Putting this all together, we get \displaystyle\sum_{s\in\mathcal{S}}\exp(C_{s,\theta}) \displaystyle\leq\left(\sum_{\begin{subarray}{c}s\leq\operatorname{pred}_{\mathcal{S}}^{(3)}(\theta)\\ s\in\mathcal{S}\end{subarray}}+\sum_{\begin{subarray}{c}\operatorname{succ}_{\mathcal{S}}^{(3)}(\theta)\leq s\\ s\in\mathcal{S}\end{subarray}}+\sum_{\begin{subarray}{c}s\in\mathcal{S}\\ \operatorname{pred}_{\mathcal{S}}^{(3)}(\theta)0} follows from Lemma 2 . ∎ Proof for normal distributions with fixed variance. Density p_{\mu} of \mathcal{N}(\mu,1)^{\otimes n} is p_{\mu}(x_{1:n})=\frac{1}{\sqrt{2\pi}}\mathrm{e}^{-\|x_{1:n}^{2}\|/2}\exp\left(\mu\sum_{k}x_{k}-\frac{n\mu^{2}}{2}\right), and, since \sum_{k}x_{k}=\mathbb{E}_{\frac{\sum x_{k}}{n}}\sum_{k}X_{k} from Lemma 3 we get properties (p i) and (p i’) for d(\theta_{1}\|\theta_{2})=\operatorname{kl}(\theta_{1}\|\theta_{2})=\frac{n}{2}(\theta_{1}-\theta_{2})^{2} and g(x_{1:n})=\frac{\sum_{k}x_{k}}{n} . To prove property (p ii) , we note that x_{1:n}\in\hat{s}^{-1}(s) means that \left|\frac{\sum_{k}x_{k}}{n}-s\right|\leq\frac{\alpha}{2\sqrt{n}} , and so d(g(x_{1:n})\|s)=\frac{n}{2}(g(x_{1:n})-s)^{2}\leq\frac{n}{2}\frac{\alpha^{2}}{4n}=\frac{\alpha^{2}}{8}. Since \hat{s}(x)=\operatorname{round}_{\mathcal{S}}(g(x)) , the property (p iii) is trivial. The difference between the consecutive elements s,s^{\prime} of the net is exactly \frac{\alpha}{\sqrt{n}} , so d(s\|s^{\prime})=\frac{n}{2}\frac{\alpha^{2}}{n}=\frac{\alpha^{2}}{2}, which establishes property (p ii’) and finishes the proof. ∎ Normal distribution with zero mean value. We have p_{\sigma^{2}}(x_{1:n})=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\|x_{1:n}\|^{2}}{2\sigma^{2}}-\frac{n}{2}\log\sigma^{2}\right). Since \|x_{1:n}\|^{2}=\sum_{k}x_{k}^{2} and all the coordinates are i.i.d., we have T(x_{1:n})=\mathbb{E}_{g(x_{1:n})}T(X_{1:n}) for T(x_{1:n})=-\frac{1}{2}\sum_{k}x_{k}^{2} and g(x_{1:n})=\frac{\|x_{1:n}\|^{2}}{n} . As canonical parametrisation \eta=1/\sigma^{2} reverses order, we still get the reverse triangle inequality (p i’) when defining d=\operatorname{kl} in terms of variance, and thus can continue to work in standard parametrisation. For two variances \sigma^{2}_{1},\sigma^{2}_{2} , we have \operatorname{kl}(\sigma^{2}_{1}\|\sigma^{2}_{2})=\frac{n}{2}\left(\frac{\sigma^{2}_{1}}{\sigma^{2}_{2}}-\log\frac{\sigma^{2}_{1}}{\sigma^{2}_{2}}-1\right). Since \hat{s}(x)=\operatorname{round}_{\mathcal{S}}(g(x)) , we immediately get (p iii) . We also have that for any s=\hat{s}(x) that g(x)/s\in\left[\frac{\sqrt{n}}{1+\sqrt{n}},\frac{1+\sqrt{n}}{\sqrt{n}}\right] , and for consecutive s,s^{\prime}\in\mathcal{S} we have s/s^{\prime}\in\left\{\frac{\sqrt{n}}{1+\sqrt{n}},\frac{1+\sqrt{n}}{\sqrt{n}}\right\} . Let h(t)=\frac{n}{2}\left(t-\log t-1\right) , then \operatorname{kl}(\sigma^{2}_{1}\|\sigma^{2}_{2})=h\left(\sigma^{2}_{1}/\sigma^{2}_{2}\right) . First, we will show (p ii’) . \displaystyle h\left(\frac{1+\sqrt{n}}{\sqrt{n}}\right) \displaystyle=\frac{n}{2}\left(1+\frac{1}{\sqrt{n}}-\underbrace{\log\left(1+\frac{1}{\sqrt{n}}\right)}_{\leq\frac{1}{\sqrt{n}}-\frac{1}{4n}}-1\right) \displaystyle\geq\frac{n}{2}\left(\frac{1}{\sqrt{n}}-\frac{1}{\sqrt{n}}+\frac{1}{4n}\right) \displaystyle\geq\frac{1}{8}, \displaystyle h\left(\frac{\sqrt{n}}{1+\sqrt{n}}\right) \displaystyle=\frac{n}{2}\left(1-\frac{1}{1+\sqrt{n}}-\underbrace{\log\left(1-\frac{1}{1+\sqrt{n}}\right)}_{\leq-\frac{1}{1+\sqrt{n}}-\frac{1}{4\left(1+\sqrt{n}\right)^{2}}}-1\right) \displaystyle\geq\frac{n}{2}\left(-\frac{1}{1+\sqrt{n}}+\frac{1}{1+\sqrt{n}}+\frac{1}{4\left(1+\sqrt{n}\right)^{2}}\right) \displaystyle\geq\frac{1}{32}, so for any two consecutive elements s,s^{\prime} of the net we have d(s\|s^{\prime})\geq 1/32 . Now, to show (p ii) , let t be between -\frac{1}{1+\sqrt{n}} and \frac{1}{\sqrt{n}} . \displaystyle h(1+t) \displaystyle=\frac{n}{2}((1+t)-\underbrace{\log(1+t)}_{\geq t-t^{2}}-1) \displaystyle\leq\frac{n}{2}(t-t+t^{2}) \displaystyle\leq\frac{|t|^{2}n}{2} \displaystyle\leq\frac{1}{n}\frac{n}{2}=\frac{1}{2} ∎ Proof for Cauchy distributions. For Cauchy distributions, we have p_{\theta}(x)=\frac{1}{\pi(1+(x-\theta)^{2})} , and so \log\frac{p_{\theta}(x)}{p_{s}(x)}=\log\left(1+(x-s)^{2}\right)-\log\left(1+(x-\theta)^{2}\right). Take g(x)=x , d(\theta_{1}\|\theta_{2})=\log\left(1+(\theta_{1}-\theta_{2})^{2}\right)\geq\log 1=0 . For \hat{s}=r^{\varepsilon} , we have that x\in\hat{s}^{-1}(n)\implies x\in[n-0.5-\varepsilon,n+0.5+\varepsilon] , so d(x\|n)\leq\log(1+(0.5+\varepsilon)^{2})\leq\log 2. Property (p iii) for r^{\varepsilon} follows from the same observation in a straightforward manner. Now, assume there are k integers between \theta_{1} and \theta_{2} . Then |\theta_{1}-\theta_{2}|\geq k-1 and d(\theta_{1}\|\theta_{2})=\log\left(1+(\theta_{1}-\theta_{2})^{2}\right)\geq 2\log(k-1). The result now follows from Lemma 1 . ∎ Proof for normal distributions with r^{\varepsilon} . The proof is mostly identical to the proof for \operatorname{round}_{\mathcal{S}} with a slightly weaker bounds. ∎ Appendix C Proofs for randomness tests All the lemmas in section 4 follow from Theorem 4.1.1. in [ 3 ] , which we here restate. Theorem 7 . Let \phi_{e} , e\in\mathbb{N} , be an enumeration of all l.s.c. functions on \mathcal{X}\times\mathfrak{M}(\mathcal{X})\times\mathcal{Y}\to[0,\infty] . where \mathfrak{M}(\mathcal{X}) is the set of all bounded measures on \mathcal{X} . Let b:\mathcal{Y}\times\mathfrak{M}(\mathcal{X})\to[0,\infty] be a l.s.c. function. There is a recursive function e\mapsto e^{\prime} with the following properties. For each e , the function \phi_{e^{\prime}} is everywhere defined and its integral is bounded by b(\mathbb{P},y) . For each e,y,\mathbb{P} , if \mathbb{E}_{\mathbb{P}}\phi_{e}(X\mid\mathbb{P},y)