The science of compressing and communicating information. It is a branch of applied mathematics and electrical engineering. Though originally the focus was on digital communications and computing, it now finds wide use in biology, physics and other sciences.

learn more… | top users | synonyms (1)

1
vote
1answer
99 views

Is there a way to mathematically describe “surprise”?

Let's say that there are ten people entered into a random drawing, the winner gets some large prize. If I were one of those ten people, and I were to win, then I would be pleasantly surprised. If ...
1
vote
1answer
37 views

Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$

Let $X,Y, and \space Z$ be random variables. Let $A$ be a subset of $U$ such that $p(X \in U)=1$ Is $p(X \in A|\frac{Y+Z}{2}) = p(X \in A|Y,Z)?$ Do these two expressions represent the same thing? ...
1
vote
1answer
33 views

Show that entropy $(p1,…,pi,…,pj,…,pm)$, < entropy $(p1,…, (pi+pj)/2 ,…, (pi+pj)/2 ,…,pm)$.

Show that the entropy of the probability distribution, $(p1,...,pi,...,pj,...,pm)$, is less than the entropy of the distribution $(p1,..., (pi+pj)/2 ,..., (pi+pj)/2 ,...,pm)$. I don't understand what ...
2
votes
1answer
92 views

Notion of Relative Entropy

I do not understand the notion of relative entropy. Relative Entropy. $D_{KL}(P||Q) = \sum_{i}^{}P(i)\log \frac{P(i)}{Q(i)}$. I try to get some intuition why it looks the way it looks. I see that it ...
5
votes
0answers
114 views

A tight lower bound for the entropy of the XOR of two random variables

Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings. Assuming $I(X;U) \le ...
0
votes
0answers
67 views

Average min-entropy and statistical distance

Let $X$ be a random variable over a set $\mathcal{X}$. The min-entropy of $X$ is defined as $$ H_{\infty}(X) := -\log(\max_x \mathbb{P}_{x\leftarrow X}[X=x]). $$ For a pair of (possibly correlated) ...
5
votes
1answer
125 views

Card drawing algorithm

I want to know whether there is an algorithm for randomly and securely drawing cards from a deck. I was thinking about a way to play deck-based games online with no trusted party and no way to cheat. ...
1
vote
1answer
296 views

Maximum entropy joint distribution from marginals?

How does one find the maximum entropy joint distribution of two random variables X and Y given their marginal probability mass functions? I know: I have the marginals, meaning p(x) and p(y) are ...
1
vote
1answer
363 views

Is maximizing entropy equivalent to minimizing the defined variance?

Assume there is multi-set of some integers : $D = \{a_1,a_2,\cdots,a_{N-1}\}$ such that $\sum_i a_i = A$ we can build a discrete probability distribution by dividing elements of set by $A$, i.e. $p_i ...
0
votes
1answer
75 views

How much information do you get if you draw a red card?

I'm trying to figure out what this question is asking and what it is I'm trying to calculate exactly. I'm told: You have cards 2-5 of each suit, except the 2 and 3 of the red cards. So 12 cards ...
1
vote
1answer
92 views

Is mutual information transitive?

Suppose A, B and C are random variables. Given that the mutual information between A and B is very large and also the mutual information between B and C is very large, could we conclude that the ...
2
votes
1answer
81 views

Transformation of mutual information to probability distribution

