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)

2
votes
0answers
43 views

Fisher Expected Information for a Gaussian Process model

Suppose I have a two dimensional Gaussian process model (GP), defined by a squared exponential correlation function s.t: $$R(x_{i},x_{j}) = \exp\left(-\frac{|x_{i} - x_{j}|^2}{2}\right).$$ I am ...
3
votes
1answer
70 views

sufficient and necessary condition for equality between conditional mutual information and unconditional one.

Suppose $X, Y, Z$ are three discrete random variables. Is there a good sufficient and necessary condition for $I(X;Y|Z) = I(X;Y)$? Usually the LHS can be bigger or smaller than the RHS, but if Z is ...
1
vote
1answer
34 views

Min/Max number of inequalities needed to determine the order of $n$ numbers

We are given an ordered $n$-tuple of positive real numbers $R=(r_1,..r_n)$. A $k$-inequality is an inequality of the form $x_1<x_2<...<x_k$ where $x_1,..,x_k$ are in $R$. For example, for $...
2
votes
1answer
100 views

Blackwell's informativeness criterion

Let $a=(a_1,\dots,a_i,\dots,a_n)$ be a probability vector, i.e. $\forall i: a_i\ge0$ and $\sum_i a_i=1$. Suppose $b$ is another $n$-dimensional probability vector. Is it true that there always ...
0
votes
1answer
71 views

Ratio between forward and reverse conditional probability

I have a probability distribution $p(Z | X)$ from which I can easily sample and compute the probability at every value for $Z$ and $X$. The inverse distribution $p(X | Z)$ however can be very complex ...
2
votes
2answers
405 views

How to prove H(X,Y) $\ge$ H(Z)?

I'm solving a problem from elements of information theory, 2nd. I got stuck by question(c) and actually, I've checked the answer, here it is: How to prove the inequality from the answer that is H(...
0
votes
1answer
67 views

Calculating the information per symbol of a markov chain source

I have a 4-state 2nd order markov chain source with symbols 0 and 1. I have all the transition probabilities and have worked out the probabilities of each state. How do I go about finding the amount ...
1
vote
1answer
39 views

Is there any differentiable function $f$ that approximates the “entropy” of a set of numbers $S$?

Where entropy is some measure of the degree of randomness/disorder in a given set of numbers: $S = \{a_1, a_2, ..., a_i\}$ For example, the set $S_{high} = \{4,0,2,5,8,3,7,2,5\}$ has a high degree of ...
2
votes
1answer
195 views

Coupon Collector Problem for Non-Uniform Coupons: On the number of missed Coupon

Suppose $\mathcal B=\{1,2,\ldots,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,\ldots,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$. The "...
2
votes
0answers
107 views

What is the variance of self-information (or surprisal)?

The self-information of an outcome $x_i$, or surprisal, is defined as: $$ I(x_i)=-\log P(x_i), $$ where $P$ means probability. This way, the Shannon entropy can be seen as the "average" or "expected" ...
2
votes
0answers
86 views

How to Calculate Values from Incoming Messages? - Evidence Propagation in Bayesian Network

I'm currently trying to wrap my head around evidence propagation in bayesian network (simple tree propagation) but I'm having trouble finding information about the process. As an example, let's take ...
1
vote
1answer
89 views

data processing inequality using non-deterministic functions

Generally data processing inequality says that the entropy cannot increase on applying a function f, or to be precise $H(f(X))\leq H(X)$ (also it is reversed if we know the function is k-to-1 so there ...
0
votes
0answers
25 views

Change of bases for entropy

From Cover and Thomas, Elements of Information Theory: Why isn't it: $ \log_b(p) = \frac{\log_a(p)}{\log_a(b)} $, so that $ H_a(X) $ is multiplied with $ \frac{1}{\log_b a} $?
0
votes
1answer
87 views

How a Galois Field is used to construct a Hamming Parity Matrix

I'm trying to understand how Matlab is generating their Hamming parity matrix. The default according to the documentation is GF(2^m), where m=3. Hamming(7, 4) parity matrix from Matlab ...
0
votes
1answer
66 views

Largest positive eigenvalue of a matrix

I am dealing with the Capacity of constrained noiseless communication channels. It has been said that the channel capacity of such a channel is $\log{\lambda}$, which $\lambda$ is the largest positive ...
3
votes
1answer
102 views

Constructor theory distinguishability

In David Deustch and Chiara Marletto's Constructor Theory of Information (section 5) a set of attributes $S$ is defined as distinguishable if the task of transforming each attribute $x$ of $S$ into an ...
7
votes
1answer
77 views

Structure of equientropic transformations

Given a probability vector $v=(v_1,\ldots,v_n)$ with $1\geq v_i\geq 0$ and $\sum_{i=1}^n v_i=1$ its entropy can be defined as: $$ H(v):=-\sum_{i=1}^nv_i\log v_i $$ I wonder what is known about ...
0
votes
0answers
34 views

Identifying a Markov chain

This is a very basic question in the theory of Markov chains and I'm just not sure how to prove it mathematically. Say we have random variables $X, Y$ that are correlated and we have a possibly ...
0
votes
0answers
75 views

How to calculate the mutual information between two outputs of Rayleigh fading channels

We have the two channels: $$X_{a,i} = H_{i}s_{i} +N_{a,i} \\ X_{b,i} = H_{i}s_{i} +N_{b,i} $$ for $1 \leq i \leq n$, where $H_i$ denotes the i.i.d. channel coefficient and is a zero-mean complex ...
0
votes
1answer
33 views

Relative Entropy decomposition reference

may I ask for some reference pointers? My bad as I got a classic case of losing my reference and thus unsure what I wrote was right or wrong. I tried looking my old references and internet and didn't ...
0
votes
2answers
50 views

Proving certain aspects of Entropy

I am trying to prove three properties of entropy. $1)$ $H(X|Y,Z)\le H(X|Y)$ $2)$ $H(X|Y,Z)\le H(X,Y)$ $3)$ $H(X,Y,Z)+H(Y)\le H(X,Y)+H(Y,Z)$ I have proved the third one, but it is based on part 1. ...
0
votes
1answer
66 views

