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 ...
10
votes
3answers
2k 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?
9
votes
1answer
2k 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) + ...
7
votes
2answers
367 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 ...
7
votes
0answers
219 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 ...
6
votes
3answers
333 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
1answer
194 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)$ ...
6
votes
0answers
104 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%. ...
5
votes
3answers
835 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
2k 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
156 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 ...
5
votes
1answer
280 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
54 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
163 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
70 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 ...
5
votes
0answers
65 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
0answers
58 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
167 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
188 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 ...
4
votes
3answers
205 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
2answers
1k 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 ...
4
votes
2answers
89 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 ...
4
votes
1answer
227 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 ...
4
votes
1answer
130 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
2answers
939 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 ...
4
votes
1answer
56 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
0answers
87 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 ...
3
votes
3answers
587 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
255 views

Entropy of $X =\{1,2,\ldots,\infty\}$ with the probability of $\{1/2^1,1/2^2,\ldots,1/2^\infty\}$?

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^1, ...
3
votes
3answers
352 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
106 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
2answers
55 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} , ...
3
votes
1answer
42 views

Do the pth powers of $p$-norms define the same partial ordering on the set of all probability distributions for all $p>1$?

Consider the $p$-th power of the Schatten $p$-norm $||q||_p$ of a probability distribution $q$ , ie, the function $\sum_j q_j^p$, where $\sum_j q_j = 1$ and $q_j \geq 0$. For fixed $q$ and $p>1$ ...
3
votes
1answer
334 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 ...
3
votes
1answer
68 views

Topological Entropy of $(x,y)\mapsto(x+y,x+a)$

Let $a\in \mathbb T^1$, how can I calculate the topological entropies of the maps $T_1:(x,y)\mapsto(x+y,x+a)$ and $T_2 : (x,y) \mapsto (x+y,y+a)$ defined on $\mathbb T^2$. Here $\mathbb T^n$ is the ...
3
votes
1answer
60 views

How to consider gravity as an entropic force?

Is it possible to consider gravity as an entropic force? What is mathematical relation between second law of thermodynamics and newton law of gravity?
3
votes
2answers
704 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 ...
3
votes
1answer
122 views

convergence of entropy and sigma-fields

This question is related to this one. Let $(X_1, X_2, \ldots)$ be a sequence of random variables such that each $X_n$ takes its values in a finite space, say $\{0,1\}$, and the $\sigma$-field ...
3
votes
2answers
116 views

Calculate entropy with n values

I trying to solve a quiz that asks the following. The variable $X$ can be the values $1,2,3,...,n$ with the probabilities $\frac{1}{2^1}, \frac{1}{2^2},\frac{1}{2^3},...,\frac{1}{2^n}$ How can I ...
3
votes
1answer
155 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
3
votes
1answer
88 views

Is $H(X)<E(X)$ for natural $X$?

For an RV $X$ with values on $\{1,2,\ldots\}$, I need to prove that the entropy is less than the EV: $H(X)\leq E(X)$ . I tried to bound the log but I'm not quite there. Appreciate any hint... Thanks
3
votes
2answers
67 views

Understanding conditional entropy intuitively $H[Y|X=x]$ vs $H[Y|X]$

I was trying to understand conditional entropy better. The part that was confusing me exactly was the difference between $H[Y|X=x]$ vs $H[Y|X]$. $E[Y|X=x]$ makes some sense to me intuitively because ...
3
votes
1answer
164 views

What does SVD Entropy Capture?

Looking at different definitions and types of Entropy, I run into the concept of SVD Entropy, which is defined as explained below. What is the intuition behind the SVD spectrum? What do different ...
3
votes
1answer
146 views

Question about entropy

Let $(X,A,\nu)$ be a probability space and $T\colon X\to X$ a measure preserving transformation $\nu$. Take a measurable partition $P=\{P_0,\dots,P_{k-1}\}$. Let$I$ be a set of all possible ...
3
votes
1answer
167 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?
3
votes
0answers
71 views

Huffman codes: does less entropy imply less weighted average codeword length?

Let $\Sigma$ be a source alphabet with a probability distribution over its symbols $P$. Then, the Shannon entropy of $\Sigma$ is $$-\sum p_j \times -\mbox{log}_2(p_j)$$ where $p_j$ is the probability ...
3
votes
0answers
73 views

Topological applications of topological entropy

I just learned topological entropy during a lecture about dynamical systems, and I wonder whether there exist purely topological applications of it.
3
votes
0answers
115 views

Can one define informational content of a mathematical expression?

At least in physicist's thinking, information, vaguely, is something that allows one to select a subset from a set. Say, a system can be in states A and B, we have done a measurement on it ...
3
votes
0answers
161 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 ...
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 ...