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
17 views

Entropy of linear codes

To find the theoretically performance-maximizing coding scheme, we need to find $P_{X^n}$ such that it maximizes entropy. The best linear coding scheme is the maximum entropy probability distribution ...
-1
votes
0answers
39 views

Great mathematics! [on hold]

Wonder if there is some topic in mathematics I haven't come across yet, which really makes one experience a new way of thinking about mathematics and logic in general? Learning calculus was a really ...
1
vote
0answers
19 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) ...
7
votes
3answers
153 views
+100

(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) ...
0
votes
0answers
29 views

Intuitive explanation of Shannon's source entropy in information / communications theory

I am trying to calculate the number of bits required to encode a message. FOr that, I am applying Shannon's entropy, H. I have done the implementation and playing around with themessage length and ...
1
vote
0answers
10 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
21 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: ...
0
votes
0answers
11 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
13 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
9 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
25 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
64 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
46 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
25 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
32 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
9 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
38 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
27 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
32 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
25 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
55 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
24 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
63 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
53 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
33 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
54 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 ...
1
vote
1answer
38 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
20 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
22 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 ...
0
votes
0answers
22 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
16 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
29 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 ...
4
votes
1answer
90 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 ...
0
votes
0answers
56 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 ...
1
vote
0answers
19 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
68 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
18 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$ ...
0
votes
0answers
14 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
38 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
22 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 ...