Questions tagged [it.information-theory]

Questions in Information Theory

Filter by
Sorted by
Tagged with
35
votes
3answers
2k views

What is the Volume of Information?

This question was asked to Jeannette Wing after her PCAST presentation on computer science. “From a physics perspective, is there a maximum volume of information we can have?” (a nice challenge ...
55
votes
13answers
4k views

Information Theory used to prove neat combinatorial statements?

What's your favorite examples where information theory is used to prove a neat combinatorial statement in a simple way ? Some examples I can think of are related to lower bounds for locally decodable ...
44
votes
10answers
4k views

Kolmogorov complexity applications in computational complexity

Informally speaking, Kolmogorov complexity of a string $x$ is a length of a shortest program that outputs $x$. We can define a notion of 'random string' using it ($x$ is random if $K(x) \geq 0.99 |x|$)...
31
votes
5answers
2k views

Efficiently computable variants of Kolmogorov complexity

Kolmogorov prefix complexity (i.e. $K(x)$ is the size of minimal self-delimiting program that outputs $x$) has several nice features: It corresponds to an intuition of giving strings with patters or ...
23
votes
5answers
7k views

Is there any connection between the diamond norm and the distance of the associated states?

In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such ...
8
votes
3answers
1k views

Kolmogorov Complexity applications in Number Theory

What are the applications of Kolmogorov Complexity in Number Theory and on proofs related fields? (The monograph by Li & Vitanyi doesn't have many applications related to Number Theory.) One of ...
4
votes
2answers
2k views

An upper bound for chi-square divergence in terms of KL divergence for general alphabets

In my research I need an upper bound for chi-square divergence in terms KL divergence which works for general alphabets. To make this precise, note that for two probability measures $P$ and $Q$ ...
9
votes
2answers
311 views

Guessing a low entropy value in multiple attempts

Suppose Alice has a distribution $\mu$ over a finite (but possibly very large) domain, such that the (Shannon) entropy of $\mu$ is upper bounded by an arbitrarily small constant $\varepsilon$. Alice ...
6
votes
1answer
259 views

Algorithmic mutual information between random string and minimal Kolmogorov sufficient statistic

Regarding notation in the following, the function $\ell(B)$ returns the length of bitstring $B$, and the cardinality of set $S$ is denoted by $|S|$. A bitstring $B$ is generated by drawing 0s and 1s ...
5
votes
2answers
2k views

Transposition of any characters in Damerau–Levenshtein edit distance computation

Is it possible to modify the computation of Damerau–Levenshtein distance to take into account not only the transposition of adjacent characters, but the transposition of any characters? Maybe some ...
4
votes
2answers
3k views

Why does the Fibonacci sequence produce a worst-case Huffman encoding?

I noticed this in my Algorithms class, but just now got around to asking.
1
vote
1answer
362 views

Does Huffman coding always produce shorter codes than the Shannon code?

Let $X\in\{1,2,\ldots,m\}$ be a discrete random variable with $X\sim p$. Let $C$ be a code for $X$ with $l_i$ being the length $i$-th codeword and let $L(C)$ be the expected length of the code. The ...
1
vote
0answers
96 views

On the equivalence of incompressibility and incompleteness in machine learning

Motivation: Motivated by the question of what problems are suitably addressed using methods in machine learning, I decided to formulate this general problem using Algorithmic Information Theory. My ...