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.

learn more… | top users | synonyms (1)

0
votes
0answers
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 ...
1
vote
0answers
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 ...
7
votes
0answers
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)|$ ...
2
votes
1answer
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) ...
2
votes
2answers
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 ...
1
vote
0answers
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 ...
0
votes
0answers
9 views

To invert a matrix for a specific problem

I am reading the book Computational Statistics, and got a problem from formula (4.43), which is derived from (4.30), (4.41), (4.42) (4.30) is $I_X(\theta)=I_{X,Z}(\theta)-I_{Z\mid X}(\theta)$, where $...
0
votes
1answer
45 views

Conditional joint information of two random variables $X,Y$ given $Z$

For 3 random variables I am trying to prove the following: \begin{eqnarray*} I(X;Y|Z)&\triangleq& H(X|Z)-H(X|Y,Z)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) \\&=&E_{p(x,y,z)}\bigg[log_2\frac{...
0
votes
0answers
26 views

Binary Symmetric Channel with Feedback

Suppose that feedback is used on a binary symmetric channel with parameter p. Each time a Y is received, it becomes the next transmission. Thus $X_1$ is Bern(1/2), $X_2$ = $Y_1$; $X_3$ = $Y_2$,..., $...
0
votes
0answers
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?
0
votes
0answers
23 views

Entropy of Quantized random variables

Let $X,Y$ be two i.i.d real-valued random variables with density function $f_{}(.).$ Let $\langle X\rangle_n, \langle Y \rangle_n$ be quantized versions of $X,Y$ respectively, i.e $\langle X \rangle_n=...
0
votes
0answers
29 views

Interaction information within markov chains

There is a signal $X$ for which we have $2$ noisy observations, $(Y_1,Y_2)$. These observations are individually further degraded into variables $(W_1,W_2),$ giving a Markov structure: $X\...
2
votes
1answer
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 ...
0
votes
1answer
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) + ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
1answer
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 ...
0
votes
1answer
69 views

Mutual information between Gaussian source and transmitted output: entropies do not add up

I have a Gaussian source $X \sim N(\mu, \Sigma)$, and under squared error fidelity choice $E[(X-Y)'(X-Y)]$, my optimal output $Y$ differs from $X$ by independent error $Z$, where $Z \sim N(\eta, \...
1
vote
1answer
38 views

Markov processes in paper “Recent Contributions to The Mathematical Theory of Communication”

I was reading the well-known paper by Warren Weaver, "Recent Contributions to The Mathematical Theory of Communication", I stumpled upon the following sentence(p. 5)" A system which produces a ...
0
votes
1answer
46 views

Proof of Jointy Typical Sequences using Chebyshev's Inequality

My lecturer went through the topic of "Jointly Typical Sequences" in my Information Theory course, and one of the properties/lemma was that $P((X^n, Y^n) \in A^{(n)}_e) \to 1$ as $n \to \infty$, where ...
1
vote
1answer
31 views

Prove for entropy of a binomial distribution

I am trying to prove the following identity for a Binomial $(n,p)$ random variable $X$, $$ H(X)= n h_2(p) + \mathbb{E}{n \choose X} $$ I've started with the definition of entropy but I am unable to ...
13
votes
2answers
121 views

can't swing the proof for this inequality

Let $p+p'=1$ and $q+q'=1$. If $\log(p/q)>\log(q'/p')$ then $(p+q)\log(p/q)>(p'+q')\log(q'/p')$. This looks deceptively simple to prove, but it's not. I couldn't crack it using Jensen's ...
6
votes
2answers
121 views

Sum of uniform random variables on simplex

Let $X,X'$ be two independent uniform random variables on $n$-dimensional simplex $\Delta_n= \{(x_1,\ldots,x_n):x_i \geq 0, \sum x_i \leq 1\}$. I am trying to find the probability distribution of ...
4
votes
2answers
83 views

Convert string to another string over a smaller alphabet, and vice versa.

I'm trying to find the most suitable algorithm to convert a string $\alpha$ over the alphabet $\Sigma$ of size $| \Sigma | = n$ to string $\beta$ over the alphabet $\Omega$ of size $| \Omega | = n-1$, ...
0
votes
0answers
24 views

Optimal length close to Entropy plus 1

For a fixed $\epsilon> 0$, one need to find a probability distribution $\bf{p}=(p_1,p_2,\ldots,p_n)$ and an optimal code (prefix-free) for this distribution such that the average length $L=\sum_{i=...
0
votes
1answer
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, · · ·...
5
votes
2answers
115 views

An elementary proof for a bound on $x \log x$

During one of our information theory classes, the Professor used the following bound to prove a result. For any $x,y \in (0,1)$, $x \neq y$, show that $$|x \log(x) - y \log(y) | \leq |x-y|\log \left(...
0
votes
0answers
27 views

Mutual Information in a commuication-chain

Consider three communication-partners $A$,$B$ and $C$ that are commuicating in a chain, like $A\rightarrow B\rightarrow C$. So, $A$ talks to $B$ and $B$ talks to $C$. The channels are noisy. Now, ...
0
votes
1answer
27 views

Mutual information: Indirect

Maybe this is a very trivial question but my own answer to it is rather based on intuition only. Consider two random variables A and B. Their mutual information is I_AB. Now, I want to obtain ...
0
votes
0answers
39 views

a problem involving binary entropy function

let $\alpha<1/2$ such that $2^{H(\alpha)}\le 2^{1-\epsilon}$,when $H$ is binary entropy function. how can i prove that then we have: $2^{n(1-\epsilon)}\ge \sum\limits_{i\le \alpha n } {n \choose ...
0
votes
0answers
41 views

Calculating the Shannon information of drawing equal no. of cards

One card is drawn each from a $k$ deck of 52 cards where $k$ is a multiple of $52$. I need to prove that information of an outcome where each card appears the same number of times tends to $\frac{51}...
4
votes
0answers
99 views

Divergence based robust inference

The term 'divergence' means a function $D$ which takes two probability distributions $g,f$ as input and puts out a non-negative real number $D(g,f)$. I have learnt that the inference based on ...
0
votes
1answer
88 views

Explain Kraft McMillan inequality and how it is applied.

I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me. We would like to encode a sequence of ...
5
votes
0answers
70 views

Solving a Matrix DE involving the KL divergence

If we let $U_\mu$ be a vector field that associates a direction vector $U_\mu(\pi)$ with each $\pi \in $ unit simplex. Each such vector field is associated with a system of ODEs: $$ \pi'(u) = U_\mu(\...
1
vote
2answers
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 ...
1
vote
1answer
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, ...
0
votes
1answer
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-...
0
votes
1answer
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)$ ...
0
votes
0answers
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 ...
2
votes
1answer
35 views

Why does $-\sum_x p(x) \log p(x) + \sum_x \int \mu(x,y) \log \mu(x,y) dy = \sum_x \int \mu(x,y) \log \mu(y \mid x) dy$?

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 \...
2
votes
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 $...
0
votes
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$ ...
0
votes
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 ...
1
vote
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 ...
1
vote
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{...
2
votes
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 ...
0
votes
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| = ...
2
votes
1answer
34 views

Shannon information for a set of 3 equally probable elements?

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/...