# Tag Info

5

Yes, Information Theory is a branch of mathematics, although its practitioners are often found in departments of Electrical and Computer Engineering or Computer Science.

3

Have you read about Maxwell's demon? Maxwell realized that if it was possible to track the trajectories of moving particles, and open and close a shutter and just the right times, it would be possible to locally increase a system's temperature without doing any work on the system. The idea would be to selectively allow the hottest particles to move into a ...

3

There is a theorem that no comparison sorting algorithm can have a worst-case running time better than $O(n\log n)$, and this limit is often referred to as an information-theoretic limit on the running time. (For example, see Leiserson et al. Introduction to Algorithms (2001) pp. 181 and preceding, or Knuth The Art of Computer Programming 3 (1998) pp. ...

2

In general, if $f:\mathbb{R}^n\to \mathbb{R}$ is concave, then for any matrix $A \in\mathbb{R}^{n\times n}$, $f(Ax)$ is also concave in $x$, and the proof uses this fact, i.e., the fact that the concave function of a linear combination is still a concave function. Proof: For any $0\leq \lambda\leq 1$, and any $x_1,x_2 \in \mathbb{R}^n$, $$f\left(A\left( ... 2 From our definition of conditional entropy:$$ H(Y|X) = \sum_{x}p_{X}(x)H(Y|X=x) = -\mathbb{E}[\text{log}p(Y|X)] $$We know the chain rule which states that:$$ H(X,Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) $$so$$ H(Y|X) - H(X|Y) = H(Y) - H(X) = 0 $$by the fact that X and Y have the same distribution. Of course this is clear from the symmetry. 2 There is definitely some general relation between the two subjects within complexity theory, and as likely one of the few people who know what both fields entail, I've not come across anything specific or even general linking the two fields in a direct manner. I've seen some research that ties the two fields separately to other areas in an indirect manner, ... 1 First lets state the claim. Claim: I(X;Y)=D(p(x,y)||p(x)p(y)) is concave in p(x) for fixed p(y|x) and convex in p(y|x) for fixed p(x). One can write the following: I(X;Y)=H(Y)-H(Y|X) where H is the entropy function. The entropy functions can further be written as$$H(Y)=-\sum_y p(y)\log(p(y)) \ \text{ and } \ H(Y|X)=-\sum_x p(x)\sum_y ...

1

That $D(u||v)$ is convex in the pair $(u,v)$ means that $$D(u_{\lambda}||v_{\lambda}) \le \lambda D(u_{1}||v_{1}) +(1-\lambda)D(u_{2}||v_{2})$$ (here $u$ and $v$ and some probability functions, with $u= \lambda u_1 +(1-\lambda) u_2$, etc) Then $$I(X_{\lambda};Y_{\lambda}) = D(p_{\lambda}(X,Y)||p_{\lambda}(X)p_\lambda(Y))$$ where (as shown in the text) ...

1

Is $p(Y|X_{n'})$ the conditional probability of $Y$ given $X_{n'}$? Then, $p(Y|X_{n'})$ is a non-negative random variable (more precisely, a non-negative measurable function with respect to the sigma-algebra generated by $X_{n'}$). So, if $p(Y|X_n)>0$, we have P \left( p(Y|X_{n'})>p(Y|X_n)\bigg|X_n,Y ... 1 The text is rather sloppy... First, it's I(X;Y) , not I(X,Y) (the notation is important). Second, "the mutual information between X and itself is 1" made me quiver, until I understood that it actually meant "the normalized mutual information". Third, the factors inside the square root lack a minus sign - (yes, they cancel in the multiplication, but ... 1 You can do this in seven measurements. Label the wires in A from 0 to 99 iusing binary numbers. Then for your first measurement, tie together all the A wires with a 1 in bit 0 (the odd wires). Your measurement tells you which of the wires in B are connected to some odd wire in A. (Because any wire in B that is connected to an odd wire in A will show a ... 1 In general, there is no rule as to whether conditioning decreases or increases mutual information. I(X;Y) can be less than, equal to, or greater than I(X;Y|Z) depending on the joint distribution of X,Y and Z. In case of the Markov chain X \to Y \to Z, the latter is true: \begin{align*} I\left(X;Y|Z\right) &= H\left(X|Z\right) - ... 1 There are such pmf coincidences, applicable for any set of candidates with more than 2 candidate values other than the maximal entropy all-value-equal entropy. For your example, consider (although there is an entire 1-parameter family of iso-entropic distributions) the distrbution with p(X) = [0.24301892,0.24301892,0.51396216]  This has the identical ...

Only top voted, non community-wiki answers of a minimum length are eligible