Entropy in data compression, additive combinatorics and probability

Abstract

This thesis has four parts:In the first part, the problem of lossless data compression with side information availableto both the encoder and the decoder is considered. The finite-blocklength fundamental limitsof the best achievable performance are defined, in two different versions of the problem:Reference-based compression, when a single side information string is used repeatedly incompressing different source messages, and pair-based compression, where a different sideinformation string is used for each source message. General achievability and conversetheorems are established for arbitrary source-side information pairs. Nonasymptotic normalapproximation expansions are proved for the optimal rate in both the reference-based and pairbased settings, for memoryless sources. These are stated in terms of explicit, finite-blocklengthbounds, that are tight up to third-order terms. Extensions that go significantly beyondthe class of memoryless sources are obtained. The relevant source dispersion is identifiedand its relationship with the conditional varentropy rate is established. Interestingly, thedispersion is different in reference-based and pair-based compression, and it is proved thatthe reference-based dispersion is in general smaller.Secondly, a discrete, asymptotic analogue of the entropy power inequality due to Tao isdiscussed. The nonasymptotic version of the result is obtained. Applications in informationtheory and connections with the entropic central limit theorem are discussed.In the third part, we recall some of the history of the information-theoretic approach toderiving core results in probability theory and give three new such proofs. A strengthenedversion of the central limit theorem for discrete random variables is established, relying onlyon information-theoretic tools and elementary arguments. It is shown that the relative entropybetween the standardised sum of n independent and identically distributed lattice randomvariables and an appropriately discretised Gaussian, vanishes as n tends to infinity. Then we give twonew information-theoretic proofs of finite versions of de Finetti’s classical representationtheorem for finite-valued random variables. We derive an upper bound on the relative entropy6between the distribution of the first k in a sequence of n exchangeable random variables,and an appropriate mixture over product distributions. The first result is stated for binaryrandom variables and the proof is based on estimating the dependence of the random variablesunder an appropriate conditioning. The second result is stated for random variables in ageneral finite alphabet. Its proof is nicely motivated by the Gibbs conditioning principle inconnection with statistical mechanics, and it follows along an appealing sequence of steps.The technical estimates required for these steps are obtained via the the method of types.The mixing measure is characterised in both cases as the law of the empirical measure of theoriginal sequence, and de Finetti’s result is recovered as a corollary.In the final part, we provide a collection of inequalities for the differential entropy of anarbitrary random variable convolved with a Gaussian. In terms of techniques, as well as ofthe results themselves, these inequalities lie in the interface between sumset inequalities forentropy and the central limit theorem.

