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
23 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
34 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
19 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 ...
0
votes
0answers
28 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: ...
2
votes
1answer
46 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
50 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
94 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
48 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
68 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
51 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
61 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
29 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
119 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
109 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
80 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 ...
0
votes
0answers
22 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
109 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 ...
0
votes
0answers
26 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
38 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
40 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 ...
4
votes
0answers
96 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
83 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
69 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) = ...
1
vote
2answers
37 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
244 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
118 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 ...
0
votes
1answer
45 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
34 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
34 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
95 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
83 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
28 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 ...
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 ...
3
votes
1answer
68 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 ...
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
46 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 ...
0
votes
2answers
61 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
118 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 ...