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
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
68 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
45 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
30 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
119 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
23 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
25 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
26 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
97 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
84 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
40 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
293 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
119 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
54 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
102 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
24 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
43 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/...
3
votes
1answer
69 views

Entropy of $f(x)=1$

Let $f(x)$ be a probability density function $f(x) = 1$ on $x = [0,1]$, and entropy defined as $$H(p(x)) = -\int p(x) \log_2(p(x)) \, dx$$ where $p(x)$ is a pdf. Unless I've made an arithmetic error, ...
1
vote
1answer
21 views

Finding unique rules for a finite number of initial steps, using Information theory

Is there a unique way to determine which rule provides the sequence that matches a finite number of initial steps, choosing the rule that needs the least amount of information to be described? ...
0
votes
1answer
29 views

Possible to eliminate mutual information between random variables by reducing the number of them?

Say you have a set of random variables that have some mutual information structure. Could be that they all have nonzero MI between them. Or perhaps there are some clusters of variables with within-...
2
votes
0answers
32 views

Departure from uniformity in a continuous (time) distribution

I know how to quantify the departure from uniformity ( or a uniform distribution) for discrete distributions. Assume you have a distribution set of P: ...
2
votes
1answer
33 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
0
votes
0answers
48 views

Mutual Information: Are these two equations equal?

I'm working with Multivariate Mutual Information (MMI), specifically with three variables $(X,Y,Z)$, applied to RNA sequences. The MMI equation that I use for three variables is based on entropy ...
1
vote
3answers
91 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, $...
0
votes
1answer
150 views

How to calculate entropy from a set of samples?

entropy (information content) is defined as: $$ H(X) = \sum_{i} {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i} {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ This allows to calculate the entropy of a ...
1
vote
0answers
51 views

Derivative of the Kullback Leibler Divergence

If: $$ H (\pi(t)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log \frac{\pi_i(t)}{\mu_i(t+1)} $$ How do I interpret: $\nabla H(\pi(t) | \mu(t+1) )$? Would it be the vector: $$ \left ( \frac{\partial H}{\...
0
votes
1answer
260 views

Noiseless Channel Capacity

Nyquist theorem proves that a signal of $B$ bandwidth, in order to be sampled correctly thus avoid aliasing, has to be sampled with a $f_c > = 2B$. When it comes to calculating the capacity of a ...
3
votes
2answers
99 views

Is conditional entropy ever taken to be a random variable?

In probability theory, the conditional expectation $E(X|Y)$ and variance $V(X|Y)$ er usually taken to be random variables, st. the value of $E(X|Y)$ depends on what value $Y$ ends up taking. I've ...
1
vote
1answer
22 views

Finding C from $\Delta C$

Define: $\Delta A(t) = A(t+1)-A(t)$ and let $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log \frac{\...
1
vote
0answers
27 views

Vector Differential in specific form

for the operator: $\Delta A(t) = A(t+1)-A(t)$, let : $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log ...
0
votes
1answer
38 views

Shannon-Hartley theorem for other bases

The Shannon-Hartley theorem is given with terms referring to a binary signal. What if a channel does not transmit via binary, but instead in another system, such as ternary or base-4?
0
votes
2answers
22 views

Information limit for digital signal

Wikipedia give the Shannon-Hartley theorem as: $$ C = B \log_2 \left(1+ \frac{S}{N}\right) $$ Where $S/N$ is the signal to noise ratio, with each quantity measured in watts. What if the channel is ...