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

learn more… | top users | synonyms

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 ...
7
votes
0answers
126 views

Approximation of Shannon entropy by trigonometric functions

Define Shannon entropy by $$I(p) = -p \log_2 p$$ Numerical experimentation shows that $\sin(\pi p)^{1-1/e}$ is a good approximation to $I(p) + I(1-p)$ on $[0,1],$ never differing by more than 3.3%. ...
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 ...
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 & ...
4
votes
0answers
90 views

A combinatorial problem.

Let be $(X, \mathbb{A}, \mu)$ a measure space, a partition of $ X $ is a disjoint family $\xi=\{P_1,\ldots,P_k \}$ of measurable sets such tath $\bigcup P_i=X\pmod0).$ If $\xi=\{P_1,\ldots,P_k ...
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 ...
3
votes
0answers
90 views

Topological applications of topological entropy

I just learned topological entropy during a lecture about dynamical systems, and I wonder whether there exist purely topological applications of it.
3
votes
0answers
116 views

Can one define informational content of a mathematical expression?

At least in physicist's thinking, information, vaguely, is something that allows one to select a subset from a set. Say, a system can be in states A and B, we have done a measurement on it ...
3
votes
0answers
108 views

Reference for a transformation

Has the (Lebesgue-)ergodic transformation $T: \{0,1\}^{\mathbb{N}} \to \{0,1\}^{\mathbb{N}}$ defined by $T(x(0)x(1)x(2)\cdots) = x(1)x(3)x(5)\cdots$ been well-studied? If so, where? Does it have a ...
3
votes
0answers
92 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
3
votes
0answers
352 views

Can I map entropy values to a common range so that they are comparable?

I am using the standard Shannon entropy formula for calculating the entropy of a system at different states. The system has a different number of possible outcomes at each state, in other words the ...
2
votes
0answers
15 views

Graph Entropy - A Tractable Measure to Measure Distinguishability of Neighbourhoods

Given a labelled directed graph G, I am interested in a measurement of G that captures how distinguishable arbitrary connected sub graphs of G are. Labels may repeat and as such two or more different ...
2
votes
0answers
39 views

Topological Entropy of $T$ on subset $Y\subset X$

Let $X=\left\{0,1,2\right\}^{\mathbb{Z}}$ and on it the following dynamics described by $T\colon X\to X$ as follows: A 1 becomes a 2, a 2 becomes a 0 and a 0 becomes a 1 if at least one of its two ...
2
votes
0answers
85 views

Is it true that $\sup_{y'\in Y'}h_d(T,U^{-1}(y'))=0$, i.e. $h(T')=h(T)$? (Bowen, Topological entropy)

First I have to give the background to my question: Let $X=\left\{0,1,2\right\}^{\mathbb{Z}}$ and on it the map $T\colon X\to X$ which describes the following dynamics: For $x\in X$, which is a ...
2
votes
0answers
58 views

What is the variance of self-information (or surprisal)?

The self-information of an outcome $x_i$, or surprisal, is defined as: $$ I(x_i)=-\log P(x_i), $$ where $P$ means probability. This way, the Shannon entropy can be seen as the "average" or "expected" ...
2
votes
0answers
26 views

Finding the Legendre transform of an “entropy type” functional

I want to find the Legendre Transform of $$T(f) = \int_{\mathbb{R}^2} f \log \left(\frac{f}g{}\right) \, dx$$ on a set $H_M = \{ f: f \ge 0 \text{ and } \int_{\mathbb{R}^2} f =M\}$, where g is some ...
2
votes
0answers
75 views

Shannon Entropy, prove $H(Wx)=H(x)+\log|\det W|$

I'm doing an essay on ICA (independent component analysis), and I could use some help. In essence, ICA is an algorithm that minimizes the entropy of $n$ $1$-dimensional random variables, but to show ...
2
votes
0answers
53 views

Shannon Entropy Continuity Constraint

I have the following problem: I want to find the probability density $p$ which maximizes the Shannon entropy \begin{equation} S := - \int_{x_b}^{x_c} dx ~ p(x) \log (p(x)) \end{equation} under the ...
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 ...
2
votes
0answers
49 views

Joint entropy maximization with a constraint

So I have 2 random variables X and Y, where X can take on values {0,1,2,3} and Y can take on values {0,1,2,3,4}. I need to maximize H(X,Y) subject to the constraint that P(X≠Y)=0.5. This also gives ...
2
votes
0answers
64 views

Entropy of sum of random variables

Let $x_1,x_2,\dots,x_n$ by random variables which take the values $0$ or $1$ with $P(x_i = 1) = p_i$ and $P(x_i = 0) = 1-p_i$, where $0 \leq p_i \leq 1$ for $i=1,2,\dots, n$. Let $$X= \sum_{i=1}^n ...
2
votes
0answers
27 views

probability subspaces that make entropy function equal to a constant value

Given the entropy fucntion: $$ H = -\sum_i^n p(i) \ln(p(i))\,.$$ where $p(i)$ are probabilities and $n=4$, I would like to know all the points in the probability space that make $H = k$, being $k$ a ...
2
votes
0answers
183 views

How many code words if average code length equals entropy

I've been given a proof of the following: If $q\geq2$, then there is a source $S$ with $q$ symbols, and an instantaneous $r$-ary code $C$ satisfying $L(C)=H_r(S)$ if and only if $q\equiv 1 ...
2
votes
0answers
57 views

Entropy of a measure-preserving transformation

Let $T:X \rightarrow X$ be a measure-preserving transformation of the probability space $(X,B,\mu)$. ($X$ is a topological space). If $K\subset X$ is a compact and invariant set, show that ...
2
votes
0answers
66 views

Computing Relative entropy?

I am doing a project for my CS class and I was wondering if the following would work. I have 50 different people who have rated the same 50 books. The rating system is as follows: negative 5 = hate ...
2
votes
0answers
169 views

rényi entropy as a derivative

Let $x=(x_i)$ be a probability measure on $\{1,\ldots,n\}$. Suppose $1<p<\infty$. The Rényi entropy of $x$ is $$ H^p(x)=\frac{1}{1-p}\log \sum_{i} x_i^p. $$ Does there exist a formula for ...
1
vote
0answers
13 views

Are there any other measures of complexity for a continuous map than topological entropy?

Let $X$ be a compact topological space and $T\colon X\to X$ be continuous. In order to say something about the complexity of $(X,T)$ there is of course the notion of topological entropy of $T$, ...
1
vote
0answers
12 views

Entropy of a 2D function versus 1D function.

I am a novice in information theory so this is more of a question seeking pointers to ideas/references to think further on the thought. I want to make concrete the idea that a function of two ...
1
vote
0answers
39 views

Intuition for Entropy over Fractals

Is there intuition for "mathematical" entropy. I know that physical entropy tracks the order in a dynamical system, for thermodynamics. As entropy goes up, general randomness and disorder goes up. ...
1
vote
0answers
9 views

Integrating entropy on an arbitrary boundary

Entropy, denoted as H, is: $$ H = -\int_a^b p\ln(p) dx $$ where the range a to b is some arbitrary boundary and where p is given by the classic: $$ p(x) = ...
1
vote
0answers
27 views

Cross-entropy minimization - equivalent unconstrained optimization problem

I'm looking at this paper "An Alternative Method for Estimating and Simulating Maximum Entropy Densities" ...
1
vote
0answers
33 views

Proof of a fact about mutual information and entropy

It is needed to prove that for distribution (a, b, c) such that $I(a;b|c) = I(a;c|b) = I(b;c|a) = 0$ exists a random variable $d$ such that $H(d) = I(a, b, c)$ and $a,b,c$ are independent with ...
1
vote
0answers
18 views

Question about history of Entropy

I have started to study Ergodic theory and entropy by some books and lecture notes more than three months but unfortunately I'm not familiar with history of Entropy (I know some thing about name of ...
1
vote
0answers
18 views

Maximum entropy distribution given second order marginals

Let $p(x,y,z)$ be a probability distribution over 3 variables (suppose them discrete, but it shouldn't matter). I know that the distribution with maximal entropy which preserves the first order ...
1
vote
0answers
60 views

Entropy calculation of Fibonacci distribution

For any positive integer $N$, consider the Fibonacci sequence $F_n$ of length $N$. Using $F_n$ we can define a Fibonacci discrete probability distribution as follows: $$p_N(n)=\frac{F_n}{\sum_{k=1}^N ...
1
vote
0answers
42 views

Estimate uncertainty of a function

I have a question about estimate the uncertainty of a function. I have a variable $x$. I assume that I can predict the variable $x$ is followed by a function $f(x)$ such as $$f(x)=\exp(-x^2)$$ Now, ...
1
vote
0answers
53 views

Limit of $\frac{1}{n}\log({n\choose np})$ without using Stirling's formula

I am trying to evaluate the following limit: $$ \forall p\in(0,1) ,\lim_{n\rightarrow \infty} \frac{1}{n}\log{n\choose \lfloor np \rfloor} =H(p),$$ where $\lfloor x\rfloor$ means the greatest integer ...
1
vote
0answers
34 views

Entropy proerty

Let $a,b,c>0$ be distinct postive reals. Define four different probability distributions: $$\mathcal{P}_{ab}:P_{a,ab}=\frac{a}{a+b}=1-P_{b,ab}$$ ...
1
vote
0answers
20 views

Summation methods and entropy

I am aware of the theory of divergent series, but don't know much of it. If you have a text to recommend, I'd be glad to hear it. Suppose I have an infinite-dimensional probability vector $\mathbf{p} ...
1
vote
0answers
26 views

Entropy of Sum vs Difference of Random Variable

I am looking for a proof of the following fact Let X and X' be i.i.d on {0,1,2}(not necessarily uniform). Prove that $H(X + X' mod\;3) \leq H(X - X' mod\;3)$ where $H()$ is the standard Shannon ...
1
vote
0answers
46 views

Calculate $\lim_{n\rightarrow \infty}\frac{\log{\binom{n}{n_1}}}{n}$

We know that $\lim_{n\rightarrow \infty}\frac{n_1}{n}=p$ and $0\leq p\leq 1$. Based on this information I want to calculate $\lim_{n\rightarrow \infty}\frac{\log{\binom{n}{n_1}}}{n}$. Any help? Note: ...
1
vote
0answers
57 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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
1
vote
0answers
172 views

Continous wavelet transform and shannon Entropy.

Note: I have asked the same question on signal processing forum,but didn't get any answer. so it might be more like a math or physics question. Hope you don't consider it as cross-post. I am trying to ...
1
vote
0answers
103 views

what is relative entropy between to random binary string with length of $L_1$ & $L_2$?

I want calculate relative entropy between two strings of binary such as: $L_1:11000100011101001$ $L_2:00101110110111001$ It is primarily when the lengths of two strings is same and in general when ...