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

learn more… | top users | synonyms

6
votes
1answer
154 views

Counting graph isomorphisms and entropy

Question: If all graphs on $n$ vertices are given equal probability, what does the induced probability distribution on the graph isomorphism classes look like? Are there any patterns that emerge as ...
0
votes
0answers
142 views

Entropy derivation from Multiplicity

Multiplicity(W)= N!/(n1!*n2!....ni!) Entropy = 1/N * ln W = 1/N*ln N! - 1/N*sigma_for_all_i(ln ni!) As N->infinity, By Stirlings approximation ...
0
votes
1answer
31 views

Meaning of this term:$H(X \oplus\hat{X}|\hat{X} )$

Here, $H$ means the entropy function. I understand that the symbol $\oplus$ means modulo $2$ addition. But I don't understand the significance of the entire expression.
1
vote
1answer
60 views

Relation between entropy and compressibility of a file

Suppose I have an ordered list of bytes (the hexdump of some object file), and wish to calculate the information entropy of this file. My understanding is I can calculate this as $$ \sum_{n=0}^{n=255} ...
1
vote
2answers
233 views

Upper bound on the entropy of a sum two random variables

Let $X$ be a random variable such that $|X| \leq A$ almost surely, for some $A > 0$. Let $Z$ be independent of $X$ such that $Z \sim {\cal N}(0, N)$. My question is: How large can the entropy ...
1
vote
2answers
160 views

Measuring the entropy of a graph representing a transition probability matrix of a first order markov chain

There's a research project i'm currently working on which requires me to analyze various aspects of "worlds" represented by transition probability matrices, where the nodes represent objects in the ...
2
votes
1answer
290 views

Entropy of the product of two random variables

Consider a random matrix $X$ and a random vector $Y$. Let the Shannon entropies $H(X) = H(Y) = n$. Is there a simple upper bound for entropy $H(XY)$? I believe $H(XY) \leq 2n$ as that is a simple ...
2
votes
1answer
65 views

partition with infinite entropy?

Let $P$ be an infinite partition of the interval $[0,1]$. Let $P$ have elements $I_i$ which has Lebesgue measure $m(I_i)$. Then the entropy of $P$ is defined by $\sum_i -m(I_i)\log m(I_i)$. Can this ...
1
vote
0answers
22 views

Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Let $p_0(x)$ be some arbitrary but fixed input probability distribution. The mutual information between the input ...
0
votes
1answer
39 views

how to find the maximum of the cross-entropy of a discrete random variable?

For a discrete random variable $x$, the cross entropy is $$H(x) = -(p_1\log p_1+\cdots+p_n\log p_n)$$ , so what is the maximum of $H(x)$? Here is what I tried, I compute the gradient as follows ...
7
votes
0answers
257 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
2
votes
1answer
62 views

If a series converges, does it converge with additional log term multiplied?

If $\sum_{n} |a_n| < \infty$, is it true that $\sum_{n} |a_n\log(a_n)| < \infty$ if $0 \leq a_n \leq 1$? I am trying to see if $A$ is trace class operator, then $A \log(A)$ is also trace class ...
0
votes
1answer
15 views

InformationGain on Two Continuos classes instead on inary

I've a problem regarding an excersise with information gain. I can't seem to get the right answer, because the excersises differs from what we learned. Usually, a target class is a binary variable ...
1
vote
1answer
44 views

Trying to understand the math in a neuroscience article by Karl Friston

I am trying to understand a neuroscience article by Karl Friston. In it he gives three equations that are, as I understand him, equivalent or inter-convertertable and refer to both physical and ...
6
votes
1answer
267 views

Finding a specific sequence of digits in pi

Looking at the pifs project on GitHub and this question on SO has made me curious as to how feasible it is to find a specific sequence of digits within Pi. Essentially, on average, how many digits of ...
0
votes
1answer
277 views

calculate channel capacity and maximum conditional entropy

i want to know when it is equal channel capacity or $I(X,Y)$ maximum or where $I(X,Y)=H(X)-H(X\mid Y)=H(Y)-H(Y\mid X)$ now if we have two random variable with some specific distribution ...
1
vote
1answer
57 views

when it is conditional entropy minimized?

for example let us consider following table know that entropy of variable is maximum when it is equally distributed,all of it's variable has equal probability,but what about joint entropy or ...
0
votes
1answer
37 views

