The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
1answer
427 views

Calculate channel capacity of general channel under constraint

Hi! Given a conditional distribution $P_{Y|X}$ I'd like to find the prior distribution $P_X$ that maximizes the mutual information $I(X;Y)$ with $P_Y(y)=\int P_{Y|X}(y|x)P_X(x)\text{dx}$ (this ...
-3
votes
0answers
38 views

Mutual Information: How these two equations are equal? [on hold]

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) ...
0
votes
1answer
66 views

Asymptotically full stationary process

Let $(X_n)_{n \in \mathbb{Z}}$ be a stationary process on a finite set $A$. Say that it is asymptotically full if for every increasing sequence of subsets $B_n \subset A^n$ such that ...
2
votes
1answer
88 views

Convolution of measures - entropy growth

Imagine you have two shift-invariant measures $\mu, \nu$ in the Bernoulli space $\{0,1\}^{\mathbb{N}}$ with positive entropy and both are not the Bernoulli measure $(\frac{1}{2},\frac{1}{2})$. I know ...
-3
votes
0answers
47 views

invariant mesures and entropy

Fix {0,1}^{N} the Bernoulli space, the shift function S and pick two dynamical systems (S,m1) (S,m2) (m1,m2 S-invariant measures). Let's say you have entropies h1 and h2 for the dynamical systems. ...
1
vote
2answers
181 views

Entropy inequality

Let $P,Q$ be probabilities on a finite set $A$ with $Q(a)\gt 0$, for all $a\in A$, and let $H(P),H(Q)$ denote the entropy and Kullback-Leibler distance respectively. Is it always true that ...
3
votes
2answers
143 views

Maximizing entropy under constraints

This question is about an extension of the variational principle in thermodynamical formalism when one adds linear constraints to the measures. Consider the one-sided shift ...
2
votes
2answers
431 views

Convexity and semicontinuity of the relative entropy function

There are several different definitions of relative entropy, and some of them are not equivalent. Following is the definition we will use in this question. Let $M$ be a closed manifold and ...
1
vote
0answers
102 views

Estimates of entropy of functional spaces

Let $M^n$ be a compact $n$-dimensional manifold. For $k\geq 0$ let us denote by $C^k(M)$ the Banach space of $k$ times continuously differentiable functions, and $B_{C^k}$ denote the unit ball of it. ...
2
votes
1answer
185 views

Embeddings of subshifts

Consider $(X,\sigma_X)$ and $(Y, \sigma_{Y})$ be subshifts of the one sided shift in two symbols. Assume that $(X,\sigma_X)$ is a transitive subshift of finite type and $(Y, \sigma_{Y})$ is a ...
9
votes
2answers
345 views

Expected centered entropy of the binomial distribution

In short, the function I am interested in is the following: $$I_n(p) = \sum_{k=0}^n \binom{n}{k} p^k (1-p)^{n-k} \left[h(p) - h\left(\tfrac{k}{n}\right)\right],$$ where $h(x) \triangleq -x \log x - ...
1
vote
1answer
230 views

Coupon Collector Problem for Non-Uniform Coupons: Bound on the number of missed Coupons

Suppose $\mathcal B=\{1,2,..,b\}$ is the set of all possible coupons, with $\mathbf p = ( p_1,p_2,...,p_b)$ assigning the probability of occurrence for all coupons in $\mathcal B$. The "traditional ...
2
votes
0answers
73 views

Concentration bound in high min entropy distribution

Let $(X_{1},\dots,X_{m})$ be joint distribution on $\{0,1\}^{m}$ with that $H_{\infty}(X_{1},\cdots,X_{m})\geq m-r$, where $H_{\infty}$ means min-entropy. Let $P_{1},...,P_{n}\subseteq [m]$ be sets ...
16
votes
8answers
1k views

When do people actually use the maximum entropy distribution?

One of the standard problems in convex optimization is the calculation of the maximum entropy distribution that satisfies some set of criteria. For example, if $\mathbf{x} \in \mathbb R^n$ is an ...
0
votes
0answers
44 views

minimal entropy approximation of a truncated discrete measure

