Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [entropy]

This tag is for questions about mathematical entropy. If you have a question about thermodynamical entropy, visit Physics Stack Exchange or Chemistry Stack Exchange instead.

0
votes
0answers
8 views

Effect of a convolution with a Bernoulli distribution on Rényi divergence

Let $P$ and $Q$ be two probability distributions on $\mathbb{Z}$. Let $D_\alpha(P\|Q)$ be the Rényi divergence of order $\alpha$ of $P$ and $Q$: $$ D_\alpha(P\|Q)=\frac{1}{\alpha-1}\sum_i\frac{P(i)^\...
3
votes
1answer
41 views

Trace of a matrix exponential with tensor products, and Von Neumann entropy

$\def\T{\operatorname{Tr}}$ $\def\1{\mathbb{1}}$ Let $H=H_1\otimes H_2\otimes H_3$ be a finite dimensional Hilbert space, and let $\rho_{123}$ be a self-adjoint matrix with $\rho_{123}\geq 0$ (...
0
votes
0answers
11 views

bounding min-entropy gain in differential privacy

In privacy-related computer science literature, we say that a randomized algorithm $\mathcal{K}$ that produces a model $\theta$ from a sample $X=(x_1,...,x_n)$ is $\epsilon$-differentially private iff ...
0
votes
0answers
17 views

Infimum of $f(\theta)= -\sum_{i=1}^n (y_i - \alpha p(y_i|x;\theta)) \ln p(y_i|x) $

Suppose $y_1 = 1, y_2 = y_3 = ...=y_n = 0\ (n\geq2)$, and $\sum_{i=1}^np(y_i|x;\theta) = 1$, $0\leq p(y_i|x;\theta)\leq1$. Meanwhile $\alpha > 0$ is a constant. Let's define a function $$f(\theta)...
1
vote
1answer
29 views

The motivation of continuous random variable mutual information by $k$'th nearest neighbour

I am reading this paper Kraskov et al, 2004, Estimating Mutual Information on estimating the mutual information of two continuous random variables based on entropy estimates from $k$-nearest neighbour ...
1
vote
1answer
39 views

Entropy for linear advection-diffusion equation

Let u be a solution to $$u_t+cu_x=\epsilon u_{xx}$$ with $\epsilon>0$, $c \in \mathbb{R}$. Show that for any convex function $\mu \in C^2(\mathbb{R})$ the total entropy $\int_\mathbb{R}\mu(u(x,t))...
0
votes
1answer
7 views

Can I derive a well-known distribution from another divergence?

A large class of distributions can be derived from $\max_{p(x)} H(p)$ s.t. $E_x{x}=\mu$ $E_x{x^n}=c_n$ where $H(p)$ denotes the Shannon (differential) entropy and are called maximum entropy. ...
0
votes
1answer
14 views

A hint for the entropy problem-entropy of one discrete variable is greater than the entropy of another one

I need a hint on how to start solving the following problem. Entropy of a discrete variable X is $H(X) = −\sum_{x\in \{x:P(X=x)>0\}}P(X=x)logP(X=x)$. Let $f:R → R$ be any function.\ a) Show that ...
0
votes
1answer
35 views

Distributing objects on containers

Suppose we have $n$ containers, each has the ability of holding $f_{i}$ object for $i=1, 2, \dots, n$. That means $f_{i}$ is the maximum number of object that the $i$th container can hold. Now, we ...
0
votes
0answers
16 views

take derivative of differential entropy of beta distribution

In order to find a beta prior for Bernoulli (Binomial) distribution, one way is to find the maximum entropy prior distribution. Now let assume if we only have information about the mean value of beta ...
0
votes
0answers
12 views

Show a convolution of distributions ε-close to min-entropy k is ε^t-close to min-entropy k

Assume $X_1,...,X_t$ are independent distributions on $\mathbb{Z}_2^n$ s.t. each $X_i$ is $\epsilon$-close to min-entropy $k$; i.e. there exist distributions $Y_1,...,Y_t$ on $\mathbb{Z}_2^n$ s.t: $$ \...
0
votes
0answers
30 views

Bound on KL-divergence-like quantity (with squared logarithms)

Given two discrete probability distributions over $n$ events, with $p_i$ and $q_i$ denoting the probability that the ith event occurs respectively, I am looking for an upper bound of the following ...
0
votes
0answers
27 views

How close is the expected length of Huffman coding and entropy?

If I want to use entropy as an approximation for the expected length of Huffman coding, how good is the approximation? I know the following identity: $H(X)\leq L(X)< H(X)+1\ $ where expected ...
1
vote
1answer
30 views

Simple Expression Related to Mutual Information

One way to define the mutual information is $I(X;Y) = H(X) - H(X|Y)$ I have found it useful to look the related quantity $?(X;Y=y) = H(X) - H(X|Y=y)$ That is, we look at how much the entropy of $X$...
1
vote
2answers
49 views

Entropy of continuous and discrete random variables

If N is a continuous random variable and X a discrete random variable. How can I calculate H(X|Y) if Y=X+N? N is a triangular distribution between -1 and 1 X can take the values ​​+-0.5 with equal ...
2
votes
0answers
31 views

An entropy inequality: $h_{\mu}(\beta,T)\leq h_{\mu}(\alpha,T)+H_{\mu}(\beta|\alpha)$

Let T be a measure preserving transformation on the probability space $(X,\mathcal{F},\mu)$. I have already solved this problem: Suppose $\alpha$ is a finite partition of $X$. Show that $h_{\mu}(\...
3
votes
1answer
24 views

Is the Renyi entropy an invertible functional of ordered probability distributions?

The Renyi entropy assigns a real number $H_{\vec{p}} (\alpha)$ to a probability distribution $\vec{p} = (p_1, p_2, \ldots)$ as a function of an order parameter $\alpha > 0, \alpha \neq 1$: $$H_{\...
0
votes
1answer
59 views

Number of points on a hyperbolic sphere a certian distance apart

Let $\mathbb{H}$ denote the upper half-plane with hyperbolic metric. Choose $p \in \mathbb{H}$. Let $\delta:=\lim\limits_{R\to \infty}\frac{\log(Vol\left(B(p,R)\right))}{R}$ be the volume entropy. ...
1
vote
0answers
34 views

Getting closer to $k$ min-entropy using summation

A distribution $D$ over $\Lambda$ has $k$ min-entropy if the largest probability mass given to any element in $\Lambda$ is $2^{-k}$ (i.e., for all $a\in\Lambda$, $D(a)\leq 2^{-k}$, and for some $a$ it ...
0
votes
1answer
60 views

A simple inequality involving the entropy function $H(x)$.

I came across the following simple inequality when I was working on a proof. I would like to know if it's a known inequality and used anywhere. $H(x) > (\ln x)\times (\ln (1-x)), 0 < x < 1.$ ...
6
votes
4answers
108 views

Entropy Lower Bound in Terms of $\ell_2$ norm

Define $$ \begin{align} H(p_1, \dots, p_n) &= \sum_{i=1}^n p_i\log1/p_i\\ &=\log n+\sum_{i=1}^n\sum_{k=2}^\infty (-1)^{k + 1} n^{k - 1} \frac{(p_i - 1/n)^k}{k (k - 1)}, \end{align} $$ where $...
2
votes
2answers
30 views

Should conditional entropy always be negative?

Recently I am studying basic of information theory and I found an awkward inequality while I am postulating following equalities using definitions of the entropy and Kullbeck-Leibler divergence. ...
0
votes
0answers
19 views

Poisson Binomial Distributed Score weighted by entropy / rareness

I have a game whose score (at chance performance) is a poisson binomial distribution (i.e. a sum of x independent Bernoulli trials, not necessarily equally distributed). It's possible in this ...
0
votes
0answers
13 views

Entropy of discrete variable

Let entropy of discrete variable $X$ be $H(X) = -\sum\limits_x{P(X=x)log(P(X=x))}$. Let $f : \mathbb{R} \rightarrow \mathbb{R}$ be any function. 1.Show that $H(X) \ge H(f(X))$ 2.Show that $H(X) = H(f(...
0
votes
0answers
21 views

Algorithm to explain the minimum subset of n variables to explain a sum of non-negative functions in N variables

For a practical application, I have a set of $M$ real valued functions $f_i(\mathbf{x}_t) , \hspace{6pt} 1 \leq i \leq M$. $x_{j,t}$ can be either real or integer in a limited range. The functions ...
0
votes
0answers
32 views

Entropy Rate of Markov Chains

I'm trying to compute the entropy rate of a given Markov chain using the following formula: $$H = -\sum\limits_{i,j}\pi_iP_{i,j}\log( P_{i,j.})$$ Below the pseudo-code I'm using in order to ...
0
votes
1answer
22 views

Two-look Gaussian channel

I'm reading through a solution from Elements of Information Theory by Thomas A. Cover. This is the two-look Gaussian channel, where the input to the channel is $X$ and the output is $(Y_1, Y_2)$. $...
5
votes
1answer
121 views

Maximum Entropy with bounded constraints

Assume we have the problem of estimating the probabilities $\{p_1,p_2,p_3\}$ subject to: $$0 \le p_1 \le .5$$ $$0.2 \le p_2 \le .6$$ $$0.3 \le p_3 \le .4$$ with only the natural constraint of $p_1+...
0
votes
0answers
31 views

Entropy of intervening variable in Markov Chain

Let's assume we are given discrete random variables $X$, $Z$, with some nonzero mutual information $I[X,Z] > 0$. I would like to understand the minimum entropy of variables $Y$ such that $X \...
0
votes
2answers
38 views

Proof that $H(X) \leq \log(|A|)$ (Shannon entropy)

The full question states: "Show that $$H(X) \leq \log(|A|)$$ with equality if and only if $P_X$ is uniform. Hint: use the Gibbs or log-sum inequality " I used "$A$" as the alphabet in here. My ...
1
vote
0answers
24 views

Tsallis entropy limit

I'm trying to understand how Tsallis entropy generalizes Boltzmann-Gibbs entropy. The Tsallis Entropy wikipedia article says Tsallis entropy of a distribution $p_i$ is: $$ s_q(p_i) = \frac{k}{q-1} \...
0
votes
0answers
35 views

Proof that the binary entropy is concave

Defining the binary entropy function as $H_{bin}(x) = - x\log(x) - (1-x)\log(1-x)$, how do I show that it is concave? I can see the intuition but not the proof. Namely, I need to prove that $H_{bin}(...
0
votes
2answers
45 views

Entropy of an infinite sequence?

Does an infinite sequence always have finite entropy? For example, doesn't $a_n=n$, the sequence of non-negative integers, have very low entropy? It feels like all "well-defined" sequences ought to ...
0
votes
0answers
54 views

Information theory - Intuition of channel capacity

Question As stated in Elements of Information theory, given $p(y|x)$, the Information channel capacity formula is $C = \max_{p(x)} I(X; Y)$ where $X, Y$ are input and output symbols, $p(x)$ is the ...
4
votes
0answers
65 views

Can this vague feeling about entropy be made precise?

Let $I$ denote the unit interval and $\mu$ be the Lebesgue measure. Let $S:I\to I$ be the map defined as $S(x)=2x \pmod{1}$. Then it is known that for any measurable subset $A$ of $I$ we have $$ \lim_{...
1
vote
1answer
41 views

True random generation given radioactive entropy

I have been reading various sources for experimentation with truly random numbers. As I understand, it is impossible for a computer to generate a "truly random" number as they are deterministic in ...
2
votes
1answer
55 views

Partial derivative of cross-entropy

I am trying to make sense of this question. $$E(t,o)=-\sum_j t_j \log o_j$$ How did he derive the following? $$\frac{\partial E} {\partial o_j} = \frac{-t_j}{o_j}$$
0
votes
0answers
19 views

Nice dimension independent proof of entropy inequality?

How does one prove that for arbitrary finite number of random variables $X,Y,Z,T,...$ the Shannon Entropy inequality holds $H(X,Y,Z,T,...) \leq H(X)+H(Y)+H(Z)+H(T)+...$ I know how to do it with ...
0
votes
1answer
15 views

Why doesn't the law of total expectation apply here? $E[X] = E[E[X \mid Y]]$

I'm learning about Entropy for the first time. From Wikipedia, $$H(Y \mid X = x) = E[I(Y) \mid X=x]$$ and the confusing part for me is this statement: " $H(Y \mid X)$ is the result of averaging $H(Y ...
0
votes
0answers
27 views

Learning about Entropy, notation question: is $P(X)$ a random variable?

Background I'm taking a first year probability course and I've gotten reasonably comfortable calculating $E[g(X)]$ using LOTUS. Now I'm learning about Entropy and for the first time I'm encountering ...
0
votes
0answers
28 views

Mean and variance of empirical entropy

$M$ samples are drawn from a discrete probability distribution $\bigl( p_i>0; \; \sum_{i=1}^{N} p_i \bigr)$. The number of times result number $i$ has occurred is given by $M_i$ (s.t. $\sum_{i=1}^N ...
0
votes
0answers
12 views

How can I solve this entropy example

X is number of points for throwing a fair dice X can be 1,2,3,4,5,6. and Y = 1 if X <5 , Y = 0 if X = 6. Then, what is the answer of H(Y) and H(X|Y)
0
votes
0answers
19 views

The integration of the entropy to the exponential distribution

I would like to ask the integration of the entropy to the exponential distribution, which is as below: Exponential: $$ p_{x}(x)=\theta*e^{-{\theta}*x}$$ ...
0
votes
1answer
19 views

How much BPS(Bits per symbol) is enough to call a compression algorithm good, with respect to entropy?

Consider a general purpose lossless data compression algorithm, It compresses a randomly generated binary file of 100MB size, with random I mean I wrote a small Script to create a file with random ...
0
votes
0answers
39 views

Entropy of random variable

Let $(\Omega, \mathcal{F}, P)$ be a probability space with $|\Omega|=m <\infty$ and $P(\omega)>0 \ \forall \omega \in \Omega$. $H(P):=-\int \log(P(\omega))dP(\omega)$ denotes the differential ...
0
votes
0answers
40 views

Prove $H(X,Y) ≤ H(X) + H(Y)$

I am trying to prove that $H(X,Y) \leq H(X) + H(Y)$ where $X,Y$ are two random variables. I saw that someone else posted this question before as well, but the discussion about it wasn't quite what I ...
0
votes
0answers
43 views

Entropy maximizing distribution when power constraint exists for one random variable

Suppose I have a random vector $\bar{X}=[X_{1},X_{2}, X_{3}]$. X1,X2 and X3 can take values from the alphabet {0,1,2,3} . (This can be even generalized to a finite set of cardinality N). I don't have ...
0
votes
1answer
45 views

Find probability distribution (joint pdf) that satisfy constraints

Suppose I have a random vector $\bar{X}=[X_{1},X_{2}]$. $X_{1}$ and $X_{2}$ comes from the alphabet {0,1,2}. I don't have any information on the probability distribution of these random variables. In ...
0
votes
3answers
97 views

What is the relationship between information in the sense of Shannon entropy and information for the human brain?

In an informatic theoretic sense, complete randomness maximizes information. For instance, an image of randomly distributed black and white pixels has a very high entropy/information. For a human ...
0
votes
0answers
40 views

Kolmogorov-Sinai theorem for a generator with infinite entropy

I can find many books and documents stating the Kolmogorov-Sinai theorem (that is $h(T) = h(T,P)$ if $P$ is a generating partition) when the generating partition is finite or countable with finite ...