What's the sum of all events? (not the sum of all probabilites of events)

I need to calculate the entropy $h(X|Y)$, where $Y=X^2$. In this case, I suppose $\mathrm p(x|y)=\frac{1}{2}$. For the entropy \begin{align} h(X|Y) &= \int\limits_y \mathrm p(y)\ h(X|Y=y)\ ...
1
vote
0answers
41 views

continuous, non-additive set function

I am looking for a non-additive, continuous set function from a simplex $\Pi_{n}$ of finite dimension $n-1$ into $[0,\infty]$. The motivation is as follows. Shannon defined the entropy ...
1
vote
2answers
102 views

Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
1
vote
1answer
389 views

How is the formula of Shannon Entropy derived?

From this slide, it's said that the smallest possible number of bits per symbol is as the Shannon Entropy formula defined: I've read this post, and still not quite understand how is this formula ...
0
votes
1answer
35 views

Mutual information decrease with coarse-graining

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$. Is it true that: If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus ...
1
vote
1answer
32 views

Gaussian distribution variance estimation

It's well known if I have a process generating normally distribuited data, I can estimate the parameters of the gaussian function: ...
5
votes
1answer
65 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
5
votes
1answer
176 views

Entropy of the induced transformation

I need help with this problem: Let $(X,\mathcal{B},\mu,T)$ be a ergodic dynamical system in the probability space $(X,\mathcal{B},\mu)$. Let $A \in \mathcal{B}$ with $\mu(A)>0$. We define the ...
1
vote
1answer
89 views

Variational Methods, why KL divergence is the difference between true distribution and approximating distribution.

Likelihood = $L(\textbf{w}) = P(V\mid \textbf{w})$. $$\ln P(V\mid \textbf{w}) = \ln \sum_H P(H,V\mid \textbf{w})$$ $$= \ln \sum_H Q(H\mid V)\frac{P(H,V\mid \textbf{w})}{Q(H\mid V)}$$ $$\geq ...
1
vote
0answers
74 views

What connections between computer science and ergodic theory?

I have a background in ergodic theory, but I am switching to computer science/programming. I would like to know if tools from ergodic theory could be useful, especially something around coding of ...
0
votes
1answer
84 views

Entropy of sum is sum of entropies

Having $X$ and $Y$ discrete random variables above finite set. Z is defined as $Z=X+Y$ when does the following happen: $$H(Z)=H(X)+H(Y)$$
1
vote
0answers
28 views

intuition for entropy solutions

For a hyperbolic PDE of the form $$u_t + f(u)_x = 0$$ it turns out that the right notion of solution is entropy solution. Now, the notion of classical solutions are obviously very natural, and also ...
0
votes
2answers
126 views

Entropy of sum of two Uniform random variables

say $X$ and $Y$ are two identical, independent and discrete Uniform random variables and $Z=X+Y$. I do not know more about the random variables. Assuming $H(\cdot)$ to be the entropy of a random ...
2
votes
1answer
51 views

Prove identity involving the Tsallis q-logarithm

The natural logarithm and the exponential can both be generalized to a called q-logarithms and q-exponentials.those functions are defined as follows: \begin{eqnarray} \log_q(x) &:=& ...
1
vote
0answers
52 views

What is the “true” entropy of a binary string?

Consider an infinite binary string $\sigma$ and define its entropy $$H_1 = -(p_0 \log_2 p_0 + p_1 \log_2 p_1)$$ with $p_i = \lim_{N\rightarrow \infty} N(i)/N$, $N(i)$ the number of $i$'s among the ...
0
votes
0answers
54 views

Problem with calculating probability of symbols

I've a $100 \times 100$ binary matrix it`s constructed with this probability table : i want to apply extended Huffman on this matrix my idea is to compress each column individually . - so starting ...
0
votes
0answers
25 views

Can we calculate entropy for nonstationary random variables?

Let's assume that $X$ is a discrete random variable, which can take any value from the set $\{x_0,\dots,x_n\}$ with the probability mass function $P(X)$. We can calculate the entropy of $X$ as ...
1
vote
1answer
45 views

Generlized Entropy compared to Generalized Dimension

I am currently reading the following paper by F.Takens: Multifractal analysis of dimensions and entropies. This paper discusses two different measures. One is generalized entropies and the other is ...
3
votes
1answer
63 views

