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)

4
votes
1answer
67 views

Joint Probability from Marginal Probabilities

$X, Y_1, Y_2$ are random variables with (possibly) different finite alphabets. For given conditional probability mass functions $\mathbb{P}(Y_1|X)$ and $\mathbb{P}(Y_2|X)$, is it always possible to ...
0
votes
1answer
78 views

Normalized Mutual Information results in log(0) with non-overlapping clusters - how to deal with that?

I want to evaluate how well my flat soft clustering method works, compared to a gold standard. After some research I found that Normalized Mutual Information would most likely be a good measure, for ...
1
vote
1answer
553 views

Is there any software package to calculate the entropy, information content, mutual information, etc?

Provided a p.f. of a discrete random variable, or a joint p.f. for several random variable, is there any software package to calculate the entropy, joint entropy, information content, mutual ...
2
votes
0answers
41 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 ...
5
votes
3answers
371 views

What does the -log[P(X)] mean in the calculation of entropy?

The entropy (self information) of a discrete random variable X is calculated as: $$ H(x)=E(-log[P(X)]) $$ What does the -log[P(X)] mean? It seems to be something like ""the self information of each ...
2
votes
0answers
32 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
0
votes
0answers
53 views

Hamming code with an additional parity bit

Suppose we use Hamming Code with additional parity bit (Aka Hamming code [8,4]). I was asked to complete the following: Given a codeword: Number of 1's is even, and there's (at least) an error ...
1
vote
0answers
2k views

Calculating minimum hamming distance of a code

We use hamming code of (7,4,3); Given 4 bits of information, we'll add 3 bits of parity, and one more parity bit for the 7-bits code. Given $x_3,x_5,x_6,x_7$ $x_1 = (x_3+x_5+x_7) \mod 2$ $x_2 = ...
1
vote
0answers
79 views

Using mutual information to estimate correlation between a continuous variable and a categorical variable

As for the title, the idea is to use mutual information, here and after MI, to estimate "correlation" (defined as "how much I know about A when I know B") between a continuous variable and a ...
2
votes
1answer
45 views

symmetry of additive channel's mutual information

Suppose we have an additive noise channel: $Y = X + Z$, where $Z$ is noise, independent of $X$. So we can write the mutual information as: $I(X;Y) = h(Y) - h(Y|X) = h(Y) - h(Z)$. We can also write ...
0
votes
1answer
58 views

Encoding a channel with Huffman Code

I have a random source which is with no memory and have this alphabet (A,B,C). Each symbol in the alphabet has a probability ( A = 0.5, B= 0.25, C = 0.25) It's given that each message including ...
3
votes
3answers
585 views

Is Standard Deviation the same as Entropy?

We know that standard deviation (SD) represents the level of dispersion of a distribution. Thus a distribution with only one value (e.g., 1,1,1,1) has SD equals to zero. Similarly, such a distribution ...
2
votes
0answers
84 views

Finding the mean and the variance of a martingale using concentration inequalities

I am trying to find the mean and the variance of a martingale defined as the maximized likelihood ratios over some finite parameter space. The way I want to do this is through Azuma's inequality (or ...
2
votes
1answer
38 views

Is it true that $H(X|Y)=H(Y|X)$?

I have some difficulties with the question whether $H(X|Y)=H(Y|X)$? From my knowledge $I(X;Y)=H(X)-H(X|Y) = H(Y)-H(Y|X)$ so $H(X|Y)=H(Y|X)$ only when $H(X)=H(Y)$ The question is whether it's ...
0
votes
1answer
42 views

Connection between Boltzmann entropy and Kolmogorov entropy

what is the connectivity between Boltzmann's entropy expression and Shannon's entropy expression? mentions a realtionship between Shannon entropy and Bolltzmann entropy. Is there a ...
2
votes
0answers
42 views

Kullback–Leibler divergence with elements that are $0$

I have a problem that I need to calculate Kullback–Leibler divergence, but the problem is that I have some elements that are $0$. Is there a way that I'm able to deal with situations like that? I know ...
0
votes
3answers
115 views

Calculating probability in a Markov Chain

