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

learn more… | top users | synonyms

2
votes
2answers
99 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
40 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) ...
0
votes
0answers
22 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
30 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
31 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: ...
1
vote
1answer
111 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
38 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
60 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
25 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
134 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
163 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
23 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
25 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
0answers
19 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
38 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
21 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
109 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
29 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
84 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
164 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
99 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
38 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
41 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 ...
2
votes
2answers
79 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
137 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| = ...
1
vote
1answer
32 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 ...
3
votes
1answer
61 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
51 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 ...
0
votes
0answers
45 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 ...
0
votes
2answers
57 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
26 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
82 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 ...
3
votes
1answer
86 views

“Empirical” entropy.

Information entropy is usually defined as $$\text{I}_b({\bf p}) = -\sum_{\forall i}p_i\log_b(p_i)$$ i.e. the expected value of the negative logarithm of the probabilities. This is all good when we ...
2
votes
1answer
72 views

Is conditional entropy ever taken to be a random variable?

In probability theory, the conditional expectation $E(X|Y)$ and variance $V(X|Y)$ er usually taken to be random variables, st. the value of $E(X|Y)$ depends on what value $Y$ ends up taking. I've ...
1
vote
1answer
27 views

How does a wavelet help in compressing data

I have an understanding of how we carry out image compression by using DCT along with Huffman encoding. The next subject is wavelets. I understand that wavelets are small waves and there are different ...
0
votes
0answers
106 views

Shannon Entropy Maximization with Constraints

I have got a cumulative distribution function $F_X(x)=Pr(X<=x)$. This distribution is described by 2 parameters $\alpha, \beta$. We define $F_k$ as follows: $\forall k<=n_k, ...
3
votes
1answer
131 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy of the random variable X ...
0
votes
1answer
35 views

Mutual Information: How these two equations are equal?

I'm a biologist trying to apply the Mutual Information (MI) to some RNA secondary structure. I know that there exists two MI equation that, mathematically, are equal: $I(X,Y) = \sum_{x,y} p(x,y) ...
1
vote
1answer
39 views

Infinite closed shift-invariant set of binary sequences with zero entropy?

Does there exist an infinite closed shift-invariant $X \subset \{0,1\}^\Bbb Z$ with zero topological entropy? How to think of an example? Will periodic points of shift$|_X$ have zero entropy?
0
votes
0answers
32 views

The difference in entropy rates between a hidden process and its observation

Let $S$ be a finite state space and $o:S\to S$ an observation function. Given a distribution $p$ on $S\times S$, consider the following optimization problem: $$\max \left[ EntropyRate(\{x_t\}) - ...
0
votes
1answer
44 views

Derivation of equation for self information

I am trying to understand how the formula I(x) = -log(p(x)) for self information was derived. From what I have read, 2 constraints were imposed on the properties ...
0
votes
1answer
49 views

Clarifying Derivation of Entropy

I'm learning about probability from the book Pattern Recognition and Machine Learning by Christopher Bishop. It includes a justification for the definition of entropy that can be summarized as: let ...
2
votes
2answers
54 views

$\log (A + \delta A) = ?$ (as an expansion in $\delta A$), where $A$ and $\delta A $ are matrices

$A$ and $\delta A$ are two non-commuting matrices and I am seeking a power series expansion to 2nd order in $\delta A$. After writing it as $\log (A (1 + A^{-1}\delta A) )$, I am unable to figure out ...
2
votes
0answers
20 views

Graph Entropy - A Tractable Measure to Measure Distinguishability of Neighbourhoods

Given a labelled directed graph G, I am interested in a measurement of G that captures how distinguishable arbitrary connected sub graphs of G are. Labels may repeat and as such two or more different ...
0
votes
0answers
23 views

How to define a one-parameter family of probability distributions

I am trying to evaluate a noise-source as a means of providing entropy to a random number generator. I am running into trouble when it comes to determining the probability distribution that has the ...
1
vote
2answers
50 views

How much information does learning this interval give you?

Let's say you have a number $x$, and a priori, you know that $x \in [0, 1)$ (each value from 0 to 1 is equally likely.) Then a wizard comes and tells you that $x \in [a, b) \subseteq [0, 1)$. How much ...
1
vote
2answers
65 views

Scalar derivative of ${\rm tr}~[A(x)\log A(x)]$ where $A(x)$ is a square matrix

How do i proceed to calculate $$\frac{d}{dx}{\rm tr}\left[{A(x) \log A(x)}\right]$$ where $A(x) \in \mathbb{M}(n)$ and $x \in \mathbb{R}$? The $\log$ function is the one defined by the exponential ...
1
vote
2answers
71 views

How many bit-flips are required to achieve random distribution?

If I have a binary number W bits wide, initially all set to zero, and I repeatedly pick a random bit and toggle it from zero to one or vice versa, how many times would I need to do this to achieve ...
0
votes
1answer
66 views

mutual information adds along path

Is it true that $I(X;Y)+I(Y;Z)=I(X;Z)$ for $X \to Y \to Z$? $I(X;Z) = H(X)+H(Z)-H(X,Z)$ and $I(X;Y)+I(Y;Z) = H(X)+H(Z)-H(Z|Y)-H(X|Y)$ Hence, we would require $-H(X,Z)=-H(Z|Y)-H(X|Y)$ -- is it true? ...