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

learn more… | top users | synonyms

3
votes
1answer
41 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$ ...
0
votes
1answer
51 views

i.i.d binary random variable question

Suppose there are i.i.d. binary random variables $X_i \sim X$ with distribution $P(X=1) = 0.75$ and $P(X=0) = 0.25$ i) For $n=5$ and $e=0.1$, which sequences fall in the typical set $A_e^n$? What is ...
1
vote
0answers
91 views

Why is the negative entropy Lipschitz with respect to the $1$-norm (Over)?

Let $\left\|x \right\| = \sum_{i=1}^{i=n}\left|x^i\right|$ and $d\left(x\right)=\sum_{i=1}^{i=n}x^i\ln x^i$ where $x\in R^n $ and $ \sum_{i=1}^{i=n}x^i=1$ How to prove: For all $x, x'$, $$\left| ...
0
votes
1answer
198 views

Approximating probability of success of Bernoulli trials using Kullback–Leibler divergence

In "Probabilistic Graphical Models" book by Daphne Koller and Nir Friedman they have the following approximation of probability of r successful outcomes of N Bernoulli trials: $P(S_N=r)\approx ...
3
votes
1answer
215 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 ...
1
vote
1answer
207 views

Bits in a coin-toss experiment

This is not homework but an actual problem. We flip a fair coin ten times. This gives A$_1$ to A$_{10}$. Each coin toss = 10 bits. We flip another fair coin ten times. This gives B$_1$ to ...
0
votes
1answer
202 views

Entropy Problem: mutual information

I have a problem about entropy and mutual information that I have attempted, but would like feedback on. 30% Boas 20% Anaconda 50% Cobra Half of the Cobras were medium sized, and the other half were ...
1
vote
1answer
78 views

About the differential entropies of well-known continuous distributions

Assume that the continuous random variable $X$ has a distribution (in a closed form expression) with differential entropy $h(X)$. Q) Then, is it true for any continuous distribution that the ...
1
vote
2answers
266 views

How to prove the following entropy formula?

Could anyone show me a proof or redirect to a source where the following entropy equation is proved? =) $$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$ Thank you!
3
votes
1answer
121 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
114 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 ...
7
votes
2answers
317 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 ...
0
votes
1answer
643 views

equivalence between uniform and normal distribution

The principle of insufficient reason says that all outcomes are equiprobable when we have no knowledge to guess otherwise. I understand this and that this corresponds to uniform distribution. However, ...
5
votes
1answer
266 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 ...
3
votes
1answer
144 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 ...
6
votes
0answers
99 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%. ...
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) + ...
2
votes
1answer
65 views

What is the CONCEPT when we speak of maximum entropy?

What is an intuitive interpretation of the concept of maximum entropy? I want to understand this concept better but what I'm finding is too "advanced" right now. Can anyone simplify it ... imagine I'm ...
1
vote
1answer
153 views

Increasing entropy of random walk in regular graph

Let $P$ be a transition matrix of a random walk in an undirected regular graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
1
vote
1answer
25 views

Entropy contribution from variable length segment of a sequence

If I have a sequence which is comprised of one of 10 prefixes, one of 5 suffixes and a variable length middle, how do I compute the entropy of the sequence? Using Shannon-Entropy $Hs= ...
0
votes
1answer
197 views

Entropy of a Binary Source with a random until first other result is given.

I was studying for an exam and i found an interesting exercise, but very very bad redacted. A coin is thrown until the first face is found. Denote as X the number of throws required. And find: a) ...
1
vote
0answers
196 views

Mutual Information of Correlated Bivariate Uniform Distribution

We have correlated bivariate uniform distribution, where X and Y have a correlation coefficient $\rho$ and they uniformly distributed in the following rectangle. What is the mutual information of $X$ ...
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 ...
2
votes
1answer
54 views

Parameter optimization in probabilistic models

Task: Suppose we model a variable $y = Wx + \mu$ as a linear transformation of $x$ plus some Gaussian noise $\mu\sim\mathcal N(0,\sigma I)$. Our aim is to minimize the estimation error of $x$ given ...
0
votes
2answers
177 views

Prove that entropy is maximized when probability is $1/n$

How can be proven that the entropy of a dice roll is maximized when the probability of each of its $6$ faces is equal, $1/6$?
3
votes
1answer
151 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 ...
0
votes
1answer
665 views

Kullback-Leibler distance between 2 probability distributions

Can I determine the Kullback-Leibler distance $$ D_{\mathrm{KL}}(P\parallel Q)=\sum_{i}\ln\left(\frac{P(i)}{Q(i)}\right) P(i) $$ between the following probability distributions? ...
1
vote
1answer
87 views

