Motivation Information Entropy CompressingInformation An Introduction to Information Theory CarltonDowney November12,2013 Motivation Information Entropy CompressingInformation INTRODUCTION (cid:73) Today’srecitationwillbeanintroductiontoInformation Theory (cid:73) Informationtheorystudiesthequantificationof Information (cid:73) Compression (cid:73) Transmission (cid:73) ErrorCorrection (cid:73) Gambling (cid:73) FoundedbyClaudeShannonin1948byhisclassicpaper “AMathematicalTheoryofCommunication” (cid:73) ItisanareaofmathematicswhichIthinkisparticularly elegant Motivation Information Entropy CompressingInformation OUTLINE Motivation Information Entropy MarginalEntropy JointEntropy ConditionalEntropy MutualInformation CompressingInformation PrefixCodes KLDivergence Motivation Information Entropy CompressingInformation OUTLINE Motivation Information Entropy MarginalEntropy JointEntropy ConditionalEntropy MutualInformation CompressingInformation PrefixCodes KLDivergence (cid:73) Roulette. Butwhy? theseareallfairgames (cid:73) Answer: RouletteprovidesuswiththemostInformation Motivation Information Entropy CompressingInformation MOTIVATION: CASINO (cid:73) You’reatacasino (cid:73) Youcanbetoncoins,dice,orroulette (cid:73) Coins=2possibleoutcomes. Pays2:1 (cid:73) Dice=6possibleoutcomes. Pays6:1 (cid:73) roulette=36possibleoutcomes. Pays36:1 (cid:73) Supposeyoucanpredicttheoutcomeofasinglecoin toss/diceroll/roulettespin. (cid:73) Whichwouldyouchoose? (cid:73) Answer: RouletteprovidesuswiththemostInformation Motivation Information Entropy CompressingInformation MOTIVATION: CASINO (cid:73) You’reatacasino (cid:73) Youcanbetoncoins,dice,orroulette (cid:73) Coins=2possibleoutcomes. Pays2:1 (cid:73) Dice=6possibleoutcomes. Pays6:1 (cid:73) roulette=36possibleoutcomes. Pays36:1 (cid:73) Supposeyoucanpredicttheoutcomeofasinglecoin toss/diceroll/roulettespin. (cid:73) Whichwouldyouchoose? (cid:73) Roulette. Butwhy? theseareallfairgames Motivation Information Entropy CompressingInformation MOTIVATION: CASINO (cid:73) You’reatacasino (cid:73) Youcanbetoncoins,dice,orroulette (cid:73) Coins=2possibleoutcomes. Pays2:1 (cid:73) Dice=6possibleoutcomes. Pays6:1 (cid:73) roulette=36possibleoutcomes. Pays36:1 (cid:73) Supposeyoucanpredicttheoutcomeofasinglecoin toss/diceroll/roulettespin. (cid:73) Whichwouldyouchoose? (cid:73) Roulette. Butwhy? theseareallfairgames (cid:73) Answer: RouletteprovidesuswiththemostInformation Motivation Information Entropy CompressingInformation MOTIVATION: COIN TOSS (cid:73) Considertwocoins: (cid:73) FaircoinC withP(H)=0.5,P(T)=0.5 F (cid:73) BentcoinC withP(H)=0.99,P(T)=0.01 B (cid:73) Supposeweflipbothcoins,andtheybothlandheads (cid:73) Intuitivelywearemore“surprised”or“Informed”byfirst outcome. (cid:73) WeknowC isalmostcertaintolandheads,sothe B knowledgethatitlandsheadsprovidesuswithverylittle information. Motivation Information Entropy CompressingInformation MOTIVATION: COMPRESSION (cid:73) Supposeweobserveasequenceofevents: (cid:73) Cointosses (cid:73) Wordsinalanguage (cid:73) notesinasong (cid:73) etc. (cid:73) Wewanttorecordthesequenceofeventsinthesmallest possiblespace. (cid:73) Inotherwordswewanttheshortestrepresentationwhich preservesallinformation. (cid:73) Anotherwaytothinkaboutthis: Howmuchinformation doesthesequenceofeventsactuallycontain? Motivation Information Entropy CompressingInformation MOTIVATION: COMPRESSION Tobeconcrete,considertheproblemofrecordingcointossesin unary. T,T,T,T,H Approach1: H T 0 00 00,00,00,00,0 Weused9characters