The entropy tag has no wiki summary.
0
votes
1answer
62 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
54 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
163 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
95 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?
0
votes
2answers
432 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
115 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 ...
0
votes
0answers
25 views
Entropy of 2-spikes Distribution
The Entropy of the following distribution is $ - \infty $
$
p(x) = \frac{\delta(x=-1) + \delta(x=1)}{2}
$
Mathematically the reason is because of having a $ - \infty \over 2 $ density probability ...
1
vote
1answer
161 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 ...
8
votes
3answers
577 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
173 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
1
vote
0answers
99 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 ...
-2
votes
1answer
128 views
cardinality of subset and entropy [closed]
(edited)
I am considering the problem about the cardinality of a proper subset, $A\subset\{0,1\}^d$ where $d$ is an integer. Of course, $|A|<2^d$. I am wondering if there is a tighter bound for it. ...
1
vote
0answers
87 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
59 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
158 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
75 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 ...
3
votes
3answers
128 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
141 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
72 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 ...
2
votes
1answer
81 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
72 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 ...
2
votes
1answer
105 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
80 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
69 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
72 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
127 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
205 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
123 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 ...
3
votes
2answers
437 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
174 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
208 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, ...
20
votes
2answers
972 views
I'm not sure about this inequality (how to prove or disprove it?)
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
160 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 ...
2
votes
2answers
496 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 ...
