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)

1
vote
0answers
11 views

Lower bound for limit of length of codeword

Here is the question I'm trying to solve. I don't really have any idea how to approach it/what theorem to use. For $ p, \lambda >0$, let $m(n,p,\lambda)$ be defined to be the least $m$ ...
1
vote
0answers
10 views

Significance of Convex Sets for I-Projection

I have been reviewing the literature on information theoretic methods in statistics, and in particular, the method of I-projections. Given a discrete, finite alphabet $\mathcal{X}$, let $\prod$ denote ...
0
votes
1answer
13 views

How to prove $2d_H(\{XY\},\{X\}\{Y\})^2 \le I(X,Y)$?

Let $X$ and $Y$ be discrete random variables. Denote the joint distribution of $X$ and $Y$ by $\{XY\}$ and their marginal distributions by $\{X\}$ and $\{Y\}$. Let $\{X\}\{Y\}$ denote the product of ...
0
votes
0answers
13 views

Kullback-Leibler Divergence (KL) and Approximation Symmetry Property

The Kullback-Leibler Divergence doesn't satisfy the symmetric property. But, it can be approximated (bounded) to such a value. in this paper: Compressing Interactive Communication under product ...
0
votes
0answers
9 views

Checking if a code can be unambiguously decoded

The source of information is A = {a, b, c, d}. More info is given in the table below. I have to find the average length of the codes, compare it to the entropy of ...
2
votes
0answers
23 views
+50

What will be the Lyapunov exponent?

If $\lambda$ is the largest positive Lyapunov exponent of a piecewise linear dynamical chaotic discrete in time map, then is there a relationship between the entropy and its $\lambda$. In the paper ...
5
votes
2answers
54 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
1
vote
1answer
11 views

The relationship between AEP and compression

So i've been reading up on AEP, and trying to get a grasp on it (and to figure out why it is important). I understand the general definitions, and that the whole idea is the knowlegde of typical ...
0
votes
0answers
25 views

Lower bound on binomial tail