necessity of uniform continuity for topological entropy

I am referring to Walters' book "Introduction to Ergodic Theory." When he defines the concept of topological entropy he always assumes that the transformation $T: X \rightarrow X$ is uniformly ...
3
votes
0answers
87 views

Huffman codes: does less entropy imply less weighted average codeword length?

Let $\Sigma$ be a source alphabet with a probability distribution over its symbols $P$. Then, the Shannon entropy of $\Sigma$ is $$-\sum p_j \times -\mbox{log}_2(p_j)$$ where $p_j$ is the probability ...
0
votes
1answer
58 views

Subadditivity of Entropy

We define $H(X) = -\sum_{x}p_{x}\log p_{x}$ and relative entropy as $H(p(x)||q(x)) = \sum_{x}p(x)\log \frac{p(x)}{q(x)} = -H(X)-\sum_{x}p(x)\log q(x).$ Now we have to prove that $H(X,Y,X) + H(Y) \leq ...
3
votes
2answers
104 views

Understanding conditional entropy intuitively $H[Y|X=x]$ vs $H[Y|X]$

I was trying to understand conditional entropy better. The part that was confusing me exactly was the difference between $H[Y|X=x]$ vs $H[Y|X]$. $E[Y|X=x]$ makes some sense to me intuitively because ...
2
votes
1answer
32 views

Are measures of information model specific?

Does an information measure for a signal do a better job if it assumes some things about the signal? For example: I have a digital stream of data, 0s and 1s coming at a clock rate $r$. What is the ...
1
vote
0answers
45 views

Solomonoff induction , Shannon Entropy, Kolmogorov Complexity.

If Expected Kolmogorov Complexity equals Shannon Entropy why can't Shannon Entropy be used as an approximation of Kolmogorov Complexity in Solomonoff Induction? Regarding Kolmogorov Complexity and ...
3
votes
1answer
88 views

toplogical entropy of general tent map

Measure theoretic entropy of General Tent maps The linked question made me wonder how to calculate the topological entropy of a general tent map. Let $I=[0,1]$ and $\alpha \in ( 0,1)$. Define $T: I ...
1
vote
2answers
153 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
5
votes
0answers
81 views

Looking for a a measure-theoretic treatment of “differential entropy”

If $X$ is a discrete random variable, its entropy $H(X)$ is usually defined as something along the lines of $-\sum \def\P{\mathbb{P}}\P(x) \log_2( \P(x))$, where the sum ranges over all the possible ...
1
vote
2answers
81 views

Shannon Entropy Minimization

The Shannon Entropy for an observation is given by $ -x \log_2(x)$. Why is the maximum entropy achieved at $x = \frac{1}{e}$, and not at $x = 0$? Could someone provide a logical explanation that ...
-2
votes
3answers
272 views

probabilistically what can we say about the next throw of a coin after n throws

this may sound easy or hard or whatever but i cant seem to find anything after searching around for a similar question/answer The question is this: What can we say (probabilistically) about the next ...
0
votes
1answer
47 views

For P0 close to P1 the relative entropy can be approximated by its series expansion,Why?

I am reading a article (An overview of distinguishing attacks on stream ciphers, Martin Hell · Thomas Johansson · Lennart Brynielsson) about Distinguishe Attacks. There is a approximate equation ...
2
votes
0answers
62 views

Maximize the expected Brier Score of P relative to P.

Fix a finite set $\mathcal S$ and let $\mathcal P$ be the collection of probability functions over the Boolean closure of $\mathcal S$. Let $\beta : \mathcal P \times \mathcal S \to \mathbb R$, with ...
5
votes
0answers
74 views

Decrease of entropy when iterating a random discrete function

Let $m$ be a positive integer. Let $S$ be the set of non-negative integers $x$ less than $m$, with $|S|=m$. Let $X_0$ be the discrete uniform distribution over $S$, with $P(x)=\begin{cases} 1/m & ...
2
votes
1answer
2k views

Correct algorithm for Shannon entropy with R

Shannon entropy is defined by: $H(X) = -\sum_{i} {P(x_i) \log_b P(x_i)}$, where b could be $e$, 2 or 10 (bit, nat, dit, respectively). My interpretation of the formula is: $H(X)$ is equal to the ...