This tag is for [Entropy](http://en.wikipedia.org/wiki/Entropy_(information_theory)) in Mathematics.

learn more… | top users | synonyms

22
votes
2answers
1k views

An information theory inequality which relates to Shannon Entropy

For $a_1,...,a_n,b_1,...,b_n>0,\quad$ define $a:=\sum a_i,\ b:=\sum b_i,\ s:=\sum \sqrt{a_ib_i}$. Is the following inequality true?: $${\frac{\Bigl(\prod a_i^{a_i}\Bigr)^\frac1a}a \cdot \frac{\...
15
votes
4answers
5k views

Is there a “most random” state in Rubik's cube?

Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?
13
votes
5answers
404 views

(Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) \...
10
votes
1answer
4k views

Entropy of a binomial distribution

How do we get the functional form for the entropy of a binomial distribution? Do we use Stirling's approximation? According to Wikipedia, the entropy is $\frac1 2 \log_2 \big( 2\pi e\, np(1-p) \big) + ...
9
votes
2answers
891 views

Can the entropy of a random variable with countably many outcomes be infinite?

Consider a random variable $X$ taking values over $\mathbb{N}$. Let $\mathbb{P}(X = i) = p_i$ for $i \in \mathbb{N}$. The entropy of $X$ is defined by $$H(X) = \sum_i -p_i \log p_i.$$ Is it possible ...
9
votes
3answers
394 views

Does $\operatorname{div}\left(\nabla G +xG\right)=0\Longleftrightarrow \nabla G +xG=0$?

Let $G$ be a smooth function defined on $\textbf{R}^d$. What are the assumptions I should use to assume that $$\operatorname{div}\left(\nabla G(x) +xG(x)\right)=0 \quad (\forall x\in \textbf{R}^d)$$ ...
8
votes
1answer
135 views

Entropy of matrix vector product

Consider a random $n$ by $n$ matrix $A$ whose entries are chosen from $\{0,1\}$ and a random $n$ dimensional vector $x$ whose entries are also chosen from $\{0,1\}$. Assume $n$ is large. What is ...
7
votes
2answers
3k views

How Entropy scales with sample size

For a discrete probability distribution, the entropy is defined as: $$H(p) = \sum_i p(x_i) \log(p(x_i))$$ I'm trying to use the entropy as a measure of how "flat / noisy" vs. "peaked" a distribution ...
7
votes
1answer
223 views

Lemma in Petersen's *Ergodic Theory*

I'm trying to understand the proof of Lemma 6.2.1 (p.260-261) in Petersen's Ergodic Theory. Specifically, I don't understand why $B_{n}^{A} \in \mathscr{B}(T^{-1}\alpha \vee \dots \vee T^{-n}\alpha)$ ...
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 ...
7
votes
0answers
151 views

Approximation of Shannon entropy by trigonometric functions

Define Shannon entropy by $$I(p) = -p \log_2 p$$ Numerical experimentation shows that $\sin(\pi p)^{1-1/e}$ is a good approximation to $I(p) + I(1-p)$ on $[0,1],$ never differing by more than 3.3%. ...
6
votes
3answers
952 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 ...
6
votes
2answers
2k views

Derivation of the maximum entropy distribution

I am reading a book and having trouble following something. The problem is to try to maximize the differential entropy $-\int_{0}^{\infty}p(r)\log p(r)$ under the constraints that $\int_{0}^{\infty}p(...
6
votes
1answer
512 views

Finding a specific sequence of digits in pi

Looking at the pifs project on GitHub and this question on SO has made me curious as to how feasible it is to find a specific sequence of digits within Pi. Essentially, on average, how many digits of ...
6
votes
2answers
2k views

Can I normalize KL-divergence to be $\leq 1$?

The Kullback-Leibler divergence has a strong relationship with mutual information, and mutual information has a number of normalized variants. Is there some similar, entropy-like value that I can use ...
6
votes
1answer
332 views

Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
6
votes
0answers
59 views

At what rate does the entropy of shuffled cards converge?

Consider a somewhat primitive method of shuffling a stack of $n$ cards: In every step, take the top card and insert it at a uniformly randomly selected one of the $n$ possible positions above, between ...
5
votes
3answers
2k views

Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$

I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough. My approach was ...
5
votes
2answers
5k views

Entropy of matrix

I am trying to understand entropy. From what I know we can get the entropy of a variable lets say X. What i dont understand is how to calculate the entropy of a matrix say m*n. I thought if columns ...
5
votes
1answer
97 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 https://en.wikipedia.org/wiki/...
5
votes
2answers
108 views

Are there logarithm functions for arbitrary rings?

The logarithm function for $\mathbb{R}$ satisfies $\log xy = \log x + \log y$ whenever both $\log x$ and $\log y$ are defined. Are their conditions for a ring $R$ which guarantee the existence of a ...
5
votes
1answer
353 views

Definition of the Entropy

I have a question regarding definition of entropy by expected value of the random variable $\log \frac{1}{p(X)}$: $H(X) = E \log \frac{1}{p(X)}$, where $X$ is drawn accordingly to the probability ...
5
votes
1answer
423 views

Pinsker $\sigma$ Algebra

Let $(X,A,\nu)$ be a probability space and $T:X\to X$ a measure-preserving transformation. The Pinsker sigma algebra is defined as the lower sigma algebra that contains all partition P of measurable ...
5
votes
1answer
184 views

Is there a possibility to determine/ estimate the topological entropy?

By $E$, denote the set of excited states $E=\left\{1,2,\ldots,e\right\}$ and by $R$ the set of refractory states $R=\left\{e+1,e+2,\ldots,e+r\right\}$. By $0$, denote the equilibrium state. The ...
5
votes
1answer
97 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
222 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 ...
5
votes
1answer
331 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 $$I\left(X,Y\right)\,=\,h\left(X\right)\,-\,h\...
5
votes
1answer
116 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 ...
5
votes
1answer
65 views

Maximum entropy of the sum of two vectors

Consider two identically distributed independent random vectors $X$ and $Y$ of dimension $n$ (assume $n$ is large). Both $X$ and $Y$ have only non-negative integer entries less than or equal to $n$ ...
5
votes
0answers
83 views

Decrease of entropy when iterating a random discrete function

Let $m$ be a positive integer. Let $S$ be the set of non-negative integers $x$ less than $m$, with $|S|=m$. Let $X_0$ be the discrete uniform distribution over $S$, with $P(x)=\begin{cases} 1/m & \...
5
votes
1answer
322 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 \...
4
votes
3answers
250 views

Probability and Entropy

According to the Wikipedia article on conditional entropy, $\sum p(x,y)\log p(x)=\sum p(x)\log p(x)$. Can someone please explain how?
4
votes
1answer
3k views

Correct algorithm for Shannon entropy with R

Shannon entropy is defined by: $H(X) = -\sum_{i} {P(x_i) \log_b P(x_i)}$, where b could be $e$, 2 or 10 (bit, nat, dit, respectively). My interpretation of the formula is: $H(X)$ is equal to the ...
4
votes
2answers
105 views

What is maximum entropy?

What is an intuitive interpretation of the concept of maximum entropy? I'm confused about what it measures, how it does that (roughly), and where one would apply it. Why do we talk of maximum ...
4
votes
2answers
140 views

Proof of recursivity of Shannon's Entropy

Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found? I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , \frac{...
4
votes
1answer
532 views

Does a maximum entropy probability distribution with KL-divergence constraint not exist?

In my earlier question I asked about a technical aspect of solving a system of equations arising from looking for an entropy-maximizing distribution $p(x)$ continuous on $\mathbb{R}$ and constrained ...
4
votes
1answer
723 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 ...
4
votes
1answer
161 views

Definition of entropy of an ergodic measure

I'm reading a paper in which it is stated that The entropy of an ergodic measure is defined as $$\lim_{n \to \infty} -\frac{1}{n} \sum_{|w|=n} \mu[w] \log \mu[w].\tag{1} \label{eq:1}$$ Here ...
4
votes
1answer
248 views

Relative entropy between singular measures

Usually, to define relative entropy between two probability measures, one assumes absolute continuity. Is it possible to extend the usual definition in the non absolutely continuous case?
4
votes
1answer
72 views

Inequality on Shannon's entropy

Let $P$ be a set of probabilities s.t. $\sum_{p_i \in P} p_i = 1$. Moreover, let $H(P)$ the Shannon's entropy of the set of probabilities $P$: $$ H(P) = -\sum_{p_i \in P} p_i \log_2 p_i $$ I define ...
4
votes
1answer
61 views

References for information theoretic statistical tools

Strange statistical concepts like spaces of probability distributions, "metrics" like Fisher information or relative entropy, and convergence with respect to these quantities are necessitated in my ...
4
votes
0answers
30 views

Arnold's combinatorial description of entropy.

V.I. Arnold says that entropy is related to the asymptotic behaviour of polynomial coefficients. This is mentioned in his book "Dynamics, Statistics and Projective Geometry of Galois Fields". Here ...
4
votes
0answers
94 views

A combinatorial problem.

Let be $(X, \mathbb{A}, \mu)$ a measure space, a partition of $ X $ is a disjoint family $\xi=\{P_1,\ldots,P_k \}$ of measurable sets such tath $\bigcup P_i=X\pmod0).$ If $\xi=\{P_1,\ldots,P_k \...
4
votes
1answer
492 views

Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
3
votes
3answers
422 views

Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries ...
3
votes
3answers
1k views

Is Standard Deviation the same as Entropy?

We know that standard deviation (SD) represents the level of dispersion of a distribution. Thus a distribution with only one value (e.g., 1,1,1,1) has SD equals to zero. Similarly, such a distribution ...
3
votes
1answer
283 views

Entropy of geometric random variable with parameter $1/2$

I'm studing for an information theory exam, maybe some of you can help me here with an exercise. What's the entropy of $X$ as $\{1,2,\ldots,n\}$ ($n$=infinity) where the probabilities are $P \{1/2^...
3
votes
3answers
680 views

Relationship between entropy and ergodicity

Are there any direct connections between entropy and ergodicity? For example, does knowing that $(X,\mathcal{S},\mu,T)$ is ergodic help in computing the entropy? I know that there are some indirect ...
3
votes
3answers
259 views

Entropy of convolution of measures

Let $G$ be a countable, discrete group, and let $\mu_1,\mu_2$ be probability measures on the group $G$. We define the entropy of $\mu_i$ as $H(\mu_i)=\sum\limits_{g \in G}-\mu_i(g)\log(\mu_i(g))$ (...
3
votes
1answer
386 views

Parameter estimation for a distribution by minimizing its conditional entropy

Let $X$ be a discrete random variable with Laplacian distribution with mean $0$ and scale $\lambda$, as $$ p(X) = \frac{1}{2\lambda} \exp\left(-\frac{|x|}{2\lambda}\right), \\ X \in \{0,1,...,255\...