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

learn more… | top users | synonyms

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
230 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
205 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
182 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
157 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
723 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
92 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
101 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
3answers
867 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
195 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
100 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
330 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
238 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
162 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
284 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
490 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
239 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
119 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
79 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
327 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
92 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
208 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
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)$ ...
1
vote
1answer
125 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 ...
4
votes
1answer
134 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 ...
1
vote
0answers
119 views

Entropy of a Finite State Transducer

Theorem 7 in Shannon's seminal paper A Mathematical Theory of Communication states: "The output of a finite state transducer driven by a finite state statistical source is a finite state ...
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?
1
vote
1answer
89 views

Upper bound for $-t \log t$

While reading Csiszár & Körner's "Information Theory: Coding Theorems for Discrete Memoryless Systems", I came across the following argument: Since $f(t) \triangleq -t\log t$ is concave and ...
0
votes
1answer
104 views

Test for randomness

I'm trying to write a program to compute a metric for the entropy in files to determine a probability that the file is compressed or encrypted. Compressed and encrypted files have very, very, very ...
1
vote
0answers
79 views

Showing that Normalized Redundancy is nonreliant on the properties of Bijection and Monotonicity

In information theory, the concept of mutual information states that for two features of arbitrary discretized probability, the following formula holds true: \begin{aligned} I(X;Y) = \sum_{y \in Y} ...
1
vote
0answers
141 views

Inequality involving KL divergence

Following is a part of an answer which was not resolved when I tried to answer a question in mathoverflow. I thought it would be nice to discuss that here. Let $P$ and $Q$ be two distinct ...
3
votes
1answer
340 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
0answers
271 views

Can I map entropy values to a common range so that they are comparable?

I am using the standard Shannon entropy formula for calculating the entropy of a system at different states. The system has a different number of possible outcomes at each state, in other words the ...
4
votes
2answers
968 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 ...
1
vote
1answer
239 views

How do I go about calculating the entropy level of this algorithm?

I have a set of items. These items are (pseudo)randomly placed into buckets. The buckets are ordered and items placed in them are ordered. After all of the items are placed in buckets, the items ...
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, ...
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 ...
0
votes
1answer
254 views

Relative Entropy given two non-equivalent sets

I am trying to calculate the relative entropy given two collections and have a question regarding some issues. Supposed we have two sets, $Real$ and $Calculated$, and their respective probability ...
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 ...