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

estimating mutual information via nearest neighbourhood

I am not sure this is the best place to ask this kind of question about discussing the content of a paper. Anyway, here is my question: There is a famous paper from Physical Review E 69, 066138(2004) ...
0
votes
0answers
33 views

Cardinality of Time Sharing Random Variable for Multiple Access Channel

it is well know that capacity of MAC is \begin{align} R_1 \le I(X_1;Y|X_2,Q)\\ R_2 \le I(X_2;Y|X_1,Q)\\ R_1 \le I(X_1,X_2;Y|Q)\\ \end{align} where $|Q| \le 4$. How is the bound on $Q$ derived?I ...
1
vote
0answers
86 views

Information set of a linear code

I am trying to prove a couple of statements about information sets of linear codes, but i am having trouble with these proofs or i am not sure if i understand correct what i should prove. I would ...
0
votes
1answer
44 views

Huffman code with specific source

There is n-ary Huffman code. Source has the following relative frequencies of t symbols: 1, $n$, $n^2$, $n^3$, . . . , $n^{t−1}$, where $t = 1 + k(n − 1)$ for some positive integer $k$. I need to find ...
0
votes
1answer
46 views

Conditional entropy of repetition code over BSC

Consider the channel that takes in a bit, repeats it $k$ times, then sends the result over a binary symmetric channel with transition probability $p$. For example, if $0$ was sent over the channel ...
0
votes
2answers
89 views

Derivative of mutual information

Here is the definition of mutual information $I(X;Y) = \int_Y \int_X p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)} \right) } \; dx \,dy,$ where $x$ and ...
5
votes
0answers
154 views

Convergence of mutual information

Let $P_n (x,y)$ be a sequence of (cumulative) probability distributions defined on $\mathcal{X}\times \mathcal{Y}$ (of arbitrary cardinality), that weakly converges to $P(x,y)$: $$ P_n (x,y) ...
0
votes
2answers
169 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 ...
1
vote
1answer
109 views

Prove there exist a $p$ so that the inequality holds

I am stuck with the following problem. Given the Gaussian mixture distribution $f(\cdot)$ $$ f(x) = ...
1
vote
0answers
35 views

Minimum of an Entropy based function

This question is a small part of a bigger problem I am working on. Let $h(p)$ be the binary entropy function. That is, for $p \in (0,1)$ $$h(p) = -p\log_2(p) - (1-p)\log_2(1-p)$$ Define the ...
0
votes
0answers
74 views

How to compute the topological entropy of a permutation?

I have a permutation, say as ${4,1,7,2,3,5,6}$, given by its induced matrix. According to this paper (Proposition 11 on p. 82), To compute its topological entropy, one can compute the ...
0
votes
1answer
35 views

What is the meaning of E and d in this formula?

I am trying to learn the information bottleneck method. On slide 15, they give this equation. I think I understand that X is a random variable (but do not understand the meaning of the exponent, n). I ...
1
vote
0answers
86 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
0answers
193 views

Mutual information between two Gaussian distribution

Suppose we have two variables $x_i$ and $x_j$ with covariance matrices $P_i$ and $P_j$ and cross-covariance $P_{ij}$. I'd like to find the mutual information on them. From reverse engineering of some ...
1
vote
0answers
27 views

KSE and Shannon entropy

Is there a theoretical connection between Kolmogorov-Sinai and Shannon entropies? What is it?
1
vote
1answer
43 views

How many points does it take to identify a low-order polynomial in $\mathbb{Z}_N$?

I want to split the Bush's Baked Beans recipe into $M$ parts so that any set of $N<M$ people can reconstruct the recipe, but with the following constraints: Each person knows only a yes or no ...
0
votes
1answer
75 views

Probability density function of entropy of a gaussian variable

I have a problem finding the probability density function of entropy of a normally distributed sample. It is known that the entropy of a gaussian variable $X$ equals $H=h(X)={1\over2}\log(2\pi ...
0
votes
0answers
34 views

Bound the entropy knowing the largest denominator

The problem comes up from considering sampling from a discrete set of $n$ items with integer weights. The $i$th item has weight $w_i$, the probability getting chosen is $w_i/\sum_j w_j$. Certainly the ...
5
votes
2answers
126 views

Determinant of Fisher information

In information geometry, the determinant of the Fisher information matrix is a natural volume form on a statistical manifold, so it has a nice geometrical interpretation. But what is it in ...
2
votes
2answers
55 views

$H(X\mid Y_1, Y_2) \leq H(X\mid Y_1)?$ (Conditional Entropy with conditioning on multiple RVs)

In short, my question is whether the "conditioning reduces entropy" maxim is also true when conditioning on one random variable as compared to conditioning on two: $$H(X\mid Y_1, Y_2) \leq H(X\mid ...
0
votes
1answer
74 views

Is it possible to study information theory while studying a first course on probability?

I'm currently taking a course on intro to probability. The course is not mathematically rigorous and does not invoke theorems from real analysis, etc. The course covers all the way from basic ...
2
votes
1answer
40 views

Self-information, one event half as likely than another event conveys twice the amount of information?

I was reading the following: "If one event is half as likely as another, then learning about the former event shouldconvey twice as much information as the latter" I know it should be easy to ...
0
votes
1answer
55 views

How is this paper using probability notation?

I am trying to understand this paper about documents and sentences. At the end of page three, they say: Let g(wi, wj ) be the distance between two events (1 if in the same sentence, 2 in neighboring, ...
0
votes
1answer
49 views

Erasure Codes with Simplex Locality

In here, theorem $1.1$. there is this line 'Since $G$ has full rank it is possible to enlarge $N$ to a set $N^{'}$ ... exactly $k-1$. Note that the enlargement operation ... any of the leaders' in the ...
-2
votes
1answer
66 views

Analysis of Kullback-Leibler divergence

Let us consider the following two probability distributions ...
1
vote
2answers
234 views

Upper bound on the entropy of a sum two random variables

Let $X$ be a random variable such that $|X| \leq A$ almost surely, for some $A > 0$. Let $Z$ be independent of $X$ such that $Z \sim {\cal N}(0, N)$. My question is: How large can the entropy ...
0
votes
1answer
49 views

mutual information of coupled variables

I have been looking for a method for evaluating the mutual information between a combination of source variables, $X_0, X_1$ and a target variable, $Y$. $$I(Y;X_0,X_1)$$ When I look on wikipedia's ...
1
vote
2answers
54 views

Ways to code two arbitrary binary strings into one without loss of information, and relevant bounds

If the title was not clear, I'm examining methods of taking two binary strings as input and outputting one binary string in such a way that the two original strings can be extracted from the output, ...
2
votes
1answer
65 views

partition with infinite entropy?

Let $P$ be an infinite partition of the interval $[0,1]$. Let $P$ have elements $I_i$ which has Lebesgue measure $m(I_i)$. Then the entropy of $P$ is defined by $\sum_i -m(I_i)\log m(I_i)$. Can this ...
1
vote
0answers
22 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
38 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
0answers
257 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
7
votes
3answers
193 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
121 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
69 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
29 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
100 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
47 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
236 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
102 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
122 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
317 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
1answer
391 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
70 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
54 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
35 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
65 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
176 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
77 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$ ...
0
votes
3answers
1k 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 ...