The tag has no usage guidance.

learn more… | top users | synonyms

2
votes
0answers
55 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 ...
5
votes
0answers
222 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
203 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 ...
8
votes
2answers
436 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 ...
1
vote
1answer
313 views

Approximation of the sum involving binary entropy function

Given the following sum: $S(n) = \sum_{i=1}^{n} \frac{1}{(1-\operatorname{H}(p))^i}$ where $H$ is the binary entropy function defined as: $\operatorname{H}(p) = -p\log p - (1-p)\log (1-p) $. Let ...
3
votes
1answer
404 views

Simple reason that a mathematician cannot do better than random when guessing contents of a box?

I have a question about the finite analog of the puzzle proposed here involving mathematicians guessing the contents of boxes. Specifically, suppose there are $k$ unopened boxes each containing a ...
3
votes
1answer
190 views

Is there a one-dimensional subshift of positive entropy s, all of whose sub-subshifts also have entropy s?

A subshift is a subset $X$ of $A^\mathbb{N}$ or $A^\mathbb{Z}$ (with $A$ finite), such that $X$ is topologically closed and closed under the shift operation. The shift operation is defined by ...
16
votes
1answer
1k 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 ...
-2
votes
1answer
124 views

“logical distance” link algorithmic complexity to statistical information [closed]

Someone mentioned what I think was referred to as 'logical distance'. My hard drive crashed and I dont have the link anymore. I do recall that I ran across it on this site, in response to linking ...
2
votes
0answers
145 views

Reference for and Properties of the $alpha$-entropy

Let $T : X \to X$ be a continuous map on, say, a compact metric space $X$. Let $\mu$ be an invariant borel measure. Under suitable conditions, a result of Brin and Katok states that $\mu$-almost ...
1
vote
1answer
116 views

order of convergence of the conditional entropy (2)

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g_n(X_n)$, then by Fano's inequality ...
3
votes
1answer
149 views

Example of Girsanov change of density with finite relative entropy, but with infinite integral over squared changed drift

Let $(\Omega, (\mathcal F_t), \mathbb P)$ denote the usual Wiener space where $\Omega = C[0,\infty)$, etc., and where $(W_t)_{t \geq 0}$ denotes the Wiener process. Let $Z \in L^1(\mathbb P)$ with $Z ...
3
votes
0answers
97 views

Is there a known generalization of the Schmidt decomposition based on a maximal set of “locally orthogonal” vectors?

I came across the following unusual generalization of the Schmidt decomposition in my work, which I describe below. I would like to know if this structure has been studied before so I can read more ...
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 ...
30
votes
2answers
2k views

An Entropy Inequality

Let $X,Y$ be probability measures on $\{1,2,\dots,n\}$, and set $K=\sum_i\sqrt{X(i)Y(i)}$ so that $Z:=\frac{1}{K}\sqrt{XY}$ is also a probability measure on $\{1,2,\dots,n\}$. How can we prove the ...
4
votes
3answers
565 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$. ...
3
votes
3answers
1k views

The relations between the Perelman's entropy functional and notions of entropy from statistical mechanics

I am looking for the relations and analogies between the Perelman's entropy functional,$\mathcal{W}(g,f,\tau)=\int_M [\tau(|\nabla f|^2+R)+f-n] (4\pi\tau)^{-\frac{n}{2}}e^{-f}dV$, and notions of ...
0
votes
1answer
116 views

order of convergence of the conditional entropy

Let $X_n$ be a random variable distributed on $A_n:=\{1, \ldots, n\}$ and $g_n\colon A_n \to A_n$ such that $\Pr\big(X_n \neq g_n(X_n)\big) \to 0$. Putting $Y_n=g(X_n)$ then by Fano's inequality ...
11
votes
1answer
666 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
2answers
533 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 ...
2
votes
1answer
491 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 ...
0
votes
0answers
378 views

Calculating entropy of adjacency matrix using eigenvalue decomposition?

