Entropy, Search, Complexity

Suppose we are given n balls colored with two colors. How many color-comparisons are needed to produce a ball of the majority color? The answer (first given by Saks and Werman) is M(n) = n−B(n), where B(n) is the number of 1’s in the binary representation of n. We consider in this paper several generalizations and variants of the majority problem such as producing a k-majority ball, determining the color status of all balls, arbitrarily many colors, the plurality problem, and the closely related liar problem.

This paper gives a broad overview of the area of searching with errors and the related field of error-correcting coding. In the vast literature regarding this problem, many papers simultaneously deal with various sorts of restrictions on the searching protocol. We partition this survey into sections, choosing the most appropriate section for each topic.

We discuss three types of inclusion matrices (subset, subspace and sequence). We exhibit their disjunct properties and their applications to error-correcting nonadaptive group testing. Under some limited conditions, these structures are optimal for their disjunct properties.

In designing an experiment, we often assume a model and then find a best design satisfying one or more optimal properties under the assumed model. This approach works well when we are absolutely sure about the assumed model that it will fit the experimental data adequately. In reality, we are rarely sure about a particular model in terms of its effectiveness in describing the data adequately. However, we are normally sure about a set of possible models that would describe the data adequately and one of them would possibly describe the data better than the other models in the set. The pioneering work of Srivastava [33] introduced the search linear model with the purpose of searching for and identifying the correct model from a set of possible models that includes the correct model. This paper focuses on model identification through the use of the search linear models, particularly in addressing the fundamental issues and important challenges in statistical design and analysis of experiments while presenting an overview on this area of research. Two important research areas developed over time using the search linear models are in factorial designs and row-column designs.

Topologies related to information divergence are introduced. The conditional limit theorem is taken as motivating example, and simplified proofs of the relevant theorems are given. Continuity properties of entropy and information divergence are discussed.

One of the distinguishing properties of the present scientific method is reproducibility. In one of its guises, probability theory is based on statistical reproduction, near certainty being obtained of truth of statements by averaging over long term to remove randomness occurring in individual experiments. When one assumes, as is often the case, that events farther and farther in the past have less and less influence on the present, the probabilistic paradigm is currently well understood and is successful in many scientific and technological applications. Recently, however, we have come to realize that precisely in these applications important stocahstic processes occur whose present outcomes are significantly influenced by events in the remote past. This behaviour is not at all well understood and some of the simplest questions remain today irritatingly beyond reach. A salient example occurs in the theory of random walks, where there is a dichotomy between recurrent and transient behaviour. After explaining this classical dichotomy, we present a very simple example with infinite memory which is neither known to be transient nor recurrent. Then, using a reinforcement mechanism due to Pólya, we explain the nature of a particular infinite memory process in terms of spontaneous emergence of opinions. Finally we would like to discuss briefly some of our recent results towards understanding the recurrence-transience dichotomy for reinforced random walks.

This lecture is intended to be an easily accessible first introduction to quantum information theory. The field is large and it is not completely covered even by the recent monograph [15]. Therefore the simple topic of data compression is selected to present some ideas of the theory. Classical information theory is not a prerequisite, we start with the basics of Shannon theory to give a feeling for Shannon entropy and for the informational divergence or relative entropy. The aim is to present Schumacher’s compression theorem and to demonstrate that the von Neumann entropy, introduced in the 1920’s by thermodynamical considerations, is a measure of quantum information exactly in the way as the Shannon entropy is that for classical information. Our discussion makes clear that the compression theorem depends heavily on the existence of the high-probability subspace.

Information theory is becoming more and more important for many fields. This is true for engineering- and technology-based areas but also for more theoretically oriented sciences such as probability and statistics.

Recently, many results on the computational complexity of sorting algorithms were obtained using Kolmogorov complexity (the incompressibility method). Especially, the usually hard average-case analysis is ammenable to this method. Here we survey such results about Bubblesort, Heapsort, Shellsort, Dobosiewiczsort, Shakersort, and sorting with stacks and queues in sequential or parallel mode. Especially in the case of Shellsort the uses of Kolmogorov complexity surprisingly easily resolved problems that had stayed open for a long time despite strenuous attacks.

We survey some recent results concerning recognition problems. Recognition problems are special combinatorial search problems, where we need not find the hidden element x itself, just compute the value f(x) for a given function f. We mainly use the approaches of classical search theory and two-party deterministic communication complexity.