A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [information-theory]

Questions about Information theory, entropy, and information content of various sources

232 questions
Filter by
Sorted by
Tagged with
15 views

### Information bottleneck function

On the Wikipedia page, the information bottleneck function is defined in the following way. For some random variable $X$ containing information about the relevant variable $Y$, we have some joint ...
28 views

### Upper bound for set disjointness under product distributions

For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some ...
30 views

### combination network

Can any one help me find a reference about how to describe the connectivity between the nodes (H relays) and users in combination network ? I mean how exactly I can draw the connection for any number ...
29 views

### Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
47 views

41 views

### Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
38 views

### How to calculate conditional entropy

I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by: How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go ...
74 views

### Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
36 views

### Proof on lower bound of search in unsorted array with information theory?

I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound ...
27 views

### Can we think of information theory in terms of “a measure on set of information”?

In information theory, we deal with the quantities $I(X;Y), H(X),H(Y), H(X|Y), H(Y|X)$. These are just numbers, but I intuitively think of them as the "measure" of a set of information. There is at ...
42 views

### How connected are information theory and algorithmic information theory?

In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth). As far as I understand, algorithmic information ...
40 views

54 views

### information theory, find entropy given Markov chain

There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...
74 views

### Is the capacity achieving input of a discrete memoryless channel unique?

Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. ...
16 views

### Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?

Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound? https://en.wikipedia.org/wiki/Bekenstein_bound
41 views

### Examples of exact computation of Kolmogorov complexity?

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...