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
1answer
247 views

Graph Entropy - What is it?

I am having trouble getting some intuition as to what graph entropy measures. The definition that I have is that given a graph $G$, $H(G) = \min_{X,Y}I(X ;Y)$, where $X$ is a uniformly random vertex ...
3
votes
2answers
167 views

Markov chains for beginners, how to think about them?

So this is what my book states: Random variables $X,Y, and Z$ are said to form a Markov chain in that order denoted $X\rightarrow Y \rightarrow Z$ if and only if: $p(x,y,z)=p(x)p(y|x)p(z|y) $ ...
2
votes
2answers
250 views

Random process, stochastic process explained intuitively?

So I've read the definitions online and this is what I understood. $X(t)$ is a random process for $t>0$ and we can think of it as being a random variable at any given time $t=t_0$. For example, ...
1
vote
1answer
129 views

$I(X;Y;Z)$ and $I(X,Y;Z)$?

Anyone can conceptually explain what the difference is between $I(X;Y;Z)$ and $I(X,Y;Z)$? where $I(X;Y;Z)=I(X;Z)+I(Y;Z/X)$ Basically, what the semicolon and coma mean in mutual information? In ...
1
vote
2answers
285 views

“by definition A and B R.V are independent means that: $p(A∪B)=p(A)+p(B)$ right?” No, absolutely not right.

Can someone please explain why? Isn't $p(a,b)=p(a)*p(b) $ equivalent to $p(A∪B)=p(A)+p(B)$? If not can you please give a counterexample or something? Thanks a lot!
2
votes
1answer
87 views

I.I.D what does this stand for?

So almost everywhere in the book it's written "random variables are IID", what does this mean? I think it means independent and identically distributed but not sure. So by definition A and B R.V are ...
2
votes
1answer
36 views

Error correcting binary partition

Let's say I have a collection of $2^n$ labeled objects, and I want to find one of them. If I can ask yes-no questions about it, binary partition would immediatly lead us to the desired object in $n$ ...
1
vote
1answer
99 views

Is there a way to mathematically describe “surprise”?

Let's say that there are ten people entered into a random drawing, the winner gets some large prize. If I were one of those ten people, and I were to win, then I would be pleasantly surprised. If ...
1
vote
1answer
37 views

Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$

Let $X,Y, and \space Z$ be random variables. Let $A$ be a subset of $U$ such that $p(X \in U)=1$ Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$ Do these two expressions represent the same thing? ...
1
vote
1answer
33 views

Show that entropy $(p1,…,pi,…,pj,…,pm)$, < entropy $(p1,…, (pi+pj)/2 ,…, (pi+pj)/2 ,…,pm)$.

Show that the entropy of the probability distribution, $(p1,...,pi,...,pj,...,pm)$, is less than the entropy of the distribution $(p1,..., (pi+pj)/2 ,..., (pi+pj)/2 ,...,pm)$. I don't understand what ...
2
votes
1answer
93 views

Notion of Relative Entropy

I do not understand the notion of relative entropy. Relative Entropy. $D_{KL}(P||Q) = \sum_{i}^{}P(i)\log \frac{P(i)}{Q(i)}$. I try to get some intuition why it looks the way it looks. I see that it ...
5
votes
0answers
115 views

A tight lower bound for the entropy of the XOR of two random variables

Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings. Assuming $I(X;U) \le ...
0
votes
0answers
72 views

Average min-entropy and statistical distance

Let $X$ be a random variable over a set $\mathcal{X}$. The min-entropy of $X$ is defined as $$ H_{\infty}(X) := -\log(\max_x \mathbb{P}_{x\leftarrow X}[X=x]). $$ For a pair of (possibly correlated) ...
5
votes
1answer
126 views

Card drawing algorithm

I want to know whether there is an algorithm for randomly and securely drawing cards from a deck. I was thinking about a way to play deck-based games online with no trusted party and no way to cheat. ...
1
vote
1answer
300 views

Maximum entropy joint distribution from marginals?

How does one find the maximum entropy joint distribution of two random variables X and Y given their marginal probability mass functions? I know: I have the marginals, meaning p(x) and p(y) are ...
1
vote
1answer
383 views

Is maximizing entropy equivalent to minimizing the defined variance?

Assume there is multi-set of some integers : $D = \{a_1,a_2,\cdots,a_{N-1}\}$ such that $\sum_i a_i = A$ we can build a discrete probability distribution by dividing elements of set by $A$, i.e. $p_i ...
0
votes
1answer
75 views

