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

learn more… | top users | synonyms

4
votes
0answers
31 views

Arnold's combinatorial description of entropy.

V.I. Arnold says that entropy is related to the asymptotic behaviour of polynomial coefficients. This is mentioned in his book "Dynamics, Statistics and Projective Geometry of Galois Fields". Here ...
0
votes
0answers
38 views

Lower Bounding postive fractions-Mutual Information

EDIT: Let $X,Y$ be random variables over some probability space with joint distribution $P$. Then the mutual information between two random variables is defined as $I(X;Y):=\sum\limits_{(x,y)\in\...
2
votes
1answer
117 views

What are differences and relationship between shannon entropy and fisher information?

When I first got into information theory, information was measured or based on shannon entropy or in other words, most books I read before were talked about shannon entropy. Today someone told me ...
3
votes
1answer
58 views

Computation of a sum using Stirling's approximation and Watson's lemma

$$Ω=\sum_{n=0}^{N-\frac{E}{\epsilon}} \frac{Ν!}{\left(\frac{N-n-\frac{E}{\epsilon}}{2}\right)!\left(\frac{N-n+\frac{E}{\epsilon}}{2}\right)!n!}$$ I am supposed to calculate the above sum using first ...
1
vote
1answer
37 views

Specific conditional entropy $H(X|Y=y)$ is not bounded by $H(X)$?

Suppose that $P(Y=y)>0$ so that $$ H(X|Y=y)=-\sum_{x} p(x|y) \log_{2} p(x|y) $$ makes sense. I've assumed for a long time that $H(X|Y=y)\le H(X)$, but then it seems that the wiki article claims ...
1
vote
0answers
79 views

Mutual information of independent fair binary random variables

Let random variables $X,Y$ independent fair random variables that take the values 0 and 1 with equal probability and $Z=X+Y$. So, $I(X;Y)=0$ and I am trying to find their conditional mutual ...
0
votes
1answer
20 views

Binary symmetric channel

Binary symmetric matrix A sends $i,j$ and B gets $i,j$. Does it mean that $A$ != $B$? I would know how to solve this if A would be equal to B, but now I'm not sure how should I start, when A has 2 ...
1
vote
1answer
59 views

Finding entropy with two unknown probabilities, and maximizing it

$$S = \{ X, Y, Z, W\};\\P(X) = 0.1;\\P(Y) = 0.5;\\P(Z) = p;\\P(W) = q$$ I don't know how to find source (S) entropy with these 2 unknown $p$ and $q$ probabilities. With which $p$ and $ q$ values ...
0
votes
0answers
25 views

I choose $n$ words from $k$ randoms words from a dictionary with $t$ words. How much entropy is this password?

Let's say I have a dictionary of $t$ words. I randomly select a set of $k<t$ words (no duplicates). Next, I deterministically choose $n<k$ words from those $k$ words (say, pick the first $n$ ...
0
votes
0answers
23 views

Correlation and entropy between stocks of the same index

My portofolio contains the stocks belonging to Nasdaq100 index. Initially, i found the entropy of closing prices between Friday's value and Monday's value,for all companies of the index, in order to ...
1
vote
0answers
39 views

Asymptotic binomial ratios

I am in need of asymptotic version of $$\frac{ \displaystyle \binom{n^{1-s}}{n^s}}{\displaystyle \binom{n}{n^{s}}}$$ where $n\in\Bbb N$ and $s\in\big(0,\frac12\big)$ and $$\displaystyle \frac{ \...
1
vote
1answer
59 views

compute H(X|Y) ( conditional probablity)

Can someone help me on this? X = {$X_1,X_2,X_3,X_4$} Y = {$Y_1,Y_2,Y_3,Y_4$} Suppose p($X_i$) = p($Y_j$) = 1/4 (each X and each Y equally likely) $1 \leq i, 4 \ge j$ and now suppose $Y_1 : X_1 ...
0
votes
1answer
12 views

definition of conditional probability $(p_i|\pi_k)$ and Tsallis entropy

Let $\Omega$ be a set of $W$ possible outcomes of an experiment with probability assignments $p_i$ and thus $\sum_{i=1}^{W}p_i=1$. Now, let's divide $\Omega$ into $K$ non-intersecting subsets each ...
0
votes
1answer
39 views

Proof of chain rule for entropy of random variables

I have the following proof for the chain rule for entropy of random variables: We write: \begin{eqnarray*} H(X_1,X_2,...,X_n)&=&-\sum\limits_{x_1,x_2,...,x_n}p(x_1,x_2,...,x_n)logp(x_1,x_2,......
1
vote
0answers
33 views

Mutual information between 2 sequences of random variables?

How would I go about expanding $I(X_1,...,X_n;Y_1,...,Y_n)$? The chain rule exists for a single case, i.e.: $I(X_1,...,X_n;Y)=\sum^n_{i=1} I(X_i;Y|X_{i-1},...,X_1)$, but I'm having doubts if this can ...
2
votes
0answers
37 views

How to evaluate the quality of the probability distribution output of a classifier?

In a classification problem, I have trained a neural network which outputs class probabilities for a given input. For a new input, I now want to evaluate the "quality" of the neural network's ...
2
votes
1answer
52 views

Proof of Central Limit Theorem via MaxEnt principle

Let $X_i$'s be i.i.d. with mean $0$ and variance $\sigma^2$. After reading Jaynes' book: Probability the Logic of Science, I decided to try out and actually prove CLT via the following steps: a) ...
2
votes
2answers
107 views

Is it possible to code with less bits than calculated by Shannon's source coding theorem?

In information theory, Shannon's source coding theorem establishes the limits to possible data compression, and the operational meaning of the Shannon entropy. Consider that we have data generated by ...
0
votes
1answer
45 views

Conditional joint information of two random variables $X,Y$ given $Z$

For 3 random variables I am trying to prove the following: \begin{eqnarray*} I(X;Y|Z)&\triangleq& H(X|Z)-H(X|Y,Z)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (1) \\&=&E_{p(x,y,z)}\bigg[log_2\frac{...
0
votes
0answers
26 views

Binary Symmetric Channel with Feedback

Suppose that feedback is used on a binary symmetric channel with parameter p. Each time a Y is received, it becomes the next transmission. Thus $X_1$ is Bern(1/2), $X_2$ = $Y_1$; $X_3$ = $Y_2$,..., $...
0
votes
0answers
36 views

mutual information entropy problem

In mutual information we have: if $x$ and $y$ are independent then $p(x,y)=p(x)p(y)$ and then $I(X;Y)=0$. Do If $I (X;Y) = 0$ when $x$ and $y$ are not necessarily independent?
0
votes
1answer
33 views

Estimate password entropy by “trying out” passwords

The entropy of a password of a fixed length $n$ and $c$ possible characters is calculated by $n*log_2(c)= log_2(c^n)$, see also here: https://ritcyberselfdefense.wordpress.com/2011/09/24/how-to-...
1
vote
1answer
163 views

Is entropy of prime numbers smaller?

Seems that entropy (in information theory) can be expressed as a measure of how unpredictable is each bit of information. I have done a little experiment: I've measured entropy of the binary ...
0
votes
0answers
50 views

Conditional joint entropy of two random variables

I am trying to prove the formula that gives the joint entropy of the random variables $X$ and $Y$ given $Z$ which is: $$H(X,Y|Z) = H(X|Z) + H(Y|X,Z)$$ based on the definition of conditional entropy ...
1
vote
1answer
78 views

Entropy of union of multisets

Assigning a random variable to some multiset: Assume that $S$ is a multiset. We can think of $S$ as independent sampling from some random variable. For instance, $S = \{H, H, T, T, T\}$ can be thought ...
0
votes
0answers
34 views

How can I compare the entropy of two vectors with different sum?

I wanna compare the entropy of two vectors, e.g. [1,2,3] vs [0.2, 0.1, 0.3]. Note that the two vectors have different sum, i.e. 6 and 0.6. Basically I wanna know which vector is more unbalanced. ...
0
votes
0answers
180 views

Jensen's inequality proof

The standard proof for Jensen's inequality using taylor expansion around a point $x_0$ involves using only first 3 terms of the Taylor series till $f^{\prime \prime}(x)$. Why are we able to ignore the ...
2
votes
3answers
287 views

An upper bound of binary entropy

Binary entropy is given by $$H_{\mathrm b}(p) = -p \log_2 p - (1 - p) \log_2 (1 - p), \hspace{6 mm} p \le \frac{1}{2}$$ How can I prove that $$H_{\mathrm b}(p) \le 2 \sqrt{p(1-p)}$$
0
votes
1answer
28 views

Prove entropy theorem

Doing a course of cryptography I have been asked to prove the following: $H(X,Y) = H(Y) +H(X|Y)$. But I simply do not know where to start, so a hint in the right direction would be very much ...
0
votes
0answers
33 views

Open covers and $(n,\varepsilon)$-separating/ spanning sets: proving three inequalities

In Peter Walters' book An Introduction to Ergodic Theory, one can find the following corollary (p. 174 in my edition). At the end of this thread, I tried to prove it. It would be great if you could ...
0
votes
1answer
25 views

Log base change problem, Multivariate Gaussian differential entropy proof

I am working through a proof in this document http://ee.tamu.edu/~georghiades/courses/ftp647/Chapter7.pdf for Theorem 3 (The entropy of a multivariate Gaussian distribution): Let X = (X1, X2, · · ·...
2
votes
0answers
41 views

Is the topological entropy of a continuous map $T\colon X\to X$ zero if $X$ is a finite topological space?

Let $X$ be a finite topological space and $T\colon X\to X$ continuous. As the title already suggests, I am wondering if the topological entropy of $T$, denoted by $h(X,T)$, then is $0$. As far as I ...
1
vote
0answers
22 views

Source coding with 2 distinct distributions and entropies

I'm learning about source coding, and many of the books/resources I've read give examples of the source $X^n$ being defined as a sequence of iid random variables. How about when the sequence is ...
3
votes
0answers
143 views

Very special geometric shape (No name yet?)

I suppose this geometric shape is something very 'special'. I cannot clarify in short about being 'special', but I think this shape stands together with such special shapes like the square and the ...
0
votes
0answers
39 views

a problem involving binary entropy function

let $\alpha<1/2$ such that $2^{H(\alpha)}\le 2^{1-\epsilon}$,when $H$ is binary entropy function. how can i prove that then we have: $2^{n(1-\epsilon)}\ge \sum\limits_{i\le \alpha n } {n \choose ...
3
votes
1answer
92 views

Definition of topological entropy

What the meaning of the limit that appears in the definition of topological entropy? Let $X$ a compact metric space and $f\colon X\to X$ a continuous function and a subset $K \subset X$. The ...
1
vote
1answer
290 views

Calculating Shannon Entropy for DNA sequence?

I'm following the formula on http://www.shannonentropy.netmark.pl/calculate to calculate the Shannon Entropy of a string of nucleotides [nt]. Since their are 4 nt, ...
0
votes
0answers
184 views

Zero conditional entropy

This question is related to this math.se question but I need a bit more guidance. For two discrete random variables $X,Y$ we define their conditional entropy to be $$H(X|Y) = -\sum_{y \in Y} Pr[Y = ...
0
votes
1answer
54 views

Is mutual information convex in the joint distribution?

Assume some joint distribution $P(X,Y) = P(Y|X)P(X)$. It is well know that, for fixed $P(Y|X)$, mutual information is a concave function of $P(X)$ and, for fixed $P(X)$, a convex function of $P(Y|X)$ ...
1
vote
2answers
44 views

Concentration property of entropy

Let $X$ be a random variable taking its values in $A = \{a_1,\ldots,a_n\}$ such that $Pr[X = a_i] = p_i$ for all $1 \leq i \leq n.$ The entropy of $X$ is defined as $$H(X) = -\sum_{i=1}^n p_i \log_2{...
2
votes
2answers
102 views

Differential Entropy

I'm a little temporarily confused about the concept of differential entropy. It says on wikipedia that the differential entropy of a Gaussian is $\log(\sigma\sqrt{2\pi e})$. However I was thinking as $...
2
votes
1answer
166 views

Is the Library of Babel random? Does it contain information?

The Library of Babel is defined as a universe in the form of a vast library containing all possible 410-page books of a certain format and character set. However, applying two means of ...
0
votes
0answers
16 views

Why $H_{V^* \cup W^*} > H_{V \cup W}$ if $H_V$ denotes entropy of language

Let $W \subseteq X^*$ be an infinite language over a finite alphabet $X$, and define ($|w|$ denotes the length of $w \in W$) $$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
2
votes
1answer
34 views

Shannon information for a set of 3 equally probable elements?

How to calculate entropy as a number of binary choices for a set of three equally probable elements? The Shannon's formula gives $\log_2(3)=1.585$. But any interpretation of binary choices gives me $5/...
3
votes
1answer
69 views

Entropy of $f(x)=1$

Let $f(x)$ be a probability density function $f(x) = 1$ on $x = [0,1]$, and entropy defined as $$H(p(x)) = -\int p(x) \log_2(p(x)) \, dx$$ where $p(x)$ is a pdf. Unless I've made an arithmetic error, ...
0
votes
1answer
54 views

Approximation for a binomial coefficient sequence summation

What is a good approximation to $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{\binom{k(k-1)/2}{i}}$$ $$\dfrac{{\binom{k}{i}}{\binom{k}{i}}(i-1)!}{(2^{(\log k)^2}-1-i)\binom{k(k-1)/2}{i}},\quad\dfrac{{\...
0
votes
0answers
48 views

Mutual Information: Are these two equations equal?

I'm working with Multivariate Mutual Information (MMI), specifically with three variables $(X,Y,Z)$, applied to RNA sequences. The MMI equation that I use for three variables is based on entropy ...
1
vote
3answers
91 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, $...
0
votes
0answers
27 views

How to efficiently select a subset of elements that maximizes a certain property? (entropy)

I need to select $k$ elements from a pool containing a much larger number $N$ of elements. The selection must be done in a way that a function $h(\{z_{i_1},\ldots,z_{i_k}\})$ is maximized or ...
0
votes
1answer
150 views

How to calculate entropy from a set of samples?

entropy (information content) is defined as: $$ H(X) = \sum_{i} {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i} {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ This allows to calculate the entropy of a ...