Suppose I have this Markov chain: And suppose that: $P_{AA} = 0.70$ $P_{AB} = 0.30$ $P_{BA} = 0.50$ $P_{BB} = 0.50$ I realize that $P_{AA} + P_{AB} = P_{BA} + P_{BB}$ but when I simulate I'm ...
4
votes
0answers
88 views

Dividing a deck of cards using only imagination

The idea came up from a discussion I had with my friends. Suppose we want to play a game using a deck of cards, and we can't use any physical materials. If we are intelligent enough, we can remember ...
1
vote
0answers
111 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 ...
2
votes
0answers
60 views

Information Entropy Applied to Complexity Theory

I was just wondering whether or not information entropy has significant applications to complexity theory. I ask because of a simple example I thought of. It comes from a riddle. Suppose you had 8 ...
1
vote
1answer
50 views

locally linearize a CDF

I have a sequence of discrete CDF's that converge to continuous CDF. Assume we call it $F_n(x)$. If say at some point, say $R$, $F_n$ is differentiable, then we can write $F_n(R+\xi) \approx ...
0
votes
1answer
30 views

KL-divergence with zero probability?

Suppose $P(X=1)=P(X=2)=1/2$ and $P(Y=1)=1$. Then $$D(Y||X)=\log\left(\frac{1}{1/2}\right)+0\cdot\log\left(\frac{0}{1/2}\right).$$ If we consider ...
0
votes
1answer
37 views

information content of a quadratic surd

how much information is required to construct the equation: $$ X^2 - 2=0 \; ? $$ suppose, in a spirit of seasonal festivity, we squander a few further bits, and pamper ourselves with the additional ...
4
votes
3answers
187 views

Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries ...
2
votes
0answers
42 views

Upper bound of mutual information in a Markov chain

Consider binary random variables $X$ and $V$ with marginal distributions $p$ and $\pi$ respectively and also the conditional distribution $p(X=x\mid V=v)=q(x\mid v)$, where $x\in\{-b,b\}$ and ...
1
vote
0answers
96 views

Distributing partially known data between n parties

Assume that $n = 2r+1$. There are $n$ elements $a_1,a_2,\ldots,a_n$ from a finite field $\mathcal{F}$, and $n$ parties. Each party knows the values of at least $r+1$ elements out of those $n$ ...
1
vote
1answer
33 views

Proving the monotonicity of a recurrence.

Define the following recurrence for $n = 1, 2, \cdots$ $T(n) = ( 1 - \operatorname{H}(\frac{1 - P^{\frac{1}{n}}}{2}))^n$ where $0 < P < 1$ is a constant, function $\operatorname{H}(\cdot)$ is ...
1
vote
0answers
65 views

Negative exponential/ exponential power distribution between 0 .0 and 1.0?

Note: I'm not very familiar with distribution and higher level math Heyho, I'm currently looking for a way to generate random values between 0.0 and 1.0 with an exponential power or negative ...
1
vote
0answers
33 views

How to define a utility of an information source?

This is a more specific (and, hopefully, clearer version of a previous question). The utility of discovering the value of a random variable $X$ can be defined to be its information content. When ...
2
votes
0answers
28 views

Fastest decaying probabilities with infinite entropy

