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

learn more… | top users | synonyms

7
votes
0answers
198 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 ...
6
votes
0answers
93 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
53 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
47 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 ...
4
votes
0answers
86 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
46 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
112 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
107 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
88 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
234 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
34 views

toplogical entropy of general tent map

Measure theoretic entropy of General Tent maps The linked question made me wonder how to calculate the topological entropy of a general tent map. Let $I=[0,1]$ and $\alpha \in ( 0,1)$. Define $T: I ...
2
votes
0answers
45 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
54 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.
2
votes
0answers
32 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
52 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
24 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
128 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
141 views

Non-zero Conditional Differential Entropy between a random variable and a function of it

Let two continuous random variables, where the one is a function of the other: $X\, $ and $\, Y=g\left(X\right)$. Their mutual information is defined as ...
2
votes
0answers
56 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
155 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
16 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
0answers
16 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
28 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
16 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
34 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
27 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
93 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
68 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 ...
1
vote
0answers
24 views

Best path for finding within a radius of x units from this point

Say i am standing at a point and knew there is one thing within a radius of x units from this point. What is best path to find that thing. Best can mean shortest, but the discussion can be more open. ...
1
vote
0answers
38 views

Calculating entropy of Naive Bayes random variables

Suppose a Naive Bayes graphical model with binary random variables is given by $$P(y,x_1,x_2,...,x_n)=P(y)P(x_1|y)...P(x_n|y)$$ Attempting to calculate $I(x_1,...,x_n;y)$ raises the question: how can ...
1
vote
0answers
46 views

Optimization problem in the Von Neumann Entropy

I have a constrainted optimization problem in the Von Neumann Entropy. In a CVX-like syntax the problem goes as follows: given variable $\mathtt{c(n)}$ $$\begin{align} \text{minimize} \qquad & ...
1
vote
0answers
33 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 ...
1
vote
0answers
60 views

convergence of discrete random variables with finite entropy

Let $Z$ be the set of discrete random variables on some probability space. Define the quantity $d(X_1,X_2)=h(X_1 \mid X_2)+h(X_2 \mid X_1)$ between two random variables $X_1, X_2 \in Z$. For $X \in Z$ ...
1
vote
0answers
66 views

convexity of the product of two entropy-like functions

Consider the functions $T_p(q)= \sum_i q_i^p$, where p>1 and q is a finite-dimensional vector satisfying $\sum_i q_i = 1, q_i >0$ (ie, a probability mass function). In information-theoretic terms, ...
1
vote
0answers
90 views

Why is the negative entropy Lipschitz with respect to the $1$-norm (Over)?

Let $\left\|x \right\| = \sum_{i=1}^{i=n}\left|x^i\right|$ and $d\left(x\right)=\sum_{i=1}^{i=n}x^i\ln x^i$ where $x\in R^n $ and $ \sum_{i=1}^{i=n}x^i=1$ How to prove: For all $x, x'$, $$\left| ...
1
vote
0answers
191 views

Mutual Information of Correlated Bivariate Uniform Distribution

We have correlated bivariate uniform distribution, where X and Y have a correlation coefficient $\rho$ and they uniformly distributed in the following rectangle. What is the mutual information of $X$ ...
1
vote
0answers
212 views

How can I determine the upper limit of Shannon Entropy?

I know that the maximum possible Shannon Entropy for an alphabet $X$ is $\log|X|$, where Shannon Entropy is: $$H(X) = - \sum_{x \in X} \; p(x) \log p(x)$$ but how is this upper limit computed?
1
vote
0answers
118 views

Incrementally compute the 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
0answers
285 views

Is conditional entropy a convex function?

A conditional entropy can be expressed in the following way, $H_{V_t}(V_s) = -\sum_{s,t}p(s,t)\log{p_t(s)} = -\sum_{s,t}p(s,t)\log{\frac{p(s,t)}{\sum_{s'}{p(s',t)}}}$ $s$ and $t$ are defined ...
1
vote
0answers
97 views

Entropy of a Finite State Transducer

Theorem 7 in Shannon's seminal paper A Mathematical Theory of Communication states: "The output of a finite state transducer driven by a finite state statistical source is a finite state ...
1
vote
0answers
79 views

Showing that Normalized Redundancy is nonreliant on the properties of Bijection and Monotonicity

In information theory, the concept of mutual information states that for two features of arbitrary discretized probability, the following formula holds true: \begin{aligned} I(X;Y) = \sum_{y \in Y} ...
1
vote
0answers
139 views

Inequality involving KL divergence

Following is a part of an answer which was not resolved when I tried to answer a question in mathoverflow. I thought it would be nice to discuss that here. Let $P$ and $Q$ be two distinct ...
0
votes
0answers
24 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
0answers
9 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.
0
votes
0answers
22 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 ...
0
votes
0answers
24 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
0answers
12 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
0answers
38 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
0answers
40 views

Problem with calculating probability of symbols

I've a $100 \times 100$ binary matrix it`s constructed with this probability table : i want to apply extended Huffman on this matrix my idea is to compress each column individually . - so starting ...
0
votes
0answers
14 views

Can we calculate entropy for nonstationary random variables?

Let's assume that $X$ is a discrete random variable, which can take any value from the set $\{x_0,\dots,x_n\}$ with the probability mass function $P(X)$. We can calculate the entropy of $X$ as ...