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)

2
votes
1answer
34 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
44 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
32 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 ((f(X,Y),...
0
votes
1answer
45 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
40 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
20 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
22 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
408 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
17 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
28 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 H(X|...
4
votes
1answer
71 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
26 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) = -(.5*...
1
vote
0answers
12 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
31 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
103 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
48 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 case,...
1
vote
0answers
27 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
50 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
17 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
21 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
48 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 p(x,...
1
vote
1answer
42 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
22 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
74 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
30 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) - H(Z/T,X,...
1
vote
1answer
68 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
58 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
41 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
35 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
56 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
28 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 $P=[P_{ij}]=Pr(X_{k+1}=...
1
vote
1answer
39 views

What is the link between homomorphisms and mutual information?

Intuitively, there seems to be a link between the (kind of) homomorphism between two algebraic structures and the mutual information between two variables. However, since I'm not a mathematician, it's ...
0
votes
0answers
26 views

Inference on a factor graph (Sum-product Algorithm)

I was going through the sum-product algorithm which can be used to find marginal distribution efficiently(and exactly) when the factor graph is a tree. I found it difficult to understand the way they ...
0
votes
0answers
24 views

Cool property of KL divergence, help me fix my reasoning

So for any rv $X$ and any event $E$ the following property should hold for KL divergence: $$\log \frac{1}{P_X(E)} = D(P_{X|X\in E} \| P_X)$$ I think this is pretty remarkable, but I don't seem to be ...
1
vote
1answer
45 views

Rate distortion function with infinite distortion

I am working through the problems in Elements of Information Theory by Cover and Thomas and have come across the following problem I couldn't answer. The problem is to find the rate distortion ...
-1
votes
1answer
21 views

Does the Information Gain algorithm favor a high-entropy attribute or a low-entropy one?

This might not be mutual to mathematics but it does relate to Information-Theory. My question is: Does the InformationGain algorithm, in Decision-Tree machine-learning, favor a high-entropy ...
0
votes
0answers
33 views

Channels with memory have higher capacity

I am working through Elements of Information Theory by Cover and Thomas and have come across the following solution to one of their problems that I don't understand. Consider a binary, symmetric ...
3
votes
3answers
50 views

“Self-referential” probability mass functions

I am currently self-studying information theory from "Quantum Information Theory" by Mark M. Wilde. He uses a kind of notation that I don't understand at all. I will explain the problem using ...
5
votes
1answer
98 views

Mutual information vs Information Gain

I always thought that mutual information and information gain refer to the same thing, however looking at Wikipedia: http://en.wikipedia.org/wiki/Information_gain https://en.wikipedia.org/wiki/...
0
votes
0answers
62 views

Generalization of Shannon's source coding theorem with a posteriori entropies

This doubt is with reference to section 5-5 of "Information theory and Coding" by Prof. Norman Abramson. Under the topic "A generalization of Shannon's First Theorem", the text discusses how knowledge ...
5
votes
3answers
84 views

Greater/lesser search with one false answer allowed

It is well known that you can determine the values of $n\geq 2$ bits using $k$ yes/no questions about the bits (for example, "is $x_1 \oplus x_3 = 1$?), even if one (but not more) of the answers ...
2
votes
2answers
72 views

Deducing an integer from $0$-$15$ and lying

I'm interested in reducing the upperbound of the number of questions needed and in finding alternate solutions to solve the following question: Suppose I have thought up an integer between $0$ and ...
2
votes
0answers
22 views

Showing that for a family of subsets of $[n]$ enough elements appear in high frequencies

Let $\mathcal{F} \subseteq 2^{[n]}$ a familiy of subsets. Assume that the following applies: For every $A \subseteq [n]$ , such that $|A|\leq \alpha n$ ($\alpha > 0$ is given), there's a subset $...
2
votes
2answers
29 views

Unique Decodability

Prove that code C is uniquely decodable if the extension $C^k(x_1,x_2,...,x_k)=C(x_1)C(x_2)...C(x_k)$ is a one-to-one mapping from $\mathcal{X}^k$ to $D^*$ for every $k\geq1$. I know that for ...
0
votes
1answer
21 views

Uniquely Decodable and Instantaneous

Which of the following codes are (a) uniquely decodable? (b) instantaneous? $C_1={00,01,0}$ $C_2={00,01,100,101,11}$ $C_3={0,10,110,1110,...}$ $C_4={0,00,000,0000}$ For part a, I think only $C_3$ ...