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

Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Let $p_0(x)$ be some arbitrary but fixed input probability distribution. The mutual information between the input ...
2
votes
1answer
45 views

Confusion about non-negative mutual information

The formula I was given for calculating information for a specific stimulus $s_x$ is: $$I(R,s_x) = \sum_i p(r_i|s_x) \log_2{p(r_i|s_x)\over p(r_i)} $$ It was also said that information is always ...
7
votes
3answers
231 views

Using decimals of $\pi$ to store data

I read recently about an idea to, instead of storing actual data, converting the data to a string of digits and then store the index of where this pattern occurs in some number, for example $\pi$. The ...
3
votes
1answer
138 views

Upper Bound on Mutual Information

I am interested in an upper bound on mutual information that I have been encountering frequently in the statistics and probability literature. I have yet to see the "purest" form of the inequality, so ...
3
votes
0answers
102 views

Mutual Information for Gaussian Process (and also Fano's Inequality)

According to this presentation: Bounding Gaussian Process Information Gain we have a closed-form expression for the information gain as follows: $$ I\left(\vec{y} \mid f\right) = \frac{1}{2} \log\det ...
1
vote
0answers
30 views

Do 2 timeseries represent the input better than one?

I only have a very basic familiarity with signal processing and information theory so I'm sorry if this is a very straight forward question. I have a very brief input signal and two timeseries as ...
3
votes
1answer
101 views

Relationship between two measures of inequality

Let $A = \{a_1,\dots,a_n\}$ be a multi-set and let $B$ be the set of distinct elements in $A$. Now define $H(A) = -\frac1n \sum_{x \in B} f(x) \log_2(f(x)/n)$ where $f(x)$ is the number of times $x$ ...
0
votes
1answer
57 views

Bounds for Mutual Information

$V_1$, $V_2$ be two binary strings with equal number of bits (say the length is $l$). Then the mutual information of $V_1$, $V_2$ can be defined as: $I(V_1;V_2)$ = $\sum_{y \in Y} \sum_{x \in X} ...
5
votes
2answers
333 views

How to Count the number of words over an alphabet subject to restrictions on letter count?

For an alphabet $X$, is there a method of computing how many words over $X$ of length $n$ there are where the number of occurrences of each letter must satisfy a system of equations? For example if ...
1
vote
2answers
224 views

Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
1
vote
1answer
161 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits ...
0
votes
1answer
683 views

Using binary entropy function to approximate log(N choose K)

I am not a mathematician and struggling with the exercises while reading this book Information Theory, Inference and Learning Algorithms. The author introduced the binary entropy function at the ...
1
vote
3answers
939 views

How is the formula of Shannon Entropy derived?

From this slide, it's said that the smallest possible number of bits per symbol is as the Shannon Entropy formula defined: I've read this post, and still not quite understand how is this formula ...
0
votes
1answer
99 views

Equality of Information Gain and Mutual Information

I am curious about definition of information gain and mutual information in the context of feature selection. If looks like two these measures define exactly the same thing, however I didn't find ...
2
votes
0answers
56 views

Shannon-Fano analysis, Binary-search-like

Prove that the codewords of the Shannon-Fano code satisfy $l_i \leq \left \lceil \log _2 \frac1{p_i}\right \rceil$. Elementary wording: given positive numbers in descending order $p_1,...,p_n$, ...
0
votes
1answer
38 views

Mutual information decrease with coarse-graining

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$. Is it true that: If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus ...
5
votes
1answer
84 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
5
votes
1answer
181 views

Entropy of the induced transformation

I need help with this problem: Let $(X,\mathcal{B},\mu,T)$ be a ergodic dynamical system in the probability space $(X,\mathcal{B},\mu)$. Let $A \in \mathcal{B}$ with $\mu(A)>0$. We define the ...
2
votes
1answer
89 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
1
vote
3answers
2k views

Similarity between two probability distribution

I am not sure how to put the question. I am not even sure if this question makes sense at all. I know that the similarity of two discrete (or continuous) distributions can be quantified by ...
0
votes
1answer
72 views

A question on Markov chain

Suppose for two random variables $X$ and $Y$ we have $X\perp\!\!\!\perp Y$ and also assume that three random variables $X$, $Y$ and $Z$ form the following Markov chain: $X\to Z\to Y$. Do these two ...
0
votes
1answer
111 views

Entropy of sum is sum of entropies

Having $X$ and $Y$ discrete random variables above finite set. Z is defined as $Z=X+Y$ when does the following happen: $$H(Z)=H(X)+H(Y)$$
2
votes
0answers
93 views

Good low-rate, short-length block codes

I am highly unsure whether this question is appropriate for this site (as it is at no point a math problem), yet searching in the stackexchange universe for similar topics showed the most hits on ...
1
vote
0answers
75 views

What is the “true” entropy of a binary string?

Consider an infinite binary string $\sigma$ and define its entropy $$H_1 = -(p_0 \log_2 p_0 + p_1 \log_2 p_1)$$ with $p_i = \lim_{N\rightarrow \infty} N(i)/N$, $N(i)$ the number of $i$'s among the ...
3
votes
0answers
33 views

Entropy of Group Action by Knowing Finiteness of Unidimensional Subaction

I've been trying to solve the following problem " Considering a measurable dinamical system $(X, \mathcal{B}, \mu, \mathcal{T})$ where $\mathcal{T}$ is an action of a semigroup $G = N^d$ on $X$ for ...
2
votes
0answers
71 views

Is there an information theory for continuous time signals?

Information theory books talk about entropy and mutual information of discrete time processes, such as a sequence of symbols sent with a symbol period $T_s$ and there received sequence. Can we talk ...
-9
votes
2answers
176 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory [closed]

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
3
votes
0answers
91 views

Doubts in Bayes' Theorem

I meet one problem on the probability and statistic theory. "Assume given the probability spaces $(X,S,\mu_i)$, $i=1,2$, and the probability space $(X,S,\lambda)$. And there exsit functions ...
1
vote
1answer
192 views

Mutual Information in an Binary Erasure Channel

Imagine a Binary Erasure Channel as depicted on Wikipedia. One equation describing the mutual information is following: $$\begin{array}{rcl} I(x;y) &=& H(x) - H(x|y) \\ &=& ...
0
votes
1answer
66 views

Calculating Entropy of Dependent Random Variables

So basically I'm trying to answer the following exam problem: I'm half struggling on H(Z | X) and H(X | Z) and mainly just need confirmation. I know that H(Z | X) = -SUM P(Z|X)P(X)logP(Z|X) ...
0
votes
1answer
123 views

Subadditivity of Entropy

We define $H(X) = -\sum_{x}p_{x}\log p_{x}$ and relative entropy as $H(p(x)||q(x)) = \sum_{x}p(x)\log \frac{p(x)}{q(x)} = -H(X)-\sum_{x}p(x)\log q(x).$ Now we have to prove that $H(X,Y,X) + H(Y) \leq ...
2
votes
2answers
48 views

Does X|Y = X formally, in the sense of RVs?

In Cover and Thomas' "Elements of Information Theory", the joint entropy $H(X,Y)$ is defined, but they state that this definition is nothing new if we consider that it is the entropy of a single ...
1
vote
0answers
50 views

Help understanding KL-Divergence

I will be doing a course in Information Theory soon and to get some early learning in I have been attempting a question with a joint probability mass function represented by the following table: In ...
2
votes
1answer
32 views

Are measures of information model specific?

Does an information measure for a signal do a better job if it assumes some things about the signal? For example: I have a digital stream of data, 0s and 1s coming at a clock rate $r$. What is the ...
3
votes
2answers
121 views

Bounding second moment of entropy

Entropy is defined as $E(-\log(P(x))$. We know it is bounded by $\log(r)$ when $r$ is the size of alphabet. Defining the second moment as $E(\log^2(P(x))$, how to show it is bounded?
0
votes
1answer
57 views

How does the presenter in this video derive this formula?

I am watching this coursera video on entropy (in the information theory sense of the word). Right around the two minute mark the presenter shows two forms for H(p). The first (after the equals sign) ...
1
vote
2answers
168 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
0
votes
1answer
69 views

Conditional mutual information and Markov chain.

If we have the Markov chain $X \to Y \to Z$, or equivalently $$I(X;Z| Y)=0, \tag{1}$$ where $I(\cdot)$ denotes the mutual information. Does the Markov chain $X \to (Y,W) \to Z$ also hold? Or ...
0
votes
1answer
23 views

Loss of information while projecting multidimensional data

I'm interested in the evaluation of the loss of information after projecting multidimensional data. Since the dimensional reduction is a common tool to analyse data,a question about the loss of ...
2
votes
3answers
66 views

What's the name of the quantity $\mathbb{P}(A\cap B)/(\mathbb{P}(A)\mathbb{P}(B))\;$?

In a physics book, I've come across the quantity $$ \frac{\def\P{\mathbb{P}}\P(A\cap B)}{\P(A)\P(B)}\,, $$ where $A$ and $B$ are events. The author calls this quantity the correlation of $A$ and ...
5
votes
0answers
98 views

Looking for a a measure-theoretic treatment of “differential entropy”

If $X$ is a discrete random variable, its entropy $H(X)$ is usually defined as something along the lines of $-\sum \def\P{\mathbb{P}}\P(x) \log_2( \P(x))$, where the sum ranges over all the possible ...
3
votes
1answer
58 views

How much information is in the question “How much information is in this question?”?

I'm actually not sure where to pose this question, but we do have an Information Theory tag so this must be the place. The "simple" question is in the title: how do I know how many bits of information ...
2
votes
3answers
66 views

Why can we use entropy to measure the quality of a language model?

I am reading the < Foundations of Statistical Natural Language Processing >. It has the following statement about the relationship between information entropy and language model: ...The ...
1
vote
1answer
328 views

The golden ratio in statistics of literature

Let a book, for example, or a poem... It consists in words and letters and symbols like : ;,!... Let $W_b$=the number of words of the book. Let $L_b$=the number of letters of the book. The number ...
1
vote
1answer
37 views

information and coding theory weakly independent problem

$X$ is weakly independent of $Y$ if the rows of the transition matrix $\begin{bmatrix}p(x|y)\end{bmatrix}$ are linearly dependent. Show that if $X$ and $Y$ are independent, then $X$ is weakly ...
1
vote
2answers
106 views

Shannon Entropy Minimization

The Shannon Entropy for an observation is given by $ -x \log_2(x)$. Why is the maximum entropy achieved at $x = \frac{1}{e}$, and not at $x = 0$? Could someone provide a logical explanation that ...
1
vote
0answers
225 views

In the Stinespring dilation theorem, what is the minimum dimension for which a dilation Hilbert space of this form is guaranteed to exist?

This may look like a problem that could easily be looked up, but it's not quite as easy as it first appears, hence my asking. I'm going to phrase my question in terms of the "Schroedinger picture" ...
0
votes
1answer
99 views

An inequality about entropy

Suppose we have random variable $X=\{x_1,\cdots,x_n\}$ with probability mass function $p$. The entropy is defined by $$H(X)=\sum_{i=1}^np(x_i)\log_b(p(x_i)^{-1})$$ where $b$ is any integer $\geq ...
8
votes
2answers
749 views

How to make the encoding of symbols needs only 1.58496 bits/symbol as carried out in theory?

I'm reading the tutorial of Information Gain, and I see the following page: I know in the example above, I can encode this way: A 0 B 10 C 11 and then this ...
0
votes
1answer
45 views

Mutual information and Independence [closed]

Let X, Y, Z be 3 random variables such that X and Z are independent. then can I say that I(X;Y|Z) = I(X;Y). and why?