In something I am reading, the following statement is mentioned in passing as something obvious: if $X_1,\ldots,X_n$ are i.i.d. Bernoulli with parameter $1/2 + \delta$, then $\mathbb{P}(\sum_{i=1}^n ...
1
vote
0answers
27 views

Information in Filtrations

Is the “information” kept track of by filtrations the same as information-theoretic “information”? If not, is there some way the two concepts can be reconciled?
1
vote
3answers
36 views

Approximation of an indefinite integral

Consider this integral $$\frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t$$ When $d$ goes to zero, $$\lim _{d\to 0} \frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t = f(x)$$ but what is the second ...
1
vote
1answer
17 views

Relative entropy between discrete and continuous random variables

Is this possible to define relative entropy between discrete and continuous random variables? Say $P$ is a discrete pmf and $Q$ is a continuous pdf, what is $D(P||Q)$?
0
votes
0answers
8 views

Monte-Carlo estimation of Mutual Information over AWGN channel

I'm trying to solve a problem I was tasked with. Basically I have to generate a 100k 16QAM inputs and transmit them over a AWGN channel. With this I have to use the Monte-Carlo estimation to figure ...
2
votes
1answer
29 views

Maximizing sum of logarithms (Z-channel capacity)

In the context of information theory, I am trying to maximize the following function (mutual information of the Z-channel's input and output) with respect to $p$ in order to derive Z-channel's ...
0
votes
2answers
26 views

Relative entropy (KL divergence) of sum of random variables

Suppose we have two independent random variables, $X$ and $Y$, with different probability distributions. What is the relative entropy between pdf of $X$ and $X+Y$, i.e. $$D(P_X||P_{X+Y})$$ assume all ...
0
votes
1answer
30 views

Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that $$H((f(X,Y), g(X,Y)))\leq H ...
0
votes
0answers
11 views

Entropy of a binary string obtained from dynamical system and length of the source code

H(S), the entropy of a source, gives you the average codeword length to encode a given source alphabet. i.e. it is the average number of bits per symbol required to encode the information in the ...
0
votes
1answer
39 views

Proof regarding size and dimension of linear codes

The problem is stated as follows: Let C be a binary linear code of length n, dimension k and distance d and assume that C contains at least one element of odd weight. Let C' be the subset of C ...
0
votes
2answers
36 views

Repetition code and binary symmetric channel, where error is near 1/2

I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error ...
1
vote
1answer
19 views

For a Fisher Information, $\mathcal{I}(\theta)$, why does $\mathcal{I}(\theta) = n\mathcal{I}_1(\theta)$ not hold for multiple dimensions?

Suppose we have that $X_1, \ldots, X_n$ are iid from a distribution with ONE parameter, $\theta$. Then, under regulatory conditions, the Fisher Information may be written as: $$ \mathcal{I}(\theta) = ...
1
vote
0answers
20 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) ...
13
votes
5answers
398 views

(Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) ...
1
vote
0answers
14 views

Channel capacity of sum of symmetric channels

I've got a channel matrix $P$ of the form $\begin{bmatrix} Q \\ R \end{bmatrix}$ where $Q,R$ are channel matrices of symmetric channels, so they now have different input alphabets but the ...
0
votes
1answer
24 views

Basic Entropy Inequality and Identity question

This is a solution to a problem I am working on: \begin{equation} \begin{aligned} H(X|Y) + H(Y|Z) &\ge^? H(X|Y, Z) + H(Y|Z) \\ &=^\text{?}H(X,Y |Z) \\ &= H(X|Z) + H(Y|X, Z)\\ &\ge ...
4
votes
1answer
70 views

Why do we like sticking random variables into their own distributions?

Let $X$ be a random variable taking values in the set $S$. It has some distribution $f(s)$. Often in statistics, we are interested in the real valued random variable $f(X)$. Here are some examples: ...
1
vote
0answers
12 views

Representation of the optimal filter measure as the measure of a diffusion process

In "Mitter SK, Newton NJ. A Variational Approach to Nonlinear Estimation. SIAM J Control Optim. 2003 Jan;42(5):1813–33", it is shown that the path estimation measure $P_{X|Y}(\cdot,y)$ for the ...
0
votes
1answer
16 views

Calculating Entropy and Information Gain of a Variable

I have the following values for two random variables. I need to compute the following values: a. H(Y) b. H(Y|X) c. and finally IG(Y|X) I will show what I have calculated so far. a. H(Y) = ...
1
vote
0answers
11 views

Removing the dimension factor in Fannes inequality

Given two distributions $x=(x_1,\ldots, x_n),y=(y_1,\ldots y_n)$ on $[n]$, it is known by Fannes inequality that $H(x)-H(y)\leq O(\|x-y\|_1\log n)$, where $H(\cdot)$ and $\|\cdot\|_1$ represent ...
0
votes
0answers
11 views

Closed form of Mutual Information, Continuous Random Variables

Is there any closed form for any non Gaussian Joint distribution ? For the Gaussian case $I(X,Y)=f( \varrho )$ where $\varrho $ is the correlation coefficient, and $f$ is an known increasing ...
1
vote
1answer
27 views

Quantum Asymptotic Equipartition

From Information Theory, we have the Asymptotic Equipartition Property, which can be proved by the Weak Law of Large Number: $\log P(x^n)=\log \prod\limits_{i=1}^{n} P(x_i)=\sum\limits_{i=1}^{n} \log ...
2
votes
1answer
88 views

proof of upper bound on differential entropy of f(X)

I asked a similar question yesterday, but I organized my question here a little and further asked my second question. Suppose $X$ is a continuous random variable with the pdf $f_x$, and $Y=g(X)$. If ...
0
votes
0answers
47 views

differential entropy of f(X)

The differential entropy is translation invariant but not scaling invariant: $h(X+c) = h(x)$ for some constant $c$,and $h(aX) = h(X) + \ln (|a|)$ . I am interested in an extension of the scaling ...
1
vote
0answers
26 views

Finding a distribution whose KL Divergence from a given distribution is a constant $\alpha$

Consider P as a multinomial distribution over k variables. I would like to find a distribution Q, also a multinomial distribution over k variables such that KL Divergence between Q from P is a ...
0
votes
0answers
38 views

How to calculate the Shannon Entropy for a block length of a word

I have a binary sequence of length N as $10110110111...$ I want to segment the above series into equal blocks of a window of length $L$. One way of determining the block length is using the ...
0
votes
0answers
15 views

Lower Bound on the Cardinality of Conditionally Strongly Typical Sets

The following question refers to this document (Advanced Topics in Information Theory by Dr. Stefan Moser, Version 2.6): http://moser-isi.ethz.ch/docs/atit_script_v26.pdf On pages 72 - 75, the lower ...
1
vote
0answers
10 views

What metric to use on SAX approximation

I'm using SAX (Symbolic Aggregate approXimation) on a time series data. There are some SAX's parameters which can be adjusted - word size, vocabulary size, etc. So, I wanted to have a metric in order ...
0
votes
1answer
20 views

Calculating mutual information for a dataset

I have a dataset of individual text documents $D = {d_0, d_1, ..., d_n}$ and a corpus of keywords $K = {k_0, k_1, ..., k_m}$ in the documents. There are zero or more keywords in each text document. I ...
1
vote
1answer
41 views

Conditional Entropy and Gibbs Inequality

We know $$H(X | Y) + H(Y) = H(X, Y)$$ Therefore, $$H(X | Y) \leq H(X, Y) $$ since $$ H(Y) \geq 0$$ If we expand this out, we get $$-\sum_{x,y} {p(x,y) \log p(x | y)} \leq - \sum_{x,y} {p(x,y) \log ...
1
vote
1answer
31 views

Convert a joint entropy matrix to a contidional entropy matrix.

I've only barely started to learn about Entropy and Information Theory as a part of a course I'm taking in Systems Theory / Cybernetics. The thing is, I'm terrible at math! Say I have a joint ...
0
votes
0answers
21 views

How to find inverse of this function (Mutual Information)?

I am looking at a real-value random variable $A$ that is defined as \begin{equation} A = \mu_A.x+n_A \end{equation} where $n_A\sim\mathcal{N}(0,\sigma_A^2)$. Also $\mu_A = \frac{\sigma_A^2}{2}$ and ...
1
vote
1answer
34 views

Does entropy inequality hold for convex combination

I have two pairs of Random Variables, $(\mathbb{X},\mathbb{Y})$ and $(\mathbb{M},\mathbb{N})$ which satisfies, $H(\mathbb{X})>H(\mathbb{Y})$ and $H(\mathbb{M})>H(\mathbb{N})$. For some convex ...
0
votes
1answer
44 views

Understanding a Sardinas-Patterson Theorem example

If $C = \{0,01,011\}$, then $C_\infty = \{1,11\}$ which is disjoint from $C$. It follows from the Sardinas-Patterson Theorem that $C$ is uniquely decodable, as we have already seen. What is the ...
1
vote
1answer
58 views

Proving that the entropy is zero given conditional entropies

Let's suppose we have 4 random variables $X,Y,Z$ and $T$ and that the following equations hold about the entropy: $$H(T|X)=H(T)$$ $$H(T|X,Y)=0$$ $$H(T|Y)=H(T)$$ $$H(Y|Z)=0$$ $$H(T|Z)=0$$ Also, the ...
1
vote
0answers
27 views

conditional mutual information

I have a question about mutual information $$I(Z ; T/X,Y) = I(T/X,Y ; Z)$$ $T,X,Y,Z$ are random variables is this statement accurate? if it is true and I know that I(Z;T/X,Y) = H(Z/X,Y) - ...
1
vote
1answer
64 views

Entropy and Mutual Information

Consider two discrete random variables $X$ $\{x_1,x_2,\dots,x_n\}$ and $Y$ $\{y_1,y_2,\dots, y_n\}$. Lets say that entropy $H(X)=0$ i.e. $X$ has a probability distribution s.t. $P(X=x_j) = 1$ for only ...
0
votes
1answer
57 views

Conditional entropy under quantization

Let $X$ be a continuous random variable and $X^n$ its quantization that becomes finer with larger $n$. Let $Y$ be a deterministic function of $X$. Then we have that the conditional entropy $$H(Y|X) = ...
0
votes
0answers
34 views

Bijection between polar and Cartesian coordinates

Let $(r,\theta)$ be the polar coordinates of a point in the plane. Then for any integer $k$, $(-r, \theta+(2k+1)\pi)$ and $(r, \theta+2k\pi)$ represent the same point. It seems intuitively obvious ...
0
votes
1answer
34 views

If $X$ to $Y$ to $Z$ is a Markov chain, prove or disprove $H(Y\mid X)\le H(Z\mid X)$

If $X \to Y \to Z$ is a Markov chain, prove or disprove $H(Y\mid X)\le H(Z\mid X)$. I said the statement was true, and from $I(X;Y)\ge I(X;Z)$ by definition, thus $H(X) - H(X\mid Y) \ge H(X)-H(X\mid ...
2
votes
1answer
55 views

Does it pay to know what you know?

Let's play a game. I ask you question a yes/no question, and you answer. You don't answer with a yes or no though, you answer with a probability of it being yes ($P \in (0,1)$). For example, I might ...
0
votes
1answer
27 views

Distribution of Markov Chain with transition matrix

An optional challenge assignment: Given a stationary Markov chain $\mathbf X=(X_k)^\infty_{k=1}$ where $X_k$ takes values in {0,1,2}. Let it have a probability transition matrix ...