Conditional entropy of sum of random variables

How can be proven that for random variables $A$ and $B$, and $C = A + B$, $$H(C\mid A) = H(B\mid A).$$ Also, would it be possible to determine if $H(C)$ would be greater than $H(A)$?
1
vote
1answer
97 views

What branch of the Math can help me with this?

I would love to focus on the branches of the Math that can help me with: generation of entropy, i suppose that most of the works are based on statistic since even a big part of the cryptographic ...
5
votes
2answers
721 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 ...
1
vote
1answer
165 views

Entropy of Zipf and Zeta Distributions

I was wondering how to show entropy of the zeta distribution. It is: $$ H_\mathrm{zeta}(X) = \sum_{k=1}^\infty \frac{1/k^s}{\zeta(s)} \log(k^s \zeta(s))$$ The entropy of the zipf distribution is: ...
1
vote
2answers
1k views

How are Huffman encoding and entropy related?

The inherent unpredictability, or randomness, of a probability distribution can be measured by the extent to which it is possible to compress data drawn from that distribution. $$ \text{more ...
0
votes
1answer
84 views

Checking efficiency of randomness with entropy

I was going through random numbers and found that the randomness of certain observations is measured by the entropy as given in here. Here, $p(x_i)$ is the probability that $x_i$ will take place. But ...
1
vote
1answer
97 views

Entropy of Order Statistic

Consider $n$ independent and identically distributed random variables $ \{X_i\}_{i=1,...n} $ with support on some interval $[a,b]$ and its $n$'th order statistic $\max_{i \in \{1,...n\}} X_i$ . The ...
3
votes
1answer
313 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} ...
1
vote
0answers
225 views

How can I determine the upper limit of Shannon Entropy?

I know that the maximum possible Shannon Entropy for an alphabet $X$ is $\log|X|$, where Shannon Entropy is: $$H(X) = - \sum_{x \in X} \; p(x) \log p(x)$$ but how is this upper limit computed?
1
vote
2answers
1k views

Calculating conditional entropy given two random variables

I have been reading a bit about conditional entropy, joint entropy, etc but I found this: $H(X|Y,Z)$ which seems to imply the entropy associated to $X$ given $Y$ and $Z$ (although I'm not sure how to ...
2
votes
0answers
158 views

rényi entropy as a derivative

Let $x=(x_i)$ be a probability measure on $\{1,\ldots,n\}$. Suppose $1<p<\infty$. The Rényi entropy of $x$ is $$ H^p(x)=\frac{1}{1-p}\log \sum_{i} x_i^p. $$ Does there exist a formula for ...
1
vote
1answer
264 views

Explicit examples of smooth entropy computation

Smooth classic entropies generalize the standard notions of entropy. This smoothing stands for a minimization/maximization over all events $\Omega$ such that $p(\Omega)\geq 1-\varepsilon$ for a given ...
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?
1
vote
3answers
437 views

Minimum number of bits required to store the order of a deck of cards

Assume I have a shuffled deck of cards (52 cards, all normal, no jokers) I'd like to record the order in my computer in such a way that the ordering requires the least bits (I'm not counting look up ...
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
2
votes
1answer
227 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 ...
1
vote
0answers
118 views

Incrementally compute the conditional entropy

Is it possible to compute a conditional entropy (see the two following formulas) in an incremental manner ? That is, the sets C and K are not fix: each time we have a new element c, set K may increase ...
0
votes
0answers
77 views

entropy of perfect cryptosystems

I am working on the product of two perfect crypto-systems and I need to prove that the product is secure. $$a -- [\text{system}\ 1] -- b -- [\text{system}\ 2] -- c$$ How can I prove that $H(a) = ...
1
vote
0answers
302 views

Is conditional entropy a convex function?

A conditional entropy can be expressed in the following way, $H_{V_t}(V_s) = -\sum_{s,t}p(s,t)\log{p_t(s)} = -\sum_{s,t}p(s,t)\log{\frac{p(s,t)}{\sum_{s'}{p(s',t)}}}$ $s$ and $t$ are defined ...
0
votes
1answer
90 views

How to compute Shannon information?

Given a string of random symbols with yet a priori unknown distribution, what are the known algorithms to compute its Shannon entropy? $$H = - \sum_i \; p_i \log p_i$$ Is there an algorithm to ...
4
votes
3answers
202 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?
6
votes
1answer
186 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)$ ...
1
vote
1answer
120 views

Question about Mutual Information

I am learning about mutual information, and am confused about one of the definitions. Mutual information is defined as $ I(X;Y) = H(X) - H(X | Y) $ where, $$ H(X) = \sum_{x} p(x) \log ...