# Tagged Questions

The science of compressing and communicating information. It is a branch of applied mathematics and electrical engineering. Though originally the focus was on digital communications and computing, it now finds wide use in biology, physics and other sciences.

15 views

### How can the maximum complexity of a binary series be proven

In an article in the scientific American (https://www.cs.auckland.ac.nz/~chaitin/sciamer.html), Chaitin mentions a way to determine the maximum complexity of the minimal program of a sequence of ones ...
33 views

### Mutual information between 2 sequences of random variables?

How would I go about expanding $I(X_1,...,X_n;Y_1,...,Y_n)$? The chain rule exists for a single case, i.e.: $I(X_1,...,X_n;Y)=\sum^n_{i=1} I(X_i;Y|X_{i-1},...,X_1)$, but I'm having doubts if this can ...
257 views

### Relation between Shannon Entropy and Total Variation distance

Let $p_1(\cdot), p_2(\cdot)$ be two discrete distributions on $\mathbb{Z}.$ Total variation distance is defined as $d_{TV}(p_1,p_2)= \frac{1}{2} \displaystyle \sum_{k \in \mathbb{Z}}|p_1(k)-p_2(k)|$ ...
53 views

### Proof of Central Limit Theorem via MaxEnt principle

Let $X_i$'s be i.i.d. with mean $0$ and variance $\sigma^2$. After reading Jaynes' book: Probability the Logic of Science, I decided to try out and actually prove CLT via the following steps: a) ...
107 views

### Is it possible to code with less bits than calculated by Shannon's source coding theorem?

In information theory, Shannon's source coding theorem establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. Consider that we have data generated by ...
20 views

### Algorithm to determine a set of source symbols in Communication System

There are many algorithms (like Huffman, Arithmetic) which exploit the redundancy in the source message stream and compress the source symbols before sending it over (noisy/noiseless) channel to the ...
9 views

37 views

### mutual information entropy problem

In mutual information we have: if $x$ and $y$ are independent then $p(x,y)=p(x)p(y)$ and then $I(X;Y)=0$. Do If $I (X;Y) = 0$ when $x$ and $y$ are not necessarily independent?
23 views

50 views

### Error correction code in $F_8$ correcting $n$ errors

Suppose we're working with $F_8=\{0,1,2,3,4,5,6,7\}$ and each of message has length of $n$. Is it possible to construct an error correction code such that it corrects $n$ errors, and each error is off ...
52 views

### Mutual Information

Given $X_1$ and $X_2$ are independent, we have \begin{align} I(X_1,X_2;Y_1,Y_2) & = I(X_1;Y_1,Y_2) + I(X_2;Y_1,Y_2\mid X_1) \\[1ex] & = I(X_1;Y_1) + I(X_1;Y_2\mid Y_1) + I(X_2;Y_2\mid X_1) + ...
98 views

### Minimum and Maximum Capacity of a channel

There is this question in the Cover and Thomas book "Elements of Information Theory". Noise alphabets: Consider the channel Y = X + Z where X = {0, 1, 2, 3} and Z is uniformly distributed over ...
50 views

### Conditional joint entropy of two random variables

I am trying to prove the formula that gives the joint entropy of the random variables $X$ and $Y$ given $Z$ which is: $$H(X,Y|Z) = H(X|Z) + H(Y|X,Z)$$ based on the definition of conditional entropy ...
65 views

### Best way to compress a noisy observation

Say we have a discrete signal $X\in \mathcal{X}$, and a noisy observation $Y\in\mathcal{Y}$. We wish to encode $Y$ into some encoding $U$ with rate $R$. That is, $H(U)=R>0$. And we want $U$ to have ...
78 views

### Entropy of union of multisets

Assigning a random variable to some multiset: Assume that $S$ is a multiset. We can think of $S$ as independent sampling from some random variable. For instance, $S = \{H, H, T, T, T\}$ can be thought ...
53 views

### Relative entropy for joint distribution of length n

In the converse proof in information theory, using Fano's inequality, at the end we would have a term like $I(X^n;Y^n)\leq nI(X;Y)$ I was wondering can we prove something like this for relative ...
69 views

26 views

### Log base change problem, Multivariate Gaussian differential entropy proof

I am working through a proof in this document http://ee.tamu.edu/~georghiades/courses/ftp647/Chapter7.pdf for Theorem 3 (The entropy of a multivariate Gaussian distribution): Let X = (X1, X2, · · ·...
115 views

41 views

### What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
311 views

### Calculating Shannon Entropy for DNA sequence?

I'm following the formula on http://www.shannonentropy.netmark.pl/calculate to calculate the Shannon Entropy of a string of nucleotides [nt]. Since their are 4 nt, ...
120 views

### Is there a term in graph theory called 'GRAIL'?

I've been a talk with a PhD student about some graph issue and told me about GRAIL graph and have drawn it for me as you see in the picture, however, I try to generalize so-called "Grail graph" to k-...
57 views

### Is mutual information convex in the joint distribution?

Assume some joint distribution $P(X,Y) = P(Y|X)P(X)$. It is well know that, for fixed $P(Y|X)$, mutual information is a concave function of $P(X)$ and, for fixed $P(X)$, a convex function of $P(Y|X)$ ...
37 views

### Probability Distribution on the Simplex with support on the faces

I am looking for a parametrized distribution on the (probability) $K$-simplex with support on its $(K-1)$-faces. I.e. say $(x_1,...x_{K+1})$ are the coordinates of the simplex with $\sum_jx_j=1$, then ...
If we write $p(\cdot)$ for a discrete probability function and $\mu(\cdot)$ for a continuous density function, then why does the following hold: $$-\sum_x p(x) \log p(x) + \sum_x \int \mu(x,y) \log \... 2answers 103 views ### Differential Entropy I'm a little temporarily confused about the concept of differential entropy. It says on wikipedia that the differential entropy of a Gaussian is \log(\sigma\sqrt{2\pi e}). However I was thinking as ... 1answer 45 views ### Distance between two p.m.fs I am stuck with the following problem from research. Is there any existing distance measure which can compare two probability mass functions with different support? For eg. for pmfs p_1 and p_2 ... 3answers 85 views ### Where do extra dimensions in gradient come from? The gradient of a scalar function f\colon \mathbb{R}^n \to \mathbb{R} is a vector-valued function \nabla f\colon \mathbb{R}^n \to \mathbb{R}^n. Since applying a function can't increase ... 1answer 32 views ### Stationarity and Ergodicity vs. Memorylessness A (discrete) memoryless information source is (usually) defined as a collection of random variables that are independent and identically distributed. My question is, does memorylessness imply ... 0answers 25 views ### The “first order” rate distortion function Suppoer we have a random source (X_n; n \geq 1) taking values in some source alphabet A to be compressed int another alphabet \hat{A}, with respect to a distortion function \rho: A \times \hat{... 1answer 44 views ### Probability measure, probability density function or probability event ? Are they different? My question is regarding the difference between probability measure and probability of event. Recently I have read an information theory paper that considered a channel modeled by probability density ... 0answers 16 views ### Why H_{V^* \cup W^*} > H_{V \cup W} if H_V denotes entropy of language Let W \subseteq X^* be an infinite language over a finite alphabet X, and define (|w| denotes the length of w \in W)$$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
How to calculate entropy as a number of binary choices for a set of three equally probable elements? The Shannon's formula gives $\log_2(3)=1.585$. But any interpretation of binary choices gives me \$5/...