Tagged Questions

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

learn more… | top users | synonyms

1
vote
1answer
25 views

Renyi entropy (zeroth order)

I am reading a book on information theory, therein has been introduced Renyi entropy of order $\alpha$ as $S_{\alpha} = \frac{1}{1-\alpha}\log(Tr\rho^{\alpha})$, where $\rho$ is density matrix. It ...
1
vote
0answers
22 views

Relative Entropy and variation formula for $C_c$

Let $R(\mu \mid \nu ) = \int_{\mathbb R} \log \frac{d\mu}{d\nu} d\nu$ for $\mu, \nu$ probability measures over $\mathbb R$. By the varational representation formula of Donsker and Varadhan we know ...
0
votes
1answer
41 views

Proving that $S=\bigcup_{j=0}^{2^k-1} S_{n-1+k}$ is a spanning set for the $2$-D Baker map

A set $S \subset X$ is a $(n,\epsilon)$-spanning set if $\forall x \in X$, $\exists y \in S $ such that $d_n(x,y)<\epsilon$. This is where we define $d_n(x,y)$ by $d_n(x,y)=\max_{0\leq k < ...
0
votes
0answers
17 views

Decomposing factorized entropy

I am trying to figure out how the equation for factorized entropy below is derived. The equation for entropy is $H(Q) = -\sum_x Q(x)\log Q(x)$ where $Q$ is a probability distribution. Let $Q(x) = ...
1
vote
2answers
36 views

Statistical Inference, Differential Geometry and Entropy

Context: Statistical Inference and Differential Geometry Let's consider a generic $ p(x;\theta) $ distribution with $ \theta $ Parameters Vector, it is obvious that $$ \int p(x; \theta) dx = 1 $$ ...
0
votes
1answer
47 views

Conditional Entropy in rolling a dice

A 6-sided die is tossed once. Two events X and Y are defined. X is the event in which an even number comes up and Y is the event in which the number is a multiple of 3. The value of H(X|Y) needs to be ...
1
vote
1answer
25 views

Channel Capacity of a Cycle Graph

I have the following problem: Given a discrete memoryless channel $Y = X + Z \mod5$, where $X$ is selected from one of 5 symbols (0, 1, 2, 3, 4), $Z$ randomly selected from (-1, 0, 1), and $X$ and $Z$ ...
0
votes
1answer
17 views

prove a theorem about an upper bound of entropy of a random vector

There is a theorem that: if Z is any zero-mean, complex random vector with covariance $E[ZZ^H]=R_z$, then $H(Z)\leq \log|{\pi eR_z}|$, with equality holding if and only if Z has a circularly ...
0
votes
0answers
14 views

Entropy of bit position in a bit stream

8 bit strings are sent over a channel. First two bits are always 1. Last six bits can be either 0 or 1. Receiver randomly selects bit-position and reveals bit but not its position. If X is the random ...
3
votes
2answers
45 views

Proof of recursivity of Shannon's Entropy

Does anybody know a book where the proof of recursivity property of Shannon's Entropy can be found? I mean this: $$H(q_1,...,q_n)=H(q_1 + q_2, q_3,...,q_n) + (q_1 +q_2)H( \frac{q_1}{q_1+q_2} , ...
-1
votes
0answers
25 views

Entropy of information and one-way algorithms.

Shannon's Entropy: $$H(X) = -\sum_iP(x_i)\log_bP(x_i)$$ Take a hash Y, and assume it gives different sum for any byte stream fitting into maximum input length of, for eg. SHA256 algorithm is: ...
0
votes
1answer
40 views

Calculate the Entropy Change if 5 Previously Tossed Dice Are Turned to All “1”

Relevant Equations: S = Boltzmann*ln(W) where S is entropy and W is the number of microstates. I have thought about this two ways. 1 way. Look at each die separately. Let macrostate 1 = number of ...
1
vote
1answer
104 views

Prove there exist a $p$ so that the inequality holds

I am stuck with the following problem. Given the Gaussian mixture distribution $f(\cdot)$ $$ f(x) = ...
0
votes
0answers
39 views

How to compute the topological entropy of a permutation?

I have a permutation, say as ${4,1,7,2,3,5,6}$, given by its induced matrix. According to this paper (Proposition 11 on p. 82), To compute its topological entropy, one can compute the ...
2
votes
1answer
53 views

Relationship between compression, shannon entropy and kolmogorov complexity

I have read that the Shannon Entropy is used as a bound for the compressibility of a message, for example here 1 it says "In other words, the best possible lossless compression rate is the entropy ...
0
votes
1answer
65 views

prove this inequality related to probability and information theory

How do I prove this? I'm thinking I should use Jensen's inequality somehow. $$\sum_K p_k(1-p_k) \le -\sum_K p_k\log p_k$$ The assumption that $\sum_K p_k=1$ holds.
0
votes
1answer
30 views

Normalization of data in decision tree

After reading through a few references, I have come to know that for machine learning in general, it is necessary to normalize features so that no features are arbitrarily large ($centering$) and all ...
0
votes
1answer
21 views

Tools to compress a finite list as a function

Can someone show me some tool to a lossless compression in an algorithm of a finite list of rational numbers? By example this list A=(0,1,3,2,-1,-2,0), there is a way to construct an algorithm or ...
1
vote
1answer
46 views

What is the correct equation for conditional relative entropy and why

I was trying to understand the concept of conditional relative entropy. As in: $$D(P(X\mid Y) ||Q(X\mid Y))= E [\log\frac{P(X\mid Y)}{Q(X\mid Y)}]$$ I would have thought that its equations would ...
5
votes
1answer
63 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
34 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
25 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
26 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
118 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
73 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 ...
0
votes
0answers
25 views

Finite shannon entropy and mutual information

I was wondering, if it can be shown that the shannon entropy for continuous random variables are finite, such that $H(X)=-\int_{-\infty}^{\infty}f(x)*log(f(x)) dx < \infty$ and the same question ...
2
votes
1answer
184 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
47 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
17 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
27 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
212 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
56 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
33 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 ...
5
votes
1answer
143 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
58 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 ...
0
votes
1answer
22 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
0answers
32 views

conditional entropy calculation

let us consider following table i am asked to calculate conditional entropy,from table i have understood everything,for instance how to calculate marginal probabilities,also i know formula for ...
0
votes
1answer
34 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
32 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
52 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 ...
0
votes
1answer
73 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
0answers
13 views

Few questions regarding applications of conditional entopy

I have the idea of entropy and conditional probability etc and having few conditional entropy related questions: 1. What does actually conditional entropy $H(Y|X)$ mean? How can we explain this term ...
0
votes
1answer
25 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
21 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
51 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
160 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
57 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
44 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
52 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)$$