How much information do you get if you draw a red card?

I'm trying to figure out what this question is asking and what it is I'm trying to calculate exactly. I'm told: You have cards 2-5 of each suit, except the 2 and 3 of the red cards. So 12 cards ...
1
vote
1answer
97 views

Is mutual information transitive?

Suppose A, B and C are random variables. Given that the mutual information between A and B is very large and also the mutual information between B and C is very large, could we conclude that the ...
2
votes
1answer
83 views

Transformation of mutual information to probability distribution

Given the upper bound for mutual information of random variables $X$ and $Y$, $I(X;Y)\leq L$, what can we say about their joint distribution? I mean for example if $L=0$, then we know $p_{XY}(A\cap ...
1
vote
0answers
124 views

KL divergence of multinomial distribution

Consider $q(x)$ be a Multinomial distribution over $\{1, \ldots, k\}$ with parameters $\{\theta_1,\ldots, \theta_k\}$. And p(x) over $\{1,\ldots, k\}$ with distribution $p(x)=\frac{1}{k}$. Then what ...
0
votes
1answer
131 views

confused about joint mutual information

I have a difficulty understanding 'joint mutual information' The expressions like $I(X,Y;B)$ are not understood. Is there an good example to understand joint mutual information? Actually, I want to ...
0
votes
0answers
18 views

Applications of dissimilarity measures

A dissimilarity measure of two probability measures $p$ and $q$ is defined as a non negative function $D(p,q)$ which is $0$ iff $p=q$ a.s. The KL divergence is an example of such a function. There are ...
6
votes
3answers
262 views

What is information theoretic entropy and its physical significance?

I have learned entropy in my information theory classes. The definition I got from text books was the average information content in a message sequence etc. But in one of the MIT videos related to ...
2
votes
2answers
107 views

Understanding notation difference between mutual information and information divergance

The mutual information is defined on random variables. That is, $I(X;Y)$ denotes the mutual information between random variables $X$ and $Y$. On the other hand, the the Kullback-Leibler divergence is ...
1
vote
0answers
38 views

Calculating entropy of Naive Bayes random variables

Suppose a Naive Bayes graphical model with binary random variables is given by $$P(y,x_1,x_2,...,x_n)=P(y)P(x_1|y)...P(x_n|y)$$ Attempting to calculate $I(x_1,...,x_n;y)$ raises the question: how can ...
2
votes
0answers
122 views

Joint distribution between a uniform random variable and a function which is “almost” independent from it

Motivation Let $f(\cdot)$ be a (possibly randomized) function, such that for any random variable $X$ (taking values from a finite set $D$), $X$ and $f(X)$ are statistically independent. Let $U, U_1, ...
1
vote
1answer
216 views

Is maximizing the Shannon differential entropy equivalent to minimizing the predictability and/or minimizing the maximum density?

For a real-valued, 1-dimensional, continuous random variable X with density f(x), I am trying to determine if maximizing the Shannon differential entropy of f(x) is mathematically equivalent to ...
2
votes
2answers
182 views

Is alpha divergence a convex divergence measure?

Alpha divergence is defined as following : $$ D_\alpha(p||q) = \frac{1}{\alpha (1-\alpha)} \left( 1- \int _x p(x)^{\alpha} q(x)^{(1-\alpha)} dx \right) $$ if the distributions are restricted to ...
0
votes
1answer
173 views

Information theory entropy equation

I'm studying information theory, and working through this document. On page 17, it shows that, with the function that gets the entropy of a probability $I$ and a probability $p$, that $I(p^a) = a * ...
1
vote
1answer
117 views

Shrink a Chain of Decimal Digits

Assume that we have a 100-digit number, made of 0 to 9. Is there a way we can actually 'shrink' this number? As a first thought, I tried to decompose the number to prime factors. But, in many cases, ...
0
votes
1answer
26 views

Bound on maximum of a fourier transform

Could someone show me why the following relation holds? $ \max_{\lambda} \vert f(\lambda)\vert \leq \sum_{-m}^m\vert t_k\vert $ where $ f(\lambda) $ is the fourier transform of the sequence $ ...
2
votes
0answers
138 views

Non-zero Conditional Differential Entropy between a random variable and a function of it

Let two continuous random variables, where the one is a function of the other: $X\, $ and $\, Y=g\left(X\right)$. Their mutual information is defined as ...
2
votes
1answer
74 views

Entropy and Shearer's Inequality

I have two questions both related to Shearer's Inequality: 1) When is equality attained in Shearer's Inequality? One trivial instance is when the random variables are all independent. Is this the ...
1
vote
0answers
66 views

Maximum of the expectation of a concave function

Let's have a function $f(x, \theta)$, and some probability distribution on $x$. Let's say I have found $\theta^* = \operatorname{argmax}(f(E[x], \theta) $, and $f$ is concave in $x$. I would like to ...
1
vote
0answers
35 views

Hiking trip distribution

I have a real life problem. My friends and I are going on a hiking trip and there's a bunch of items (mostly food) that we want to distribute among us so everyone carries approximately equal weight. ...
3
votes
0answers
107 views

Reference for a transformation

Has the (Lebesgue-)ergodic transformation $T: \{0,1\}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}}$ defined by $T(x(0)x(1)x(2)\cdots) = x(1)x(3)x(5)\cdots$ been well-studied? If so, where? Does it have a ...
1
vote
0answers
79 views

