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)

0
votes
1answer
135 views

Need help in understanding state transition diagram of a convolutional coder. How are the output bits calculated?

Have a look at the above figure. I am confused in how the output bits are calculated. e.g. according to my understanding a state transition from 00 to 10 (with input bit 1) should produce output 10 ...
0
votes
2answers
177 views

Cover information theory 7.21 tall, fat people

I am stuck on Thomas Cover information theory 2nd edition, problem 7.21 Fat, tall people. The problem is like following: 7.21 Tall, fat people. Suppose that the average height of people in a room is ...
7
votes
2answers
289 views

What is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression?

What is the connection between Boltzmann's entropy expression and Shannon's entropy expression? Shannon's entropy expression: $$ S= -K\sum_{i=1}^np_i\log (p_i) $$
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 ...
0
votes
0answers
50 views

decreasing capacity of channel

I have a question regarding the capacity of a channel Consider a channel given by the transition probabilities $p(y|x)$ with capacity $C$. Now a friendly statistician offers to preprocess the output ...
2
votes
1answer
391 views

Conditional Independence and Mutual information

I have a question concerning conditional independence. According to wikipedia (yes, maybe not the best source) two random variables are conditionally independent given a third if $$p(x,y|z) = ...
1
vote
2answers
1k views

Fano's inequality explained intuitively?

I am now reading through a book to understand Fano's inequality, but I remember my professor explaining it in a certain way that made it seem so logical. I will go office hours as soon as possible, ...
2
votes
1answer
556 views

Graph Entropy - What is it?

I am having trouble getting some intuition as to what graph entropy measures. The definition that I have is that given a graph $G$, $H(G) = \min_{X,Y}I(X ;Y)$, where $X$ is a uniformly random vertex ...
3
votes
2answers
296 views

Markov chains for beginners, how to think about them?

So this is what my book states: Random variables $X,Y, and Z$ are said to form a Markov chain in that order denoted $X\rightarrow Y \rightarrow Z$ if and only if: $p(x,y,z)=p(x)p(y|x)p(z|y) $ ...
2
votes
2answers
493 views

Random process, stochastic process explained intuitively?

So I've read the definitions online and this is what I understood. $X(t)$ is a random process for $t>0$ and we can think of it as being a random variable at any given time $t=t_0$. For example, ...
1
vote
1answer
263 views

$I(X;Y;Z)$ and $I(X,Y;Z)$?

Anyone can conceptually explain what the difference is between $I(X;Y;Z)$ and $I(X,Y;Z)$? where $I(X;Y;Z)=I(X;Z)+I(Y;Z/X)$ Basically, what the semicolon and coma mean in mutual information? In ...
1
vote
2answers
288 views

“by definition A and B R.V are independent means that: $p(A∪B)=p(A)+p(B)$ right?” No, absolutely not right.

Can someone please explain why? Isn't $p(a,b)=p(a)*p(b) $ equivalent to $p(A∪B)=p(A)+p(B)$? If not can you please give a counterexample or something? Thanks a lot!
2
votes
1answer
147 views

I.I.D what does this stand for?

So almost everywhere in the book it's written "random variables are IID", what does this mean? I think it means independent and identically distributed but not sure. So by definition A and B R.V are ...
2
votes
1answer
39 views

Error correcting binary partition

Let's say I have a collection of $2^n$ labeled objects, and I want to find one of them. If I can ask yes-no questions about it, binary partition would immediatly lead us to the desired object in $n$ ...
1
vote
1answer
105 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
38 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
34 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
123 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
1answer
230 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 ...
5
votes
1answer
193 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. ...
3
votes
1answer
513 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
881 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
86 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
148 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
126 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
177 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 ...
1
vote
1answer
355 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 ...
6
votes
3answers
585 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
141 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
43 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 ...
3
votes
0answers
174 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
291 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
254 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
233 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
196 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
36 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 $ ...
4
votes
1answer
235 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
126 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
77 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
38 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
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 ...
2
votes
0answers
145 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
262 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
129 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
61 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 ...
7
votes
1answer
343 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 ...
4
votes
2answers
436 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
117 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
54 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 ...
4
votes
1answer
162 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 ...