The basic modeling problem begins with a set of observed data yn = {yt : t = 1, 2, …, n}, generated by some physical machinery, where the elements yt may be of any kind. Since no matter what they are they can be encoded as numbers we take them as such, i.e. natural numbers with or without the order if the data come from finite or countable sets, and real numbers otherwise. Often each number yt is observed together with others x1,t, x2,t, …, called explanatory data, written collectively as a K × n matrix X = {xi,j}, and the data then are written as yn ∣X. It is convenient to use the terminology “variables” for the source of these data. Hence, we say that the data {yt} come from the variable Y, and the explanatory data are generated by variables X1, X2, and so on.

In physics the explanatory data often determine the data yn of interest, called a “law,” but not so in statistical problems. Although by taking sufficiently many explanatory data we may also fit a function to the given set of observed data, but this is not a “law,” since if the same machinery were to generate additional data yn+1, x1,n+1, x2,n+1, … the function would not give yn+1. This is the reason the objective is to learn the statistical properties of the data yn, possibly in the context of the explanatory data.

This book has two parts: the first summarizes the facts of coding and information theory which are needed to understand the essence of estimation and statistics, and the second describes a new theory of estimation, which also covers a good part of statistics as well. After all, both estimation and statistics are about extracting information from the often chaotic looking data in order to learn what it is that makes the data behave the way they do. The first part together with an outline of the algorithmic information in Appendix A is meant for the statistician who wants to understand his or her discipline rather than just learn a bag of tricks with programs to apply them to various data, tricks that are not based on any theory and do not stand a critical examination although some of them can be quite useful, providing solutions for important statistical problems.

The word information has many meanings, two of which have been formalized by Shannon. The first is fundamental in communication as just the number of messages, strings of symbols, either to be stored or to be sent over some communication channel, the practical question being the size of the storage device needed or the time it takes to send them. The second meaning is the measure of the strength of the statistical property a string has, which is fundamental in statistics, and very different from that in communication.

I have a long lasting interest in estimation, which started with attempts to control industrial processes. It did not take long to realize that the control part is easy if you knew the behavior of the process you want to control, which meant that the real problem is estimation. When I was asked by the Information Theory Society to give the 2009 Shannon Lecture I thought of giving a coherent survey of estimation theory. However, during the year given to prepare the talk I found that it was not possible, because there was no coherent theory of estimation. There was a collection of facts and results but they were isolated with little to connect them. To my surprise this applied even to the works of some of the greatest names in statistics, such as Fisher, Cramér, and Rao, which I had been familiar with for decades, but which I had never questioned until now that I was more or less forced to do so. As an example, the famous maximum likelihood estimator due to Fisher [12] had virtually no formal justification. The celebrated Cramér-Rao inequality gives it a non-asymptotic justification only for special models and for more general parametric models only an asymptotic justification. Clearly, no workable theory should be founded on asymptotic behavior. About the value of asymptotics, we quote Keynes' famous quip that “asymptotically we all shall be dead.”

We begin with the description of the most basic and primitive codes. Let A = a1, …, ak be a finite set: the set is called an alphabet, and its elements are called symbols. The main interest is in the set of finite sequences sn = aiaj … of the symbols of some length n, called messages or for us just data. The problem is to send or store them in a manner that costs the sending device little time and storage space. Again for practical reasons these devices use binary symbols 0 and 1, while the original symbols are represented as a sequence of binary symbols, such as the eight bits long “bytes.” Let for each symbol a in A, C: a ↦ C(a) be a one-to-one map, called a code, from the alphabet into the set of binary strings. It is extended to the messages by concatenation C : aiaj … an ↦ C(ai)C(aj) … C(an). Both binary strings C(a) and C(ai)C(aj) … C(an) are called codewords.

This will give us an upside down binary tree, with the root on top, whose nodes are the codewords, first of the symbols for n = 1 and then of the length 2 messages, and so on. The left hand tree in Figure 2.1 illustrates the code for the symbols of the alphabet A = {a, b, c}.

