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

learn more… | top users | synonyms

4
votes
0answers
87 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 ...
4
votes
2answers
89 views

Are there logarithm functions for arbitrary rings?

The logarithm function for $\mathbb{R}$ satisfies $\log xy = \log x + \log y$ whenever both $\log x$ and $\log y$ are defined. Are their conditions for a ring $R$ which guarantee the existence of a ...
1
vote
1answer
83 views

Entropy vs predictability vs encodability

Imagine there's a guessing game where a series of binary symbols are presented and a human must decide quickly if the symbol is the same as the previous or different. There's a property of the ...
0
votes
0answers
142 views

Replace a continuous probability distribution with a discrete one

Say one wants to fit a curve $f(x)$ to a set of noisy data points $(x_i, y_i)$. If the error for each point $y_i$ is assumed to be normally distributed with variance $\sigma_i^2$, one wants to find ...
2
votes
1answer
50 views

Shannon inequalities

I have some difficulties in showing the relationship between mutual information $I(X; Y |Z)$ and $I(X; Y)$? What is larger?
2
votes
0answers
57 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 ...
1
vote
0answers
61 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$ ...
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 ...
1
vote
0answers
69 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, ...
3
votes
1answer
42 views

Do the pth powers of $p$-norms define the same partial ordering on the set of all probability distributions for all $p>1$?

Consider the $p$-th power of the Schatten $p$-norm $||q||_p$ of a probability distribution $q$ , ie, the function $\sum_j q_j^p$, where $\sum_j q_j = 1$ and $q_j \geq 0$. For fixed $q$ and $p>1$ ...
0
votes
1answer
51 views

i.i.d binary random variable question

Suppose there are i.i.d. binary random variables $X_i \sim X$ with distribution $P(X=1) = 0.75$ and $P(X=0) = 0.25$ i) For $n=5$ and $e=0.1$, which sequences fall in the typical set $A_e^n$? What is ...
1
vote
0answers
91 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| ...
0
votes
1answer
203 views

Approximating probability of success of Bernoulli trials using Kullback–Leibler divergence

In "Probabilistic Graphical Models" book by Daphne Koller and Nir Friedman they have the following approximation of probability of r successful outcomes of N Bernoulli trials: $P(S_N=r)\approx ...
3
votes
1answer
220 views

Definition of the Entropy

I have a question regarding definition of entropy by expected value of the random variable $\log \frac{1}{p(X)}$: $H(X) = E \log \frac{1}{p(X)}$, where $X$ is drawn accordingly to the probability ...
1
vote
1answer
215 views

Bits in a coin-toss experiment

This is not homework but an actual problem. We flip a fair coin ten times. This gives A$_1$ to A$_{10}$. Each coin toss = 10 bits. We flip another fair coin ten times. This gives B$_1$ to ...
0
votes
1answer
214 views

Entropy Problem: mutual information

I have a problem about entropy and mutual information that I have attempted, but would like feedback on. 30% Boas 20% Anaconda 50% Cobra Half of the Cobras were medium sized, and the other half were ...
1
vote
1answer
79 views

About the differential entropies of well-known continuous distributions

Assume that the continuous random variable $X$ has a distribution (in a closed form expression) with differential entropy $h(X)$. Q) Then, is it true for any continuous distribution that the ...
1
vote
2answers
289 views

How to prove the following entropy formula?

Could anyone show me a proof or redirect to a source where the following entropy equation is proved? =) $$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$ Thank you!
3
votes
1answer
121 views

convergence of entropy and sigma-fields

This question is related to this one. Let $(X_1, X_2, \ldots)$ be a sequence of random variables such that each $X_n$ takes its values in a finite space, say $\{0,1\}$, and the $\sigma$-field ...
3
votes
2answers
114 views

Calculate entropy with n values

I trying to solve a quiz that asks the following. The variable $X$ can be the values $1,2,3,...,n$ with the probabilities $\frac{1}{2^1}, \frac{1}{2^2},\frac{1}{2^3},...,\frac{1}{2^n}$ How can I ...
7
votes
2answers
334 views

Can the entropy of a random variable with countably many outcomes be infinite?

Consider a random variable $X$ taking values over $\mathbb{N}$. Let $\mathbb{P}(X = i) = p_i$ for $i \in \mathbb{N}$. The entropy of $X$ is defined by $$H(X) = \sum_i -p_i \log p_i.$$ Is it possible ...
0
votes
1answer
664 views

equivalence between uniform and normal distribution

The principle of insufficient reason says that all outcomes are equiprobable when we have no knowledge to guess otherwise. I understand this and that this corresponds to uniform distribution. However, ...
5
votes
1answer
275 views

Pinsker $\sigma$ Algebra

Let $(X,A,\nu)$ be a probability space and $T:X\to X$ a measure-preserving transformation. The Pinsker sigma algebra is defined as the lower sigma algebra that contains all partition P of measurable ...
3
votes
1answer
144 views

Question about entropy

Let $(X,A,\nu)$ be a probability space and $T\colon X\to X$ a measure preserving transformation $\nu$. Take a measurable partition $P=\{P_0,\dots,P_{k-1}\}$. Let$I$ be a set of all possible ...
6
votes
0answers
103 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%. ...
9
votes
1answer
2k views

Entropy of a binomial distribution

