# Questions tagged [information-theory]

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

214 questions
Filter by
Sorted by
Tagged with
1k views

45 views

### Calculating Frequency of Terms with Zipf's Law

I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure. Suppose we have a corpus in which Zipf’s Law holds. If the most ...
103 views

125 views

### Do most bitstrings expand if they halt when executed by a Universal Turing machine?

According to the counting argument, most bitstrings are incompressible or only slightly compressible. However, the counting argument does not work in the opposite direction, since there are an ...
639 views

### Understanding of self-information

I am trying to fully understand the meaning behind the self-information of events. While I totally understood how to calculate it, all explanations I find online lack of an explanation why less likely ...
65 views

### [Choosing tunable parameter M in Golomb/Rice Encoding]

I am a Computer Science student and I study Data Compression now. I read many methods but Golomb-Rice Encoding was not clear for me. I understand the method how it works but in the algorithm there is ...
50 views

### Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$|\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
43 views

### What is The correct terminology for expressing *this* notion of complexity

Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set ...
490 views

### How does youtube do video quality change/video compression?

After uploading a high definition video in youtube, youtube automatically makes a low definition(standard definition) version of the video. I would like to know what algorithm they use to reduce the ...
104 views

### Second-order Markov text generation?

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which ...
87 views

### Calculating the information density of an encoding system

How do I calculate the information density of an encoding system? This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
394 views

### How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya . How can I estimate Bhattacharyya parameter for BSC ...
844 views

### Conceptual overview: Self-information, Mutual information, uncertainty, entropy

I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x_i, y_i$ as events of experiments $X, Y$. Self-information, ...
102 views

### What should be the way to design code for such a situation?

I have a graph as given below: Let us assume one node as transmitter and another as receiver. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
125 views

### Choosing a shortest representative number from interval in arithmetic coding

In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution ...
425 views

### Impossibility for Byzantine Generals Problem where $n \leq 3m$

Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the ...
150 views

63 views

### Can the set of all $2^{24}$ colors be expressed as a ternary linear code?

Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a ...
167 views

### Algorithms that achieve better compression for more data

I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression". Could super compression be ...
72 views

### If you want to archive (and compress) a number of files into one archive is it more efficient to archive first and then compress?

When compressing multiple files, is it more efficient to (1) first compress each individual file separately and then concatenate/merge the results, or (2) first concatenate/merge the files into a ...
31 views

### Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$

Prove that $H_r(S) = H(s) / \log_2r$. I'm not sure how to prove this. Any help would be greatly appreciated!
There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me. First question is why he assumes that we can "Consider an optimal code $C_m$. ...