Entropy, Search, Complexity (eBook)

Contents 6
Preface 8
Two Colors and More 10
1. The majority problem 10
2. First Generalization: Determining a k-majority 12
3. Second generalization: more colors 17
4. Third generalization: the plurality problem 20
5. The liar problem 23
6. A final generalization: determining the color classes 26
References 27
Coding with Feedback and Searching with Lies 28
1. Introduction 28
2. Definitions and terminology 31
3. A Berlekamp strategy and the translation bound 33
4. Linear growth 35
5. Fixed error 35
6. Asymptotic results for fixed error 38
7. Fixed number of messages 39
8. Fast algorithm 40
9. Comparison and interval questions 41
10. Asymmetric questions 43
11. Detecting errors 44
12. Linearly bounded error 45
13. Local restrictions 47
14. Unbounded search 47
15. Optimal strategies with minimum adaptiveness 49
16. The continuous case 50
17. Q-ary case 54
18. The probabilistic case 57
19. Search and information theory 59
20. Identification and a general search model 61
21. The game without feedback 62
22. Learning and searching 63
23. Unequal protection with feedback 64
References 67
Nonadaptive and Trivial Two-Stage Group Testing with Error-Correcting de-Disjunct Inclusion Matrices 72
1. Group testing 72
2. Inclusion matrices 73
3. de-disjunct matrices 76
4. Some optimal de-disjunct matrices with constant rowweight 81
5. Remarks 82
References 82
Model Identification Using Search Linear Models and Search Designs 86
1. Introduction 86
2. Search linear model 88
3. Search procedure, search probabilities, and performance evaluation 88
4. Search designs 90
5. Statistical design of scientific experiments 96
6. The information provided by an experiment 98
7. Some elegant combinatorial problems arising in search designs 102
8. Analysis under the general slm using simulation distributions 105
References 110
Information Topologies with Applications 114
1. Introduction and preliminaries 114
2. The strong information topology 121
3. Continuity of entropy and divergence 128
4. Weak information topologies 135
5. The conditional limit theorem 141
6. Discussion 148
References 149
Reinforced Random Walk 152
An open problem 152
Spontaneous emergence of opinions 154
The current state of affairs 158
References 159
Quantum Source Coding and Data Compression 160
1. Classical source coding 160
2. Quantum mechanical sources 167
3. Extension to sources with memory 172
4. Appendix 174
References 178
Information Theory at the Service of Science 180
1. Introduction, background 180
2. Game Theoretical Equilibrium, the idea 183
3. Information theoretical concepts 184
4. Instances of GTE 188
5. Technical discussion of the Dmin-game 194
References 205
Analysis of Sorting Algorithms by Kolmogorov Complexity ( A Survey) 210
1. Introduction 210
2. Bubblesort 214
3. Heapsort 216
4. Shellsort 220
5. Dobosiewicz Sort and Shakersort 225
6. Sorting with queues and stacks 227
References 232
Recognition Problems in Combinatorial Search 234
1. Introduction 234
2. Preliminaries 235
3. Recognition problems 241
4. The generalized communication model 247
5. Recognition problems in partially ordered sets 253
6. Predetermined complexity 260
7. Open problems 263
References 264