Entropy in data compression, additive combinatorics and probability
Authors: Γαβαλάκης Λάμπρος 
Published: July 2024

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