Αυτή η διατριβή έχει τέσσερα μέρη:Στο πρώτο μέρος, εξετάζεται το πρόβλημα της μη απωλεστικής συμπίεσης δεδομένων με παράπλευρη πληροφορία διαθέσιμη τόσο στον κωδικοποιητή όσο και στον αποκωδικοποιητή. Οι θεμελιώδεις περιορισμοί για πεπερασμένο μήκος μπλοκ της καλύτερης επιτεύξιμης απόδοσης ορίζονται σε δύο διαφορετικές εκδοχές του προβλήματος: Συμπίεση βάσει αναφοράς, όταν μια μοναδική ακολουθία παράπλευρης πληροφορίας χρησιμοποιείται επανειλημμένα για τη συμπίεση διαφορετικών μηνυμάτων πηγής, και συμπίεση βάσει ζεύγους, όπου μια διαφορετική ακολουθία παράπλευρης πληροφορίας χρησιμοποιείται για κάθε μήνυμα πηγής. Γενικά θεωρήματα επιτευξιμότητας και αντίστροφα θεωρήματα αποδεικνύονται για αυθαίρετα ζεύγη πηγής-παράπλευρης πληροφορίας. Μη ασυμπτωτικές αναπτύξεις κανονικής προσέγγισης αποδεικνύονται για τον βέλτιστο ρυθμό τόσο στην εκδοχή βάσει αναφοράς όσο και στην εκδοχή βάσει ζεύγους, για πηγές χωρίς μνήμη. Αυτά παρουσιάζονται ως ακριβή φράγματα, πεπερασμένου μήκους μπλοκ, που είναι βέλτιστα μέχρι τους όρους τρίτης τάξης. Επιτυγχάνονται επεκτάσεις που υπερβαίνουν σημαντικά την κατηγορία των πηγών χωρίς μνήμη. Προσδιορίζεται η κατάλληλη έννοια διασκόρπισης πηγής και βρίσκεται η σχέση της με τον ρυθμό διασπορικής εντροπίας. Ενδιαφέρον παρουσιάζει το γεγονός ότι η διασκόρπιση είναι διαφορετική στη συμπίεση βάσει αναφοράς και στη συμπίεση βάσει ζεύγους, και αποδεικνύεται ότι η διασκόρπιση βάσει αναφοράς είναι γενικά μικρότερη.Δεύτερον, συζητείται ένα διακριτό, ασυμπτωτικό ανάλογο της ανισότητας εντροπικής ισχύος του Tao. Αποδεικνύεται η μη ασυμπτωτική εκδοχή του αποτελέσματος. Συζητούνται εφαρμογές στη θεωρία πληροφορίας και συνδέσεις με το εντροπικό κεντρικό οριακό θεώρημα.Στο τρίτο μέρος, ανακαλούμε μερικά από τα ιστορικά στοιχεία της προσέγγισης μέσω θεωρίας πληροφορίας στην εξαγωγή βασικών αποτελεσμάτων στη θεωρία πιθανοτήτων και δίνουμε τρεις νέες τέτοιες αποδείξεις. Αποδεικνύεται μια ισχυρή μορφή του κεντρικού οριακού θεωρήματος για διακριτές τυχαίες μεταβλητές, βασιζόμενη μόνο σε εργαλεία της θεωρίας πληροφορίας και στοιχειώδη επιχειρήματα. Δείχνεται ότι η σχετική εντροπία μεταξύ του κανονικοποιημένου αθροίσματος $n$ ανεξάρτητων και ισόνομων διακριτών τυχαίων μεταβλητών και μιας κατάλληλα διακριτοποιημένης κανονικής κατανομής, τείνει στο μηδέν καθώς το n τείνει στο άπειρο. Στη συνέχεια, δίνουμε δύο νέες αποδείξεις με βάση τη θεωρία πληροφορίας για πεπερασμένες εκδοχές του κλασικού θεωρήματος αναπαράστασης του de Finetti για τυχαίες μεταβλητές με πεπερασμένες τιμές. Δίνουμε ένα άνω φράγμα για τη σχετική εντροπία μεταξύ της κατανομής των πρώτων k σε μια ακολουθία n εναλλάξιμων τυχαίων μεταβλητών και ενός κατάλληλου μείγματος γινόμενων κατανομών. Το πρώτο αποτέλεσμα διατυπώνεται για δυαδικές τυχαίες μεταβλητές και η απόδειξη βασίζεται στην εκτίμηση της εξάρτησης των τυχαίων μεταβλητών υπό κατάλληλη δέσμευση. Το δεύτερο αποτέλεσμα διατυπώνεται για τυχαίες μεταβλητές σε ένα γενικό πεπερασμένο αλφάβητο. Η απόδειξή του είναι με ωραίο τρόπο παρακινημένη από το δεσμευμένο οριακό θεώρημα του Gibbs από τη στατιστική μηχανική και ακολουθεί μια ελκυστική ακολουθία βημάτων. Οι τεχνικές εκτιμήσεις που απαιτούνται για αυτά τα βήματα επιτυγχάνονται μέσω της χρήσης της μεθόδου των τύπων. Το μέτρο μείγματος χαρακτηρίζεται και στις δύο περιπτώσεις ως ο νόμος του εμπειρικού μέτρου της αρχικής ακολουθίας, και το αποτέλεσμα του de Finetti ανακτάται ως πόρισμα.Στο τελευταίο μέρος, παρουσιάζουμε μια συλλογή ανισοτήτων για τη διαφορική εντροπία μιας αυθαίρετης τυχαίας μεταβλητής υπό συνέλιξη με μια κανονική κατανομή. Από άποψη τεχνικών, καθώς και των ίδιων των αποτελεσμάτων, αυτές οι ανισότητες βρίσκονται στη διεπαφή μεταξύ των ανισοτήτων αθροίσματος συνόλου για την εντροπία και του κεντρικού οριακού θεωρήματος.