Simple information theory question: where is this equation coming from?

I am reading a simple example of a joint distribution that looks like this: ...
0
votes
1answer
53 views

Comparing two mutual information expressions

Given the following Data Processing Inequality $$X\rightarrow Y\rightarrow Z$$ one can say that $$I(X;Y) \geq I(X;Y|Z)$$ Intuition tells me this is not correct since conditioning reduces entropy and ...
0
votes
1answer
347 views

Markov chain and mutual information

If $X\rightarrow Y\rightarrow Z$ follow a Markov chain, then we have the following properties$$I(X;Z)\leq I(X;Y)$$ where $I$ is the mutual information expression. Intuitvely I agree. I want to ...
0
votes
1answer
126 views

Entropy is upper bounded by cardinality of the random variable

How can one prove that the entropy of random variable $X$ is upper bounded by $\log|X|$? I tried the following $$H(x) = - \sum_x p(x)\log p(x)$$ $$ \leq - \sum_x p(x)\sum_x\log p(x)$$ $$= - \sum_x\...
1
vote
1answer
76 views

Have Information Theoretic results been used in other branches of mathematics?

consider this a soft-question. Information Theory is fairly young branch of mathematics (60 years). I am interested in question, whether there have been any information theoretic results that had ...
0
votes
1answer
63 views

Explanation of Information double summation within Normalized Mutual Information

The Normalized Mutual Information NMI calculation is described in deflation-PIC paper with the applicable formula copied to the screenshot shown below. My question is specifically about the double ...
0
votes
1answer
62 views

Binomial coefficients bounded by entropy exponential

So I'm trying to prove that for $\frac{1}{2}< x \leq 1$ we have $$\sum_{\lceil nx \rceil}^{n}{n \choose k} \leq 2^{nh(x)}$$ I've managed to prove that $$\sum_{0}^{\lfloor nx \rfloor}{ n\choose k}\...
0
votes
1answer
409 views

Capacity of Z Channel

Calculating the capacity of the Z channel (binary asymmetric channel) here, the entropy $ H(Y)$ isn't supposed to be $ H(Y)=H(a+(1-a)p,(1-a)(1-p))$ ? What's the reason for having $H(Y)=H((1-a)(1-p))$ ?...
0
votes
1answer
62 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
2answers
321 views

Convexity of mutual information $I(X;Y)$ in conditional $p(y \mid x)$

I'm trying to understand the proof that $I(X;Y)$ is convex in conditional distribution $p(y \mid x)$ - from Elements of Information Theory by Cover & Thomas, theorem 2.7.4. In the proof we fix $p(...
0
votes
2answers
85 views

Question regarding the Entropy of a probability mass function