How to calculate entropy using the eigenvalues when the eigenvalues are negative? Is there a simple relation between the entropy of a matrix and its characteristic polynomial?
3
votes
2answers
171 views

Estimate entropy of a binary process in terms of decay of correlations

Suppose $( X_{n} )$ is an ergodic binary process with $$ \mathbb P(X_{n}=1)= \mathbb P(X_{n}=0)=\frac 12. $$ Naturally the entropy (rate) $h(X)$ of $X=(X_{n})$ satisfies $$ h(X)=\lim_{n\to\infty} ...
9
votes
1answer
1k views

What's the maximum entropy probability distribution given bounds [a,b] and mean?

What is the continuous probability distribution that maximizes entropy, given only the bounds of the random variable [a,b] and the mean mu of the probability distribution? For example: if a=0, b=1, ...
2
votes
0answers
133 views

A.G. Vitushkin's “Easily representable families of functions” - can it be generalized?

Background In his monograph "Estimation of the complexity of the tabulation problem" (translated into English as "Theory of the Transmission and Processing of Information") Vitushkin studies ...
2
votes
2answers
256 views

probability measures with entropy equal to nonnegative number

Is it true that for a given nonnegative number, there exists a measure-theoretical entropy value (supremum of entropies of all partitions under a measure-preserving transformation) that equals this ...
4
votes
1answer
408 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} ...
4
votes
2answers
289 views

Maximum entropy priors in infinite dimensional spaces

Is there an extension of maximum entropy probability distributions for function spaces? For $\mathbb{R}^n$ and discrete spaces, there is much literature about this problem under names such as ...
0
votes
1answer
221 views

Entropy of inverse map for endomorphism case on surfaces

Hi, I know that in the diffeomorphism case the measure entropy of the T:M^{2}-->M^{2} (M smooth Rimannian surface) will be the same as the measure entropy of T^{-1}. But i need to know about the ...
3
votes
1answer
771 views

Convergence of Markov chains in terms of relative entropy

Consider a finite state, irreducible Markov chain with a rate matrix $Q$ and a stationary distribution $\pi$. Suppose the chain starts with the initial distribution $p$ at time $0$, then at time $t$ ...
3
votes
1answer
182 views

Ising entropy of a finite L_1 x L_2 lattice

We know the entropy per site of the 2-d Ising model from Onsager's solution. Has anybody also calculated the entropy for a finite rectangle of size L_1 x L_2 with periodic boundary conditions (i.e. on ...
5
votes
1answer
759 views

Bounding the entropy of a convolution

Say we have a function $f:\mathbb{Z}_2^n \to \mathbb{R}$, such that $\sum _{x\in \mathbb{Z}_2^n} f(x)^2 = 1$ (so we can think of $\{ f(x)^2\} _{x\in \mathbb{Z}_2^n}$ as a distribution). It is natural ...
4
votes
2answers
822 views

Is there a simple relation between the entropy of a matrix and its characteristic polynomial?

Assume $M$ is an invertible positive matrix of rank $N$. The Von Neumann entropy $H$ of a matrix $M$ with eigenvalues $\{ \lambda_n \}$ is $H[M] = -\sum_{n=1}^N \lambda_n \ln \lambda_n$. In ...
1
vote
0answers
160 views

Entropy of factors of Bernoulli schemes