Given the upper bound for mutual information of random variables $X$ and $Y$, $I(X;Y)\leq L$, what can we say about their joint distribution? I mean for example if $L=0$, then we know $p_{XY}(A\cap ...
1
vote
0answers
124 views

KL divergence of multinomial distribution

Consider $q(x)$ be a Multinomial distribution over $\{1, \ldots, k\}$ with parameters $\{\theta_1,\ldots, \theta_k\}$. And p(x) over $\{1,\ldots, k\}$ with distribution $p(x)=\frac{1}{k}$. Then what ...
0
votes
1answer
124 views

confused about joint mutual information

I have a difficulty understanding 'joint mutual information' The expressions like $I(X,Y;B)$ are not understood. Is there an good example to understand joint mutual information? Actually, I want to ...
0
votes
0answers
18 views

Applications of dissimilarity measures

A dissimilarity measure of two probability measures $p$ and $q$ is defined as a non negative function $D(p,q)$ which is $0$ iff $p=q$ a.s. The KL divergence is an example of such a function. There are ...
6
votes
3answers
259 views

What is information theoretic entropy and its physical significance?

I have learned entropy in my information theory classes. The definition I got from text books was the average information content in a message sequence etc. But in one of the MIT videos related to ...
2
votes
2answers
105 views

Understanding notation difference between mutual information and information divergance

The mutual information is defined on random variables. That is, $I(X;Y)$ denotes the mutual information between random variables $X$ and $Y$. On the other hand, the the Kullback-Leibler divergence is ...
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 ...
2
votes
0answers
121 views

Joint distribution between a uniform random variable and a function which is “almost” independent from it

Motivation Let $f(\cdot)$ be a (possibly randomized) function, such that for any random variable $X$ (taking values from a finite set $D$), $X$ and $f(X)$ are statistically independent. Let $U, U_1, ...
1
vote
1answer
215 views

Is maximizing the Shannon differential entropy equivalent to minimizing the predictability and/or minimizing the maximum density?

For a real-valued, 1-dimensional, continuous random variable X with density f(x), I am trying to determine if maximizing the Shannon differential entropy of f(x) is mathematically equivalent to ...
2
votes
2answers
176 views

Is alpha divergence a convex divergence measure?

Alpha divergence is defined as following : $$ D_\alpha(p||q) = \frac{1}{\alpha (1-\alpha)} \left( 1- \int _x p(x)^{\alpha} q(x)^{(1-\alpha)} dx \right) $$ if the distributions are restricted to ...
0
votes
1answer
170 views

Information theory entropy equation

I'm studying information theory, and working through this document. On page 17, it shows that, with the function that gets the entropy of a probability $I$ and a probability $p$, that $I(p^a) = a * ...
1
vote
1answer
113 views

Shrink a Chain of Decimal Digits

Assume that we have a 100-digit number, made of 0 to 9. Is there a way we can actually 'shrink' this number? As a first thought, I tried to decompose the number to prime factors. But, in many cases, ...
0
votes
1answer
26 views

Bound on maximum of a fourier transform

Could someone show me why the following relation holds? $ \max_{\lambda} \vert f(\lambda)\vert \leq \sum_{-m}^m\vert t_k\vert $ where $ f(\lambda) $ is the fourier transform of the sequence $ ...
2
votes
0answers
136 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
1answer
72 views

Entropy and Shearer's Inequality

I have two questions both related to Shearer's Inequality: 1) When is equality attained in Shearer's Inequality? One trivial instance is when the random variables are all independent. Is this the ...
1
vote
0answers
65 views

Maximum of the expectation of a concave function

Let's have a function $f(x, \theta)$, and some probability distribution on $x$. Let's say I have found $\theta^* = \operatorname{argmax}(f(E[x], \theta) $, and $f$ is concave in $x$. I would like to ...
1
vote
0answers
35 views

Hiking trip distribution

I have a real life problem. My friends and I are going on a hiking trip and there's a bunch of items (mostly food) that we want to distribute among us so everyone carries approximately equal weight. ...
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 ...
1
vote
0answers
77 views

Entropy Rate of a sequence of Random Variables with Distributions related to Primes

Let us consider a stochastic process $\mathcal{X}=\{X_i\}_{i \in \mathbb{N} }$ where $X_i$'s are independent and $X_i$ is distributed as $$X_i=p_k \ \mbox{w. p.}\frac{p_k}{\sum_{l=1}^{i}p_l},\ 1\leq ...
3
votes
1answer
129 views

Positivity of Renyi Mutual Information

The differential Renyi entropy for a probability distribution is given by $H_q(P(X))=\frac{1}{1-q}\log\int p^q(x)dx$. In the limit of $q\to 1$, it reduces to the usual Shannon entropy. We can write ...
0
votes
1answer
93 views

questions in channel capacity

Q) Suppose we have a set of t coins, all but two of which have uniform weight $0$. and two counterfeit coins have different weights$>0$. If one can only use a spring scale, what is the ...
1
vote
1answer
55 views

approximate $[0, 1]$ continuous function with 2d basis.

everyone. I've been thinking of this problem when reading papers about Fourier series. I think I can state my question as follows: in the interval $[0, 1]$, I want to approximate an unknown ...
6
votes
1answer
230 views

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one ...
3
votes
2answers
251 views

Intuition of information theory

I am reading the book "Elements of Information Theory" by Cover and Thomas and I am having trouble understanding conceptually the various ideas. For example, I know that $H(X)$ can be interpreted as ...
2
votes
0answers
107 views

Lower bound on uncertainty reduction

Let $T$ be a set of tuples such that each score tuple $s(t_i)$, $t_i \in T$ is uncertain (i.e., not known deterministically). The score $s(t_i)$ can be represented as a uniform probability density ...
0
votes
1answer
50 views

Optimization of entropy for fixed distance to uniform

Suppose that I know that a probability distribution with $n$ outcomes is very close to being uniform (that is: $\forall i,p_i=\frac{1}{n}$), and in particular for $n\epsilon\ll 1$ the distribution ...
3
votes
1answer
116 views

Source coding theorem - optimum number of bits?

The source coding theorem says that information transfer with variable length code uses less bits and is equal to the entropy of the distribution. It also says that there is no code that uses lesser ...
0
votes
1answer
108 views

concatenation of channels

Assuming I have 2 channels: BSC => Z Z=> BSC the first channel is a concatenation of the BSC channel and then the Z channel. the second channel is a concatenation of the Z channel and then the BSC ...
2
votes
1answer
88 views

Properties of Entropy

When someone writes $H(X_1, X_2, X_3) = H(X_1) + H(X_2\mid X_1) + H(X_3\mid X_2, X_1)$, how should that last term be interpreted/read? As the joint entropy between 2 variables where variable 1 is ...
3
votes
0answers
53 views

Is there a conditional version of the asymptotic equipartition property?

Let $X_i$ be independent random variables with $\operatorname{Pr}(X_i = x) = p_x$, and let $F_n$ be the empirical frequency distribution of $X_1, \ldots, X_n$: that is, $(F_n)_x$ For any frequency ...
2
votes
1answer
76 views

Conditional Probability, Lack of Dependence on a Parameter

I am trying to understand why the following is true: $$ p(f(Y) = f(y) \mid Y = y) = p(f(Y) = f(y) \mid X = x, Y = y) \qquad \ldots \text{(Eq. 1)} $$ where $Y$ and $X$ are random variables, and $f(Y)$ ...
6
votes
3answers
301 views

Another Information Theory Riddle

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. In a magic trick, there are ...
2
votes
2answers
213 views

How can you use a (fair) coin to draw straws among 3 people? (Information Theory) [duplicate]

The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay. How can you use a (fair) coin ...
0
votes
0answers
70 views

Intregral of exponential of Shannon Entropy Function

Here I am going to ask a similar question as rde asked , that is what is the integral of exponential of entropy function. That is what is the value of $F[H(x)]=\int_{-1}^{+1} e^{ikH(f(x^2))} dx$ ...
1
vote
1answer
92 views

Information content associated with an outcome

I have the following exam question for a multimedia exam in college: Assume that you roll a single ordinary six-sided die twice, and observe that the second number rolled is greater than the ...
2
votes
4answers
167 views

What exactly is a probability measure in simple words?

Can someone explain probability measure in simple words? This term has been hunting me for my life. Today I came across Kullback-Leibler divergence. The KL divergence between probability measure P ...
0
votes
1answer
109 views

How information works?

I am really confused after reading wikipedia... What I don't get is how can something "bring" information, and in mathematics, how a mathematical object (like a set) can "have" information. For ...
1
vote
0answers
42 views

Hellinger distance between 3-parameter Weibull distributions

I found Wikipedia to have listed Hellinger distance between pairs of 2-parameter Weibull distributions sharing the same shape parameter http://en.wikipedia.org/wiki/Hellinger_distance However, I ...
0
votes
1answer
47 views

What is being maximised in the channel capacity formula?

The channel capacity formula is given as such: $$C=\max_{p(x)}I(X,Y)$$ Does this mean that it is the maximum probability multiplied by the mutual information, or is something else being maximised ...