How do we get the functional form for the entropy of a binomial distribution? Do we use Stirling's approximation? According to Wikipedia, the entropy is $\frac1 2 \log_2 \big( 2\pi e\, np(1-p) \big) + ...
2
votes
1answer
65 views

What is the CONCEPT when we speak of maximum entropy?

What is an intuitive interpretation of the concept of maximum entropy? I want to understand this concept better but what I'm finding is too "advanced" right now. Can anyone simplify it ... imagine I'm ...
1
vote
1answer
154 views

Increasing entropy of random walk in regular graph

Let $P$ be a transition matrix of a random walk in an undirected regular graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by $$H(\pi)=-\sum_{v \in ...
1
vote
1answer
25 views

Entropy contribution from variable length segment of a sequence

If I have a sequence which is comprised of one of 10 prefixes, one of 5 suffixes and a variable length middle, how do I compute the entropy of the sequence? Using Shannon-Entropy $Hs= ...
0
votes
1answer
209 views

Entropy of a Binary Source with a random until first other result is given.

I was studying for an exam and i found an interesting exercise, but very very bad redacted. A coin is thrown until the first face is found. Denote as X the number of throws required. And find: a) ...
1
vote
0answers
197 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$ ...
5
votes
2answers
2k views

Entropy of matrix

I am trying to understand entropy. From what I know we can get the entropy of a variable lets say X. What i dont understand is how to calculate the entropy of a matrix say m*n. I thought if columns ...
2
votes
1answer
54 views

Parameter optimization in probabilistic models

Task: Suppose we model a variable $y = Wx + \mu$ as a linear transformation of $x$ plus some Gaussian noise $\mu\sim\mathcal N(0,\sigma I)$. Our aim is to minimize the estimation error of $x$ given ...
0
votes
2answers
181 views

Prove that entropy is maximized when probability is $1/n$

How can be proven that the entropy of a dice roll is maximized when the probability of each of its $6$ faces is equal, $1/6$?
3
votes
1answer
152 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
0
votes
1answer
691 views

Kullback-Leibler distance between 2 probability distributions

Can I determine the Kullback-Leibler distance $$ D_{\mathrm{KL}}(P\parallel Q)=\sum_{i}\ln\left(\frac{P(i)}{Q(i)}\right) P(i) $$ between the following probability distributions? ...
1
vote
1answer
88 views

Conditional entropy of sum of random variables

How can be proven that for random variables $A$ and $B$, and $C = A + B$, $$H(C\mid A) = H(B\mid A).$$ Also, would it be possible to determine if $H(C)$ would be greater than $H(A)$?
1
vote
1answer
98 views

What branch of the Math can help me with this?

I would love to focus on the branches of the Math that can help me with: generation of entropy, i suppose that most of the works are based on statistic since even a big part of the cryptographic ...
5
votes
3answers
769 views

Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$

I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough. My approach was ...
1
vote
1answer
167 views

Entropy of Zipf and Zeta Distributions

I was wondering how to show entropy of the zeta distribution. It is: $$ H_\mathrm{zeta}(X) = \sum_{k=1}^\infty \frac{1/k^s}{\zeta(s)} \log(k^s \zeta(s))$$ The entropy of the zipf distribution is: ...
1
vote
2answers
1k views

How are Huffman encoding and entropy related?

The inherent unpredictability, or randomness, of a probability distribution can be measured by the extent to which it is possible to compress data drawn from that distribution. $$ \text{more ...
0
votes
1answer
84 views

Checking efficiency of randomness with entropy

I was going through random numbers and found that the randomness of certain observations is measured by the entropy as given in here. Here, $p(x_i)$ is the probability that $x_i$ will take place. But ...
1
vote
1answer
98 views

Entropy of Order Statistic

Consider $n$ independent and identically distributed random variables $ \{X_i\}_{i=1,...n} $ with support on some interval $[a,b]$ and its $n$'th order statistic $\max_{i \in \{1,...n\}} X_i$ . The ...
3
votes
1answer
319 views

Notation of cross entropy

I have a question regarding a notation that seems to be very usual. For starters, cross entropy is defined by: \begin{align}H(X, q) &= H(X) + D(p||q) \\ & =-\sum_x p(x)\log_2 q(x)\end{align} ...
1
vote
0answers
227 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
2answers
1k views

Calculating conditional entropy given two random variables

I have been reading a bit about conditional entropy, joint entropy, etc but I found this: $H(X|Y,Z)$ which seems to imply the entropy associated to $X$ given $Y$ and $Z$ (although I'm not sure how to ...
2
votes
0answers
160 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
1answer
275 views

Explicit examples of smooth entropy computation

Smooth classic entropies generalize the standard notions of entropy. This smoothing stands for a minimization/maximization over all events $\Omega$ such that $p(\Omega)\geq 1-\varepsilon$ for a given ...
10
votes
3answers
2k views

Is there a “most random” state in Rubik's cube?

Is there a state in Rubik's cube which can be considered to have the highest degree of randomness (maximum entropy?) asssuming that the solved Rubik's cube has the lowest?
1
vote
3answers
454 views

Minimum number of bits required to store the order of a deck of cards

Assume I have a shuffled deck of cards (52 cards, all normal, no jokers) I'd like to record the order in my computer in such a way that the ordering requires the least bits (I'm not counting look up ...