Let $X$ be a Bernoulli scheme. A factor $\psi: X \to Y$ is finitary if for almost every $x \in X$ there exist integers $m \leq n$ such that the zero coordinates of $\psi(x)$ and $\psi(x')$ agree for ...
1
vote
0answers
57 views

Information amount of fuzzy data transfer [closed]

Suppose we have binary channel from which we are able to receive zeroes and ones. We also know apriory probability $p$ of receiving "1". Then we can calculate information amount of each digit $q$ we ...
10
votes
2answers
1k views

Proving a messy inequality

EDIT: After much work I was able to reduce the inequality to a single variable function which I need to show is non-positive. That function is (for $0\leq p\leq\frac{1}{2}$) $$\frac{p^2(\log(p))^2 - ...
2
votes
0answers
310 views

Does this inequality of negative relative entropy and quantum relative entropy hold?

Hello, everyone! Question I have a question about the relationship between general relative entropy and general quantum relative entropy: Given a unit vector $|i\rangle$ and two Hermitian matrices ...
8
votes
2answers
363 views

Entropy conjecture for distributions over $\mathbb{Z}_n$

Suppose we have two independent random variables $X$ (with distribution $p_X$) and $Y$ (with distribution $p_Y$) which take values in the cyclic group $\mathbb{Z}_n$. Let $Z = X +Y$, where the ...
1
vote
0answers
252 views

Incremental computation of a conditional entropy

Is it possible to compute a conditional entropy (see the two following formulas) in an incremental manner ? That is, the sets C and K are not fix: each time we have a new element c, set K may increase ...
1
vote
1answer
152 views

asymptotic behaviour of the entropy and degeneracy

For each $n \in \mathbb{N}$ let $X_n$ be a random variable taking its values in a finite set $E_n$ with $P(X_n=x_n)>0$ for all $x_n \in E_n$. Say that $X_n$ is asymptotically degenerate if ...
4
votes
1answer
541 views

Low degree polynomial approximation for the entropy function

Let $X$ be a discrete random variable with possible values $\{x_1,\ldots,x_n\}$, and let $p$ denote the probability mass function of $X$. In addition, denote $p_i=p(x_i)$. The entropy of $X$ is ...
1
vote
1answer
384 views

existence of finitely additive measures with zero entropy

Let $X$ be a countable set and $\mathcal M(X)$ be the set of finitely additive probability measures on $X$. If $\mu\in\mathcal M(X)$, I define the entropy of $\mu$ to be $$ ...
3
votes
1answer
246 views

Compact group extension of a zero entropy system.

Suppose $T: X \to X$ is a continuous map and $\mu$ a $T$-ergodic probability measure over the Borel sets of $X$. Now, suppose $K \subset \mathrm{Hom}(X)$ is a compact group of measure-preserving ...
11
votes
1answer
1k views

System with invariant measure, but no ergodic measure.

Question Examples of continuous transformations $T: X \to X$ such that the family of invariant probability measures $M(T)$ is NOT empty but there is no ergodic measure ($E(T) = \emptyset$). Notice ...
10
votes
3answers
793 views

Supremum amongst Kolmogorov-Sinai entropies: ergodic or just invariant measures.

Cases where $sup_{\mu \in E(T)} h_\mu(T) \neq \sup_{\mu \in M(T)} h_\mu(T)$. Background For a topological space $X$, let $T: X \to X$ be a continuous application. Then, call the set of ...
0
votes
1answer
398 views

closed form expression for Rényi entropy for multivariate Gaussian distributions

Is there any closed form expression for Rényi entropy of a set variables with multivariate Gaussian distribution?
0
votes
1answer
326 views

Robust entropy-like measure for analyzing uncertainity

I'm looking for a measure to analysis the uncertainty observed in a set of variables (with multivariate Gaussian distribution). So, I've tried conventional Shanon entropy (differential entropy) which ...
7
votes
1answer
6k views

How to compute KL-divergence when PMF contains 0s?

From the Wikipedia page on Kullback-Leibler divergence, the way to compute this metric is to utilize the following formula: The way I understand this is to compute the PMFs of two given sample sets ...
6
votes
1answer
248 views

A geometric/topology notion of Typical Sequences? Power of typical sequences in multiuser channels?

The idea of Typical sequences(http://en.wikipedia.org/wiki/Typical_set) is a crucial concept in Shannon's proof of the Noisy channel coding theorem. Unfortunately the notion is not sufficient to ...
8
votes
1answer
2k views

Entropy of the Ising model

Consider the standard Ising model on $[0,N]^2$ for $N$ large. By that I mean the square-lattice Ising model without external field, inside an $N$-by-$N$ square. What is its entropy for $N$ large? It ...