I assume that the entropy, $E$, of a probability mass function (pmf), $p(X)$, of a discrete random variable, $X$, is computed as: $$\begin{align}\mathbb{E}(p(X)) &= -p(X = x_1)\log[p(X = x_1)]-p(...
1
vote
1answer
91 views

Relation between Genetic Algorithm and Information theory

Can anyone suggest me some references (papers, books, lecture notes) on the relation between GA and Information theory?
1
vote
1answer
38 views

Convexity of $I(X;Y)$: why $H(Y)$ convex in $p(y)$ $\Rightarrow$ $H(Y)$ convex in $p(x)$

I would like to understand the proof that mutual information $I(X;Y)$ is concave in $p(x)$ - as presented in Elements of Information Theory by Cover & Thomas, theorem 2.7.4. Here's the proof from ...
2
votes
1answer
37 views

conditional entropies for identical distributions

Let me say I have two distributions $X$ and $Y$ which are identical, but they are not independent. Now if were to calculate the conditional entropies $H(X|Y)$ and $H(Y|X)$. Is calculating one joint ...
1
vote
2answers
68 views

Probability of inequality, Markov inequality application

A bit of context: working on a problem about channel coding. Through a channel we are sending a random variable $X_n$, a code, and at the other side we see $Y$ (both discrete). Then we perform an ...
2
votes
0answers
41 views

Doubt in derivation of a proof in Information Theory

In my class we were trying to derive Shanon's Source Theorem, first by proving the equivalent form in a weaker version. The question is -Consider a biased coin with probability of heads $p \geq \frac{...
1
vote
1answer
65 views

Standard deviation of a baised $d$-sided coin

I know that that standard deviation of a noisy bit (a biased coin with probability distribution $\{ p, 1-p \}$ ) is given by $$ \sigma = \sqrt{p(1-p)} $$ What is then a measure of the standard ...
1
vote
2answers
75 views

Strategy to find out how wires are connected

There is a tube with $100$ electrical wires that are not labeled. At side $A$ of the tube, the terminal ends of the $100$ electrical wires can be connected. It is possible to connect more than $2$ ...
3
votes
0answers
94 views

Proving or disproving concavity of a function

I want to prove that the following function is concave (as a part of another proof). $$f(p) = \max_{\begin{matrix}x,y\\0\le x \le 1\\0\le y \le 1 \\ x * y = p\end{matrix}} \lambda h(x) + \bar{\...
0
votes
0answers
86 views

Absolute value of difference between entropies (of two distributions)

I have the following inequality for the $L_1$ distance between two distributions $Q$, $Q^n$ on a finite set $B$: $$\|Q-Q^n|| < \frac{2|B|}{n}\leq \frac{C}{n} \leq \frac12 $$ Assuming $C\geq2|B|$, ...
9
votes
1answer
182 views

Is Entropy = Information circular or trivial?

I have seen several "maximum entropy distributions" used in the mathematical and statistical literature, often with the justification that they are "minimally informed" beyond the assumptions and data ...
3
votes
2answers
229 views

Is Information Theory Mathematics?

When I read about Information Theory, for example on Wikipedia, I can never find statements that say if Information Theory is "real" Mathematics with underlying axioms, a notion of "proof beyond doubt"...
1
vote
1answer
362 views

What does “to first order in exponent” mean?

I am studying information theory on "Elements of Invormation theory" (Cover Thomas). I cannot understand the meaning of "to first order in exponent" in the following theorem: .............................
4
votes
3answers
3k 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 ...
2
votes
2answers
62 views

Channel code for multiple bit errors

I've been exploring information theory out of personal interest and have a cursory understanding of Hamming Codes. From what I can tell, they're designed to exclusively detect the location of a single ...
0
votes
1answer
102 views

From Orthogonal vectors to Useful Bivector

If we have set of orthogonal vectors (X) can we form a set of orthogonal bivectors from that set? I am trying to find if there is a way to get 'more information' from an orthogonal matrix by some ...
1
vote
1answer
65 views

Understanding an application of Entropy

I'm struggling with the following exercise on entropy. Suppose that your friend Alice chooses a number $X$ uniformly at random from $[1,n]$, which she writes down using $\log n$ bits; you can assume ...
0
votes
0answers
90 views

Random Codebook Generation

I do generate a random codebook $\mathcal{C}$ by generating $2^{NC}$ codewords $X^N=[X_1\;X_2\;\cdots\;X_N]$ randomly and independently, each according to some distribution $p_{X^n}(x^n)=\Pi_{i=1}^n ...
0
votes
1answer
60 views

Relation between independence number and channel capacity

Suppose $P_{Y|X}$ is a discrete memoryless channel with confusability graph $G$ and capacity $C = max_{P_X}I(X; Y )$. I want to prove the following relation: $\log{\alpha(G)}\le C$ where $\alpha(G)$ ...