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
votes
0answers
35 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 ...
2
votes
1answer
531 views

How come that HSL can contain more information than RGB?

I have noticed weird thing when working with HSL - unlike RGB, it has some blind spots where certain value just does not matter. I'm sure we were taught about this when I had Linear algebra lectures ...
1
vote
2answers
690 views

what is the mutual information of three variables?

mutual information of tow variables is $\displaystyle\sum\sum p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$ what is the mutual information of three variables? is it $\displaystyle\sum\sum\sum ...
0
votes
0answers
15 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) ...
0
votes
0answers
20 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 ...
0
votes
1answer
52 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) = ...
2
votes
1answer
57 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 ...
1
vote
0answers
9 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 ...
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
0answers
31 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
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) = ...
0
votes
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 ...
0
votes
0answers
44 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 ...
32
votes
8answers
8k views

Intuitive explanation of entropy?

I have bumped many times into entropy, but it has never been clear for me why we use this formula: If $X$ is random variable then its entropy is: $$H(X) = -\displaystyle\sum_{x} p(x)\log p(x).$$ ...
0
votes
1answer
18 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 ...
4
votes
1answer
37 views

Asymmetric Multiple Error Correction

In some non-volatile memories, errors are only affect one logic state (just 1->0). Is there a coding technique which could correct k asymmetric errors? I know that the BCH code could correct k random ...
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
58 views

Metric Entropy Upper Bounds

In the paper Information-Theoretic Determination of Minimax Rates of Convergence the authors present Theorem 3 as follows: If $M_2(\epsilon)$ is the $\ell_2$ packing entropy of a density class ...
1
vote
1answer
37 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 ...
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
1answer
26 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
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
1answer
29 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
23 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
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
61 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 ...
2
votes
2answers
86 views

How to incrementally reveal information

Please give a protocol to incrementally reveal information. A politician wishes to make a yes/no announcement with out shocking the economy. They set a date 100 days in the future, and every day ...
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
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 ...
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 ...
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 ...
4
votes
2answers
418 views

Positivity of Renyi Mutual Information

The differential Renyi entropy for a probability distribution is given by $H_q(P(X))=\frac{1}{1-q}\log\int p^q(x)dx$. In the limit of $q\to 1$, it reduces to the usual Shannon entropy. We can write ...
1
vote
1answer
48 views

Justifying $\log{\frac{1}{P_{X}(x)}}$ as the measure of self information

I was reviewing self information and then came to realize that there is one idea that I have that I believe should be wrong but don't know why. Let self-information associated with a random variable ...
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 ...
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 ...
2
votes
0answers
196 views

How to deconstruct Shannon Joint Entropy $H(X,Y,Z)$ equation for semi-related variables?

Background The purpose of this is to produce a shuffle correction for Transfer Entropy estimation: $$\operatorname{TE}_{x\to y}=H(X_{t+\tau})-H(X_\tau)-H(X_{t+\tau},Y_t,X_t)+H(X_t,Y_t)$$ In order ...
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 ...
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 ...
2
votes
3answers
2k views

How is logistic loss and cross-entropy related?

I found that Kullback-Leibler loss, log-loss or cross-entropy is the same loss function. Is the logistic-loss function used in logistic regression equivalent to the cross-entropy function? If yes, can ...
0
votes
0answers
55 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 ...