Consider a measure $\mu$ on $\mathbb{N}$ given by the sequence $(\mu(n))_{n \geq 0}$ with $\mu(0)>0$. For example $\mu(n)=n^2+1$ on the figure below. For each $n$, let $X_n \sim \mu(\cdot \mid ...
15
votes
3answers
370 views

Intrinsic significance of differential entropy

Many commentators (e.g. Jaynes, Rota) argue that the notion of "differential entropy" is problematic (as commonly defined by $ h(X) = \int ( \log\frac{1}{p(x)} ) p(x) \, dx $, where $X$ is a random ...
2
votes
0answers
55 views

minimal entropy approximation of a discrete random variable

Let $X$ be a $\mathbb{N}$-valued random variable. Define $$ H^\epsilon_n(X) = \inf_f H(f(X)) $$ where $f$ runs over all functions $\mathbb{N} \to \mathbb{N}$ such that $\Pr(f(X)\neq X)<\epsilon$ ...
1
vote
1answer
133 views

Discrete Maximum Entropy Distribution with given mean

For a given mean $\mu$, what is the entropy maximizing probability distribution on the nonnegative integers? Different sources indicated either the geometric or the Poisson distribution for this. As ...
8
votes
2answers
398 views

Inequality in information theory

I am reading the paper "chain independence and common information" (http://ttic.uchicago.edu/~yury/papers/independ.pdf). In this paper, an inequality is used several times (without proof) which looks ...
2
votes
0answers
149 views

Interpretation of Shannon Entropy Application

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Let entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ be given by ...
2
votes
0answers
48 views

Sequence transformations that are entropy invariant

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Define entropy of $\mathcal{A}=\{a_i\}_{i=1}^m$ by ...
1
vote
1answer
105 views

Limiting Entropy of deterministic sequences - 1

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$. Consider distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Given $\{a_i\}_{i=1}^m$, let $\mathcal{P}_{a,m}$ be distribution at ...
1
vote
0answers
42 views

Limiting Entropy of deterministic sequences - 2

Consider a collection of increasing positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Given $\{a_i\}_{i=1}^m$, let $\mathcal{P}_a$ be limiting distribution ...
1
vote
1answer
80 views

Entropy difference dominance of sequences

Consider a collection of positive integers $\{a_i\}_{i=1}^m$ and the distribution $p_i=\frac{a_i}{\sum_{i=1}^ma_i}$. Similarly for the collection $\{a_i\}_{i=1}^{m+1}$ form the distribution ...
1
vote
1answer
56 views

Entropy dominance of certain restricted sequenes

Say you have positive $\{a_i\}_{i=1}^n$ and you have $p_i=\frac{a_i}{\sum_{i=1}^na_i}$, then assume you have a $C$ such that $C<2a_n\ll\sum_{i=1}^na_i$ (that is $C$ is not very large), then define ...
2
votes
1answer
70 views

Entropy dominance

Let $0<a<b<c$ be distinct positive reals. Define four different probability distributions: $$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$ ...
8
votes
1answer
195 views

Higher moments of information and Renyi entropy

For a given discrete probability distribution, Shannon entropy can be though as an expectation value $\langle - \log p \rangle$ (see also: What is entropy, really?, What is the role of the logarithm ...
2
votes
0answers
77 views

Property of relative entropy [closed]

For $X$ a measurable space and $P,Q$ two probability measure on $X$ s.t. $Q$ is absolutely continuous with respect to $P$, the relative entropy is defined as $$D(Q\|P)=\int_X ...
3
votes
1answer
81 views

Average entropy of quantum system in bipartite pure state for finite temperature

[I got halfway through writing this when I found the paper that answers the question in (essentially) the affirmative. I'll post it anyways in case anyone is interested.] Background: If a random ...
0
votes
1answer
126 views

Why private randomization does not help the Shannon's source coding

I am wondering why stochastic encoder and decoder can not help the Shannon source coding? I know the achievability scheme of source coding, which is based on typicality, is deterministic, and hence we ...
2
votes
1answer
68 views

Which is the right way to compute the Approximate Entropy (ApEn)?

My problem is the inconsistency between the definition and the computation of the Approximate entropy (ApEn). Suppose $u = (u_i:1\leq i \leq N)$ is a sequence of ...
1
vote
1answer
101 views

Entropy on a draw from a random distribution.

Suppose I am attempting to calculate the entropy of a continuous, normally distributed random variable $X$, from the distribution $\mathcal{N}(\mu, \sigma)$. This is easy to to do - I just calculate ...
4
votes
0answers
83 views

$q$-deformations of fundamental equation of information and entropies

Classical information theory: fundamental equation of information In classical information theory, the information $I(A)$ of an event $A$ (any element of the $\sigma$-algebra $\mathcal F$ of a ...
18
votes
2answers
1k views

An Entropy Inequality (generalized)

Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$. For $0\le \alpha \le 1$, set $K=\sum_i X(i)^\alpha Y(i)^{1-\alpha}$ so that $Z:=\frac{1}{K}X^\alpha Y^{1-\alpha}$ is also a probability ...
1
vote
0answers
44 views

Characterization of the optimal solution in relative entropy minimization

The following optimization problem is related to relative entropy and to the limit of the iterative proportional fitting procedure. For $1 \leq i,j \leq n$ and fixed $w_{ij} \geq 0$, and fixed $a_i, ...
1
vote
1answer
102 views

Invariance of mutual information

Let $I(X,Y):=H(X)+H(Y)-H(X,Y)$ be the mutual information of the joint probability distribution $p_{XY}$ (here $H(\cdot)$ is the Shannon entropy of its argument). I know that the mutual information is ...
3
votes
0answers
123 views

On the volume entropy of negatively curved manifolds

Let $X$ be the universal cover of a closed negatively curved Riemannian manifold. Let $x_0\in X$ be a base point, $S$ be the unit sphere in $T_{x_0}X$ and $\exp:T_{x_0}X\rightarrow X$ be the ...
1
vote
1answer
86 views

Connection between inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
9
votes
2answers
353 views

Entropy for Haar measure on $O(n)$

Let $G$ be a locally compact group. A measure $\mu$ is the right-Haar measure on $G$ if for every $g\in G$ and $E\subseteq G$ Borel set $\mu(Eg)=\mu(E)$. It is known that every locally compact group ...
4
votes
3answers
514 views

Incremental entropy computation

After a quick internet search I found no method for incremental entropy computation. Question 1 Let $\{x_i\}_{i=1}^n$ and $\{x_i\}_{i=1+n}^{n+m}$ be two samples and let $S_i^j:=\sum_{k=i}^j x_k$. ...
1
vote
3answers
137 views

How to estimate the entropy of a distribution on a power set?

Given a probability distribution $(X,p)$, its entropy is defined as $H=-\sum_{x\in X} p(x)\log p(x)$. Given a sample of observations $x_n,n=1..N$, one can estimate $p(x)=\frac{\#\{i:x_i=x\}}{N}$ and ...
2
votes
0answers
33 views

largest size for a randomness extractor

I am not so expert in theoretical computer science, so sorry if the question is trivial, i just could not find it in literature. Suppose we have a source $X$ with min-entropy $\ell$, the randomness ...
12
votes
0answers
176 views

Entropy in elimination theory, or a brief remark by Gelfand-Kapranov-Zelevinsky

In the introduction to their book "Discriminants, resultants and multidimensional determinant", the authors state a very intriguing observation concerning the coefficients of monomials appearing in ...
5
votes
1answer
173 views

General additive function of probability

Let $H$ be a function of finite sequences of probabilities (non-negative numbers summing up to 1) into real numbers, such that: $H$ is continuous, $H$ is symmetric w.r.t. the order of its arguments, ...
9
votes
1answer
622 views

Entropy of edit distance

The edit or Levenshtein distance between two strings is the minimum number of single character insertions, deletions and substitutions to transform one string into another. If we take random binary ...
2
votes
0answers
53 views

Private Randomness extractor

Suppose we are given two random variables $X$ and $Y$ with fixed marginal and joint distribution. What is the maximum randomness that we can extract from $Y$ that is independent from $X$, that is, if ...
16
votes
1answer
916 views

Gini Coefficient and Renyi Entropy

Gini coefficient (aka Gini Index) is a quantity used in economics to describe income inequality. It is 0 for uniformly distributed income, and approaches 1 when all income is in hands of one ...
4
votes
1answer
365 views

Upper bound on joint Renyi entropy

Renyi entropy of a random pair $(X,Y)$ with probability distribution $p_{X,Y}$ is defined by \begin{equation} H_\alpha(X,Y) = \frac{1}{1-\alpha}\log\sum_{x,y} p_{X,Y}(x,y)^\alpha. \end{equation} ...
5
votes
0answers
206 views

Maximizing Renyi entropy for a certain channel

The channel under consideration is $T = A + B$, where $A$ and $B$ take on values in $\{0, 1\}$ according to a probability mass function. Let (joint) random vector $(A_1, A_2,\ldots, A_n)$ be denoted ...
2
votes
0answers
171 views

metric entropy for Lipschitz functions

Suppose $(X,d)$ is a metric space of unit diameer and let $F$ be the collection of all $1$-Lipschitz functions mapping $X$ to $[-1,1]$, equipped with the sup-norm $||\cdot||_\infty$. I am interested ...