scientific article; zbMATH DE number 107482
asymptotic equipartition propertybroadcast channelchannel capacitychannel coding theoremChernoff boundcoding theoremcorrelated sourcesCramer Rao inequalitydata compressionerror probabilityFano's inequalityFisher informationGaussian channelhalting problemHamming codeshypothesis testinginference channelinformation theoryKolmogorov complexityKraft inequalitylarge deviation theorylaw of large numbersmaximum entropymethod of typesmulti-user information theorymultiple access channelnetwork information theoryNeyman Pearson lammaprobability theoryrate distortion theoryrelay channelShannon-Fano-Elias codingside informationSlepian-Wolf theoremsource codesspectral estimationthermodynamicsTuring machinetwo way channeluniversal coding
Statistical aspects of information-theoretic topics (62B10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to information and communication theory (94-01) Information theory (general) (94A15) Measures of information, entropy (94A17) Rate-distortion theory in information and communication theory (94A34)
The opening sentence of the book reads: ``This is intended to be a simple and accessible book on information theory. As Einstein said: Everything should be made as simple as possible, but not simpler. Having read the book my conclusion is that the authors very well succeeded in doing so. Their definitions of the basic notions in Information Theory are accompanied by a lot of examples that make intuitively clear why these notions have to be defined in that way. The proofs of the basic theorems are very transparent and (of course this goes hand in hand) elegant. Furthermore the authors give a lot of connections and applications of results of Information Theory to other sciences (e.g. Probability Theory, Physics, Economy and Computer Science). I think the book could perfectly be used to give a course in Information Theory to students from different branches. Almost no mathematical background is required, however it helps when some knowledge on probability theory is present. The book contains a lot of nice exercises that encourage the student in mastering the basic techniques and applying results. Every chapter closes with a summary in which the main results of the chapter are restated. This is followed by the exercises and a kind of historical perspective stating who contributed to the development of the results and where they can be found for the first time. In Chapter 1 an outline for the rest of the book is given. Chapter 2 develops the basic notions of Information Theory: Entropy, Relative and Mutual Information, Conditional Information. This is followed by some useful results such as chain rules and important inequalities stemming from concavity and convexity of certain functions. Then some implications to Thermodynamics and Probability Theory are discussed. The Chapter closes with Fano's inequality. Chapter 3 is about the Asymptotic Equipartition Property, that states that the set of sequences of possible appearances of random variables can be divided into two sets: The typical set of sequences that appear with probability tending to 1 and the non-typical set of sequences that are not likely to show up. The connections between entropy, data compression and typical sequences are explored. Chapter 4 is concerned with the entropy rate of stochastic processes. The notion of Markov Chain is developed. The Chapter closes with some results on hidden Markov Models. Chapter 5 is devoted to data compression. First some examples of source codes are given. Then the Kraft inequality is proved. After that optimal coding is being discussed and some bounds on the optimal codelength are derived. Shannon-Fano-Elias coding is the next subject of this Chapter, followed by a kind of ``reverse coding in which the object is to mimic a given probability distribution using a fair coin. Chapter 6 explores data compression a little further and shows connections to gambling strategies. The Chapter closes with some remarks on the entropy of English text, and shows a number of ``approximations to English (up to fourth order in which every letter depends on the previous three). Kolmogorov Complexity is the main topic in Chapter 7. This is the length of the shortest computer program that produces the sequence. Formally it is enough to take into account a Turing machine since this is a universal computer. It turns out that the Komogorov Complexity of sequences is not computable as a consequence of the halting problem. (It cannot be decided whether a program stops or continues forever, hence looking at all programs and finding which sequences they produce is impossible. Unfortunately this is the only way to find the Kolmogorov Complexity of sequences.) Chapter 8 turns to quite another subject: that of Channel Capacity. First the notion of a Channel is developed and some examples are given. Then the Channel Capacity is introduced and investigated. Moreover the Error Probability is introduced. Next the Channel Coding Theorem is stated, exemplified and proved (of course the proof uses the already developed concept of typical sequences: The typical sequences are covered by codewords and the non-typical sequences produce a decoding error). Fano's inequality is used to prove the Converse to the Coding Theorem. Shortly Coding Theory is touched upon (e.g. Hamming codes are explained). In Section 8.12 the influence of feedback is studied. Chapter 9 takes continuous random variables into consideration and the notion of differential entropy is developed. All kind of properties of discrete random variables have their counterparts for continuous random variables and this is about the essence of this Chapter. The results of Chapter 9 are used in Chapter 10 where the Gaussian Channel is discussed. The Capacity for Gaussian Channels with a power constraint is derived and the Theory is pushed a little further in developing the counterparts of the results from Chapter 8 for the case of continuous random variables. Chapter 11 focusses on Maximum Entropy and Spectral Estimation. The Entropy Rate for a Gaussian process is defined and a Maximum Entropy Theorem due to Burg is discussed for this case. In Chapter 12 the implications of information theoretic results for Statistics are discussed. Subjects within this Chapter include: the Method of Types, the Law of Large Numbers, Large Deviation Theory, Hypothesis Testing (Neyman Pearson lemma), Chernoff Bound and Universal Coding (the purpose of which is to reach the entropy using coding techniques which do not depend on the probability distribution on the Source). The Chapter ends with Lempel-Ziv Coding, the notion of Fisher Information and the Cramer Rao Inequality. In Chapter 13 our attention is drawn to Rate Distortion Theory. Chapter 14 discusses ``Network Information Theory sometimes called multi-user information theory. Subjects covered are: --- Gaussian Multiple User Channels; --- Discrete Multi Access Channels (for some of them the capacity region is determined) (for these two cases the following channels are investigated: the Multiple Access Channel, the Broadcast Channel, the Relay Channel, the inference channel and the two way channel); --- Encoding of correlated sources (Slepian-Wolf theorem); --- Coding with side information. Chapter 15 is devoted to implications of information theoretic results to economics (the stock market). In Chapter 16 the basic and useful inequalities in Information Theory are recalled and collected. The book ends with giving a large bibliography. Normally a book of this proportion contains a lot of misprints and errors, but the authors succeeded in keeping this to a minimum (the only more or less ``serious one is the omission of Reference [235]). Since cryptography is a widely developing field these days it surprised me that no information theoretic applications to cryptography were discussed. Nevertheless I think that without risk I can recommended this book both to the expert and to the novice in Information theory.
- Elements of Information Theory
- Elements of underdetermined information theory
- scientific article; zbMATH DE number 5381394
- Information theory
- scientific article; zbMATH DE number 3937089
- scientific article; zbMATH DE number 3159838
- scientific article; zbMATH DE number 927559
- An Elementary Approach to the Theory of Information
- scientific article; zbMATH DE number 4116450
- scientific article; zbMATH DE number 3135403
- Symmetric measures via moments
- Complete monotonicity of the entropy in the central limit theorem for gamma and inverse Gaussian distributions
- Relative entropy measures applied to healthy and pathological voice characterization
- Motion identification from image sequences: Information theory and pixel selection
- WSE, a new sequence distance measure based on word frequencies
- Codification schemes and finite automata
- Entanglement assisted classical capacity of a class of quantum channels with long-term memory
- Object matching in disjoint cameras using a color transfer approach
- Sketching information divergences
- Semi-supervised graph clustering: a kernel approach
- Entropy of hidden Markov processes via cycle expansion
- Dimension of homogeneous rational self-similar measures with overlaps
- Signal-to-noise ratio performance limitations for input disturbance rejection in output feedback control
- Feature selection with dynamic mutual information
- Statistical mechanics of complex systems for pattern identification
- Generalization of Hilbert transform for symbolic analysis of noisy signals
- A general definition of conditional information and its application to ergodic decomposition
- Improved mixing time bounds for the Thorp shuffle and \(L\)-reversal chain
- The \(S\)-digraph optimization problem and the greedy algorithm
- Exploring the state sequence space for hidden Markov and semi-Markov chains
- Measuring the efficiency of the intraday Forex market with a universal data compression algorithm
- The Chernoff lower bound for symmetric quantum hypothesis testing
- Cryptanalysis of an E0-like combiner with memory
- Growth of strategy sets, entropy, and nonstationary bounded recall
- Classical capacity of quantum channels with general Markovian correlated noise
- Quantifying information leakage in process calculi
- Model, properties and imputation method of missing SNP genotype data utilizing mutual information
- Tracking and identification of regime-switching systems using binary sensors
- High resolution quantization and entropy coding of jump processes
- A refinement of the common cause principle
- Hypergraph decomposition and secret sharing
- New bounds on classical and quantum one-way communication complexity
- Global optimization of expensive-to-evaluate functions: An empirical comparison of two sampling criteria
- Characterizations based on Rényi entropy of order statistics and record values
- A low complexity robust detector in impulsive noise
- An overview of distinguishing attacks on stream ciphers
- Counting distinctions: on the conceptual foundations of Shannon's information theory
- Commitment and authentication systems
- Restructuring binary search trees revisited
- On the average depth of asymmetric LC-tries
- Compressing probability distributions
- Blind detection in symmetric non-Gaussian noise with unknown PDF using maximum entropy method with moment generating function constraints
- When cognitive diagnosis meets computerized adaptive testing: CD-CAT
- Some results on ordering of survival functions through uncertainty
- Numerical taxonomy and the principle of maximum entropy
- Averaging over decision trees
- Models, prior information, and Bayesian analysis
- Some aspects of the information theoretic dialogue
- Perfectly secure key distribution for dynamic conferences
- Optimal representation in average using Kolmogorov complexity
- Generalized Beimel-Chor schemes for broadcast encryption and interactive key distribution
- A strong approximation theorem for stochastic recursive algorithms
- Action-timing problem with sequential Bayesian belief revision process
- The space complexity of approximating the frequency moments
- On the stability of open networks: A unified approach by stochastic dominance
- Fluctuation spectroscopy
- On sparse approximations to randomized strategies and convex combinations
- Minimum entropy of error principle in estimation
- Computational depth and reducibility
- Testing for nonlinearity using redundancies: Quantitative and qualitative aspects
- The theory of search from a statistical viewpoint. (With discussion)
- The unicity distance: An upper bound on the probability of an eavesdropper successfully estimating the secret key
- State estimation with communication constraints
- Information and the clone mapping of chromosomes
- An information-theoretic approach to the design of a distributed cascade of sensors
- Information criteria for residual generation and fault detection and isolation
- Linking information reconciliation and privacy amplification
- Models of multi-user write-efficient memories and general diametric theorems
- Optimum measurements for discrimination among symmetric quantum states and parameter estimation
- On-line maximum likelihood prediction with respect to general loss functions
- Classification of binary vectors by stochastic complexity.
- Testing whether lifetime distribution is decreasing uncertainty
- Identification of deterministic chaos by an information-theoretic measure of the sensitive dependence on the initial conditions
- The finite sample properties of simultaneous equations' estimates and estimators. Bayesian and non-Bayesian approaches
- Performance study of marginal posterior density estimation via Kullback-Leibler divergence
- Mutual information, metric entropy and cumulative relative entropy risk
- State change, quantum probability, and information in operational phase-space measurement
- Tsallis entropy production for diffusion on the diluted hypercube
- Portfolio choice with endogenous utility: a large deviations approach.
- On finite strategy sets for finitely repeated zero-sum games.
- Sharing one secret vs. sharing many secrets.
- On the concept of best achievable compression ratio for lossy image coding.
- The generalized universal law of generalization.
- An approach to simple bargaining games and related problems
- Non-logarithmic Jensen-Shannon divergence
- A note on proximity of distributions in terms of coinciding moments.
- Multiscale entropy analysis of human gait dynamics
- Formulas for Rényi information and related measures for univariate distributions.
- Information flow on trees
- Estimation of the weights of interacting criteria from the set of profiles by means of information-theoretic functionals.
- A note on Kolmogorov complexity and entropy
- Some upper bounds for relative entropy and applications
- Sol Golomb's 60th birthday symposium. Papers from the symposium, Oxnard, CA, USA, May 29--31, 1992
- Maximal codeword lengths in Huffman codes
- The characterization of a measure of information discrepancy
- Min-wise independent permutations
- Information-theoretic determination of minimax rates of convergence
- Relative complexity changes in time series using information measures
- General properties and estimation of conditional Bernoulli models
- Applying MDL to learn best model granularity
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023085)