Customarily, hypothesis testing is about the problem of finding out if some effect of interest, like the curing power of a drug, is supported by observed data, or if it is a random “fluke” rather than a real effect of the drug. To have a formal way to test this a certain probability hypothesis is set up to represent the effect. This can be done by selecting a function of the data, s(xn), called a test statistic, the distribution of which can be calculated under the hypothesis. Frequently parametric probability distributions have a special parameter value to represent randomness, like 1/2 in Bernoulli models for binary data and 0 for the mean of normal distributions, and the no effect case can be represented by the single model such as f(s(xn); θ0), called the null hypothesis. The test statistic is or should be in effect an estimator of the parameter, and if the data cause the test statistic to fall in the tail, into a so-called critical region of small probability, say 0.05, the null hypothesis is rejected, indicating by the double negation that the real effect is not ruled out. Fisher called the amount of evidence for the rejection of the null hypothesis the statistical significance on the selected level 0.05, which is frequently misused to mean that there is 95 percent statistical significance to accept the real effect.

The word “information” has several meanings, the simplest of which has been formalized for communication by Hartley [17] as the logarithm of the number of elements in a finite set. Hence the information in the set A = {a, b, c, d} is log 4 = 2 (bits) in the base 2 logarithm. Only two types of logarithm are used in this book: the base 2 logarithm which we write simply as log, and the natural logarithm, written as ln. The amount of information in the set A = {a, b, c, d, e, f, g, h} is three bits, and so on. Hence such a formalization has nothing to do with any other meaning of the information communicated, such as the utility or quality. If we were asked to describe one element, say c in the second set, we could do it by saying that it is the third element, which could be done with the binary number 11 in both sets, but the element f in the second set would require three bits, namely 011. So we see that if the number of elements in a set is not a power of 2, we need either the maximum ∣log ∣A∣ number of bits or one less, as will be explained in the next section. Hence, we start seeing that “information,” relative to a set, could be formalized and measured by the shortest code length with which any element in a set could be described.

Although the material in this appendix is not used directly in the rest of the book, it has a profound importance in understanding the very essence of randomness and complexity, which are fundamental to probabilities and statistics. The algorithmic information or complexity theory is founded on the theory of recursive functions, the roots of which go back to the logicians Godel, Kleen, Church, and above all to Turing, who described a universal computer, the Turing machine, whose computing capability is no less than that of the latest supercomputers. The field of recursiveness has grown into an extensive branch of mathematics, of which we give just the very basics, which are relevant to statistics. For a comprehensive treatment we refer the reader to [26].

The field is somewhat peculiar in that the derivations and proofs of the basic results can be performed in two very different manners. First, since the partial recursive functions can be axiomatized as is common in other branches of mathematics the proofs are similar. But since the same set is also defined in terms of the computer, the Turing machine, a proof has to be a program. Now, the programs as binary strings of that machine are very primitive, like the machine language programs in modern computers, and they tend to be long and both hard to read and hard to understand. To shorten them and make them more comprehensible an appeal is often made to intuition, and the details are left to the reader to fill in.

Now that we know how to estimate real-valued parameters optimally the question arises of how confident we can be in the estimated result, which requires infinite precision numbers. It is clear that if we repeat the estimation on a new set of data, generated by the same physical machinery, the result will not be the same. It seems that the model class is too rich for the amount of data we have. After all, if we fit Bernoulli models to a binary string of length n, there cannot be more than 2n properties in the data that we can learn, even if no two strings have a common property. And yet the model class has a continuum of parameter values, each representing a property.

One way to balance the learnable information in the data and the model class is to restrict the precision in the estimated parameters. However, we should not take any fixed precision, for example each parameter quantized to two decimals, because that does not take into account the fact that the sensitivity of models with respect to changes in the parameters depends on the parameters. The problem is related to statistical robustness, which while perfectly meaningful is based on practical considerations such as a model's sensitivity to outliers rather than on any reasonably comprehensive theory. If we stick to the model classes of interest in this book the parameter precision amounts to interval estimation.