Entropy Rate of a sequence of Random Variables with Distributions related to Primes

Let us consider a stochastic process $\mathcal{X}=\{X_i\}_{i \in \mathbb{N} }$ where $X_i$'s are independent and $X_i$ is distributed as $$X_i=p_k \ \mbox{w. p.}\frac{p_k}{\sum_{l=1}^{i}p_l},\ 1\leq ...
3
votes
1answer
132 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 ...
0
votes
1answer
93 views

questions in channel capacity

Q) Suppose we have a set of t coins, all but two of which have uniform weight $0$. and two counterfeit coins have different weights$>0$. If one can only use a spring scale, what is the ...
1
vote
1answer
55 views

approximate $[0, 1]$ continuous function with 2d basis.

everyone. I've been thinking of this problem when reading papers about Fourier series. I think I can state my question as follows: in the interval $[0, 1]$, I want to approximate an unknown ...
6
votes
1answer
230 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
3
votes
2answers
256 views

Intuition of information theory

I am reading the book "Elements of Information Theory" by Cover and Thomas and I am having trouble understanding conceptually the various ideas. For example, I know that $H(X)$ can be interpreted as ...
2
votes
0answers
107 views

Lower bound on uncertainty reduction

Let $T$ be a set of tuples such that each score tuple $s(t_i)$, $t_i \in T$ is uncertain (i.e., not known deterministically). The score $s(t_i)$ can be represented as a uniform probability density ...
0
votes
1answer
50 views

Optimization of entropy for fixed distance to uniform

Suppose that I know that a probability distribution with $n$ outcomes is very close to being uniform (that is: $\forall i,p_i=\frac{1}{n}$), and in particular for $n\epsilon\ll 1$ the distribution ...
3
votes
1answer
118 views

Source coding theorem - optimum number of bits?

The source coding theorem says that information transfer with variable length code uses less bits and is equal to the entropy of the distribution. It also says that there is no code that uses lesser ...
0
votes
1answer
109 views

concatenation of channels

Assuming I have 2 channels: BSC => Z Z=> BSC the first channel is a concatenation of the BSC channel and then the Z channel. the second channel is a concatenation of the Z channel and then the BSC ...
2
votes
1answer
89 views

Properties of Entropy

When someone writes $H(X_1, X_2, X_3) = H(X_1) + H(X_2\mid X_1) + H(X_3\mid X_2, X_1)$, how should that last term be interpreted/read? As the joint entropy between 2 variables where variable 1 is ...
3
votes
0answers
53 views

Is there a conditional version of the asymptotic equipartition property?

Let $X_i$ be independent random variables with $\operatorname{Pr}(X_i = x) = p_x$, and let $F_n$ be the empirical frequency distribution of $X_1, \ldots, X_n$: that is, $(F_n)_x$ For any frequency ...
2
votes
1answer
77 views

Conditional Probability, Lack of Dependence on a Parameter

I am trying to understand why the following is true: $$ p(f(Y) = f(y) \mid Y = y) = p(f(Y) = f(y) \mid X = x, Y = y) \qquad \ldots \text{(Eq. 1)} $$ where $Y$ and $X$ are random variables, and $f(Y)$ ...
6
votes
3answers
305 views

Another Information Theory Riddle

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. In a magic trick, there are ...