A well known theorem of analysis is that there is no slowest rate of divergence of a series. "Completely irrelevantly," we know that there exists probabilities (e.g. $\mathtt{Const}/(n\log^2 ...
0
votes
0answers
36 views

How to define “compound entropy”

Entropy measures the "surprise" one experiences when uncovering a the actual value of a random variable as $$-\sum_i p_i \log_2 p_i$$ E.g., if we observe Red 8 ...
1
vote
1answer
91 views

Mutual information and additivity under independence?

So I've been trying to figure this out since I saw it quoted in a paper. Suppose $y$ and $z$ are two independent variables. Is it true then that $I(x;y) + I(x;z) \leq I(x:y,z)$? My intuition is that ...
3
votes
0answers
46 views

Prove that communication protocol complexity less than $n\epsilon$

Alice and Bob get as an input words $x$ and $y$, which consist of $0$ and $1$. Length of $x$ is $n$ and length of $y$ is $2n$. They want to know if the word $x$ is subword of word $y$. For example, ...
0
votes
1answer
72 views

Code for specific case [Information Theory]

I have a channel where the probability of sending a $0$ and receiving a $1$ is $P_e$, sending $0$ and receiving $0$ is $1-P_e$, sending $1$ receiving $0$ is $P_e$, sending $1$ receiving $1$ is ...
1
vote
0answers
24 views

Does this quantity have a meaning or relation to something else?

$X$ is a discrete random variable taking values in $\{0,1,2,3,\ldots\}$ with a probability mass function $p_X(n)$. Let $$U_k(X)=\sum_{n=k}^\infty\sqrt{np_X(n)p_X(n-k)}$$ where $k$ is a positive ...
0
votes
1answer
16 views

Question about flipping terms in matrix multiplication in proving that $h(N_n(\mu , K))=\frac{1}{2}\log(2 \pi n)^n |K|$

So in my book, it is written: Let $X_1,X_2,...,X_n$ have a multivariate normal distribution with mean $\mu$ and covariance matrix $K$ and $\textbf{X}=(X_1,X_2,...,X_n)$ The above isn't really ...
2
votes
0answers
87 views

Relation between entropy of variable and entropy of conditioned variable

Let $X$ be a discrete random variable, and let $E$ be an event on the same probability space as $X$. Let $X_E$ be $X$ conditioned on the event $E$. Is there a general relationship between the Shannon ...
1
vote
0answers
35 views

Independent transformation of probability measures

I have a pair of dependent random variable $(\theta, X)$ where $\theta\in K$ for a compact subset $K\subset\mathbb{R}$ and $X\in\mathbb{R}^d$ with marginals $P_{\theta}$ and $P_X$. I want to ...
2
votes
0answers
34 views

Is it true that $\sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}$?

Given $q \in \mathbb N$, $q\geq 2$ is it true that \begin{equation*} \sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}? \end{equation*} Here $H_q(x) = x\log _q(1/x) + (1-x)\log _q(1/(1-x))$ is the ...
1
vote
0answers
19 views

Orthogonality of parameter space

Folks, I have a basic information theory question. I am fitting a highly parameterized model to some data. In general: $$ y = \sum\limits_{i=1}^{13} \alpha_i X_i $$ Currently I use gradient descent ...
2
votes
0answers
132 views

Explanation of Radon-Nikodym derivates wrt to probabilities

I am currently working in communications, where a lot of work is done via probability calculations (densities and such). As I am not a mathematician, I do have a quite hard time understanding one ...
1
vote
0answers
77 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 ...
0
votes
1answer
27 views

$Y$ is a function of $X$: making an inference based on the markovity of $ X$

In the information theory book by Cover and Thomas it is written: if $X$ is markov and $Y$ is a function of $X$ then: ...
0
votes
2answers
52 views

Can infinite random sequences be asymptotically compressed?

A number $0.5<p<1$ is chosen at random and given to two people A and B whom are allowed to communicate before beeing separated. A is then given a sequence S of N random bits where each bit has ...
2
votes
1answer
64 views

Confused about notation: difference between $\prod_{i=1}^np(x_i)$ and $\prod_{i=1}^np(x)$

In my information theory book by Cover and Thomas, at the beginning of the channel coding theorem, it's written: "Each entry in this matrix" (the matrix of the randomly generated code) "is ...
2
votes
1answer
96 views

3-bit sensors — A question about Hamming distance in signals

I came across this question on Willy Wu's riddle site You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. ...
2
votes
0answers
135 views

Information content of universal sentence

What is the information content of a sentence S like 'one has a successor'. To me, it looks like if we assume no a priori knowledge, both S and it's negation will have equal probablity 1/2. This is ...
0
votes
2answers
181 views

Hamming Code Error Detection

I am learning few things about hamming code and error detection so my question may sound stupid. So i know that lets i ahve (7,4) hamming code and i made transpose of parity check matrix H(t). Now say ...
1
vote
1answer
136 views

Bounding mutual information given ROC curve statistics

When evaluating a binary classifier, the basic data are as in this contingency table, where rows represent groundtruth value and columns represent the estimated value: $$ \begin{matrix} & + ...
3
votes
1answer
201 views

Solid Angle Calculation - Understanding a formula

I'm currently reading a paper and try to understand this one formula. The problem is: In an n dimensional space. A cone with half-angle $\theta$ is given (the top of the cone is in the origin). We are ...