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

learn more… | top users | synonyms

1
vote
1answer
94 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
632 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
148 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
81 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
89 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
273 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
203 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
150 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
246 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
375 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
86 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
211 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
74 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
275 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
87 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
191 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?
5
votes
1answer
180 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
109 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
119 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
97 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
146 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
86 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
95 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
139 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
307 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
227 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
797 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
218 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
250 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
221 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
995 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 ...