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
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
21 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
96 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 case,...
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
41 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
16 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
44 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
38 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
71 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
29 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
67 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
40 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
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
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
23 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
23 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
41 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
20 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
48 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
59 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
81 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
21 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
20 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$ ...
1
vote
0answers
15 views

Subfair odds and Kuhn-Tucker conditions

I'm reading Elements of Information Theory by Cover and Thomas and they touch on the fact that when computing the optimal betting strategy when the odds are subfair and one may not bet a certain ...
0
votes
1answer
40 views

Upper bound on Huffman codeword length

I am reading Elements of Information Theory by Cover and Thomas and have been unable to find an upper bound on the length of a codeword in a Huffman code, either in this book or on the web. Does one ...
0
votes
0answers
29 views

Optimal Betting on One Horse

A specific horse has odds o and you consider the chance of this horse winning to be p. You are given the opportunity to bet a fraction b of your money on this horse, while the remaining fraction 1 − b ...
1
vote
0answers
27 views

Huffman Code Assuming Wrong Distribution

Assume the random variable X ∼ p(x). We design a Huffman code C for this X but unfortunately we assume an incorrect probability distribution p' for the random variable. What can you say about the ...
1
vote
0answers
34 views

Question on the motivation of Information Geometry

In the Preface of 'Methods of Information Geometry': We consider the set, $S$, of normal distributions $P(x; \mu, \sigma) = \dfrac{1}{\sqrt{2\pi }\sigma}\exp \left \{ - \dfrac{(x-\mu)^2}{2\sigma^2}\...
1
vote
1answer
51 views

Calculating the capacity of a Binary Channel?

I'm pretty new in information theory so I need your suggestions or references in order to solve this problem. I have my attempt below. Problem: Every second, Alice can either send (bit 1) or not ...
0
votes
0answers
43 views

Conditional probability between two random vectors: input and output of a channel.

Suppose we send a sequence of $n$ bits $X=\{x_1,...,x_n\}$ through a channel. Each $x_k=1$ with probability $p$, and $x_k=0$ w.p. $1-p$. The channel flips one input bit with probability $q$. If $Y=\{...
0
votes
1answer
24 views

PRNG for compression

I'm trying to intuitively grasp information theory. You have a string of size X that contains a lot of information, say it's a movie. You have a string of size N << X which is going to be the ...
0
votes
1answer
24 views

Is relative entropy with respect to a pmf a continuous function?

Is the relative entropy $D(p || q)$ with a fixed pmf $q$, continuous over $p$, where $p \in \{x \in \mathbb{R}^n: \sum_{i=1}^n x_i = 1 , x_i \geq 0 \}$?
0
votes
0answers
22 views

Entropy of sum of uniform random variables on a simplex [duplicate]

For two i.i.d random variables $X$ and $Y$, which are uniformly distributed on the $n$-dimensional simplex $\Delta_n= \left\{(x_1,\ldots,x_n): x_i \geq 0, \sum_i x_i \leq 1 \right\}$, I want to find ...
0
votes
1answer
48 views

Conditional entropy and independent conditioning variables

Let $X,Y,Z,Y',Z'$ be random variables where $Y\sim Y', Z\sim Z'$, $Y$ and $Z$ are independent, while $Y'$ and $Z'$ are, in the sense that we have $p(X,Y,Z)=p(X|Y,Z)p(Y)p(Z)$ $p(X,Y',Z')=p(X|Y',Z')p(...