Information theory

information_theory.json

https://arbital.com/p/information_theory

by Nate Soares May 20 2016

Index
Information theory

Mathematics
…

The study (and quantificaiton) of information, and its communication and storage.

Tagged

Needs clickbait, Stub

All Creators

Nate Soares, jorgejuan lafuente

Likes

Reverse Related

Needs clickbait This page does not have clickbait (a short teaser for the page displayed on various lists). Feel free to add it! - Eric Bruylant
Stub This page only gives a very brief overview of the topic. If you're able to, please help expand or improve it! - Eliezer Yudkowsky

Children

Algorithmic complexity When you compress the information, what you are left with determines the complexity. - Eliezer Yudkowsky
- Most complex things are not very compressible We can't *prove* it's impossible, but it would be *extremely surprising* to discover a 500-state Turing machine that output the exact text of "Romeo and Juliet". - Eliezer Yudkowsky
Bit (of data) A bit of data is the amount of data required to single out one message from a set of two. Equivalen… - Nate Soares
- Bit (of data): Examples In the game "20 questions", one player (the "leader") thinks of a concept, and the other players ask… - Nate Soares
- Fractional bits It takes $\log_2(8) = 3$ bits of data to carry one message from a set of 8 possible messages. Simila… - Nate Soares
  - Fractional bits: Expected cost interpretation In the GalCom thought experiment, you regularly have to send large volumes of information through de… - Nate Soares
- How many bits to a trit? $\log_2(3) \approx 1.585.$ This can be interpreted a few different ways: 1. If you multiply the nu… - Nate Soares
  - Encoding trits with GalCom bits There are $\log_2(3) \approx 1.585$ bits to a Trit. Why is it that particular value? Consider the Ga… - Nate Soares
Communication: magician example Imagine that you and I are both magicians, performing a trick where I think of a card from a deck of… - Nate Soares
Compressing multiple messages How many bits of data does it take to encode an $n$-message? Naively, the answer is $\lceil \log_2(n… - Nate Soares
Data capacity The data capacity of an object is defined to be the Logarithm of the number of different distinguish… - Nate Soares
Decit Decimal digit - Nate Soares
Dependent messages can be encoded cheaply Say you want to transmit a 2-message, a 4-message, and a 256-message to somebody. For example, you m… - Nate Soares
Fractional bits It takes $\log_2(8) = 3$ bits of data to carry one message from a set of 8 possible messages. Simila… - Nate Soares
- Fractional bits: Expected cost interpretation In the GalCom thought experiment, you regularly have to send large volumes of information through de… - Nate Soares
GalCom In the GalCom thought experiment, you live in the future, and make your money by living in the Dene… - Nate Soares
- Encoding trits with GalCom bits There are $\log_2(3) \approx 1.585$ bits to a Trit. Why is it that particular value? Consider the Ga… - Nate Soares
- GalCom: Rules 1. It costs 1 galcoin per bit to reserve on-peak bits in advance. (Galcoins are very expensive.) 2. … - Nate Soares
How many bits to a trit? $\log_2(3) \approx 1.585.$ This can be interpreted a few different ways: 1. If you multiply the nu… - Nate Soares
- Encoding trits with GalCom bits There are $\log_2(3) \approx 1.585$ bits to a Trit. Why is it that particular value? Consider the Ga… - Nate Soares
Information Information is a measure of how much a message grants an observer the ability to predict the world.… - Nate Soares
- Shannon The shannon (Sh) is a unit of Information. One shannon is the difference in [info\_entropy entropy] … - Nate Soares
Intradependent encoding An encoding $E(m)$ of a message $m$ is intradependent if the fact that $E(m)$ encodes $m$ can be de… - Nate Soares
Intradependent encodings can be compressed Given an encoding scheme $E$ which gives an Intradependent encoding of a message $m,$ we can in prin… - Nate Soares
Trit Trinary digit - Nate Soares
n-message A message singling out one thing from a set of $n$ is sometimes called an $n$-message. For example,… - Nate Soares