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
0answers
10 views

Mutual information: Indirect

Maybe this is a very trivial question but my own answer to it is rather based on intuition only. Consider two random variables A and B. Their mutual information is I_AB. Now, I want to obtain ...
0
votes
0answers
18 views

a problem involving binary entropy function

let $\alpha<1/2$ such that $2^{H(\alpha)}\le 2^{1-\epsilon}$,when $H$ is binary entropy function. how can i prove that then we have: $2^{n(1-\epsilon)}\ge \sum\limits_{i\le \alpha n } {n \choose ...
0
votes
0answers
29 views

Calculating the Shannon information of drawing equal no. of cards

One card is drawn each from a $k$ deck of 52 cards where $k$ is a multiple of $52$. I need to prove that information of an outcome where each card appears the same number of times tends to ...
0
votes
1answer
45 views

Explain Kraft McMillan inequality and how it is applied.

I am going through some questions and answers regarding Information Theory and I found this question and its solution. Can some one explain this solution to me. We would like to encode a sequence of ...
-3
votes
0answers
16 views

what is the mathematical semantic of information (in the context of entropy theory)? [closed]

can you discuss the semantic of this definition. "information is change in the entropy” can you validate this mathematically and if possible refer this definition to any relevant literature
5
votes
0answers
57 views

Solving a Matrix DE involving the KL divergence

If we let $U_\mu$ be a vector field that associates a direction vector $U_\mu(\pi)$ with each $\pi \in $ unit simplex. Each such vector field is associated with a system of ODEs: $$ \pi'(u) = ...
1
vote
2answers
31 views

What's theoretical maximum information compression rate?

Let's say I've got a random bit sequence s and a reversible function f(s), for which the following statement ...
1
vote
1answer
31 views

Calculating Shannon Entropy for DNA sequence?

I'm following the formula on http://www.shannonentropy.netmark.pl/calculate to calculate the Shannon Entropy of a string of nucleotides [nt]. Since their are 4 nt, ...
0
votes
1answer
113 views

Is there a term in graph theory called 'GRAIL'?

I've been a talk with a PhD student about some graph issue and told me about GRAIL graph and have drawn it for me as you see in the picture, however, I try to generalize so-called "Grail graph" to ...
0
votes
1answer
23 views

Is mutual information convex in the joint distribution?

Assume some joint distribution $P(X,Y) = P(Y|X)P(X)$. It is well know that, for fixed $P(Y|X)$, mutual information is a concave function of $P(X)$ and, for fixed $P(X)$, a convex function of $P(Y|X)$ ...
0
votes
0answers
15 views

Probability Distribution on the Simplex with support on the faces

I am looking for a parametrized distribution on the (probability) $K$-simplex with support on its $(K-1)$-faces. I.e. say $(x_1,...x_{K+1})$ are the coordinates of the simplex with $\sum_jx_j=1$, then ...
2
votes
1answer
29 views

Why does $-\sum_x p(x) \log p(x) + \sum_x \int \mu(x,y) \log \mu(x,y) dy = \sum_x \int \mu(x,y) \log \mu(y \mid x) dy$?

If we write $p(\cdot)$ for a discrete probability function and $\mu(\cdot)$ for a continuous density function, then why does the following hold: $$-\sum_x p(x) \log p(x) + \sum_x \int \mu(x,y) \log ...
2
votes
2answers
52 views

Differential Entropy

I'm a little temporarily confused about the concept of differential entropy. It says on wikipedia that the differential entropy of a Gaussian is $\log(\sigma\sqrt{2\pi e})$. However I was thinking as ...
0
votes
1answer
33 views

Distance between two p.m.fs

I am stuck with the following problem from research. Is there any existing distance measure which can compare two probability mass functions with different support? For eg. for pmfs $p_1$ and $p_2$ ...
0
votes
3answers
74 views

Where do extra dimensions in gradient come from?

The gradient of a scalar function $f\colon \mathbb{R}^n \to \mathbb{R}$ is a vector-valued function $\nabla f\colon \mathbb{R}^n \to \mathbb{R}^n$. Since applying a function can't increase ...
1
vote
1answer
20 views

Stationarity and Ergodicity vs. Memorylessness

A (discrete) memoryless information source is (usually) defined as a collection of random variables that are independent and identically distributed. My question is, does memorylessness imply ...
0
votes
0answers
22 views

The “first order” rate distortion function

Suppoer we have a random source $(X_n; n \geq 1)$ taking values in some source alphabet $A$ to be compressed int another alphabet $\hat{A}$, with respect to a distortion function $\rho: A \times ...
2
votes
1answer
26 views

Probability measure, probability density function or probability event ? Are they different?

My question is regarding the difference between probability measure and probability of event. Recently I have read an information theory paper that considered a channel modeled by probability density ...
0
votes
0answers
15 views

Why $H_{V^* \cup W^*} > H_{V \cup W}$ if $H_V$ denotes entropy of language

Let $W \subseteq X^*$ be an infinite language over a finite alphabet $X$, and define ($|w|$ denotes the length of $w \in W$) $$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
1
vote
1answer
24 views

Shannon information for a set of 3 equally probable elements?

How to calculate entropy as a number of binary choices for a set of three equally probable elements? The Shannon's formula gives $\log_2(3)=1.585$. But any interpretation of binary choices gives me ...
2
votes
1answer
45 views

Entropy of $f(x)=1$

Let $f(x)$ be a probability mass function $f(x) = 1$ on $x = [0,1]$, and entropy defined as $$H(p(x)) = -\int p(x) \log_2(p(x)) \, dx$$ where $p(x)$ is a pmf. Unless I've made an arithmetic error, the ...
1
vote
1answer
18 views

Finding unique rules for a finite number of initial steps, using Information theory

Is there a unique way to determine which rule provides the sequence that matches a finite number of initial steps, choosing the rule that needs the least amount of information to be described? ...
0
votes
1answer
25 views

Possible to eliminate mutual information between random variables by reducing the number of them?

Say you have a set of random variables that have some mutual information structure. Could be that they all have nonzero MI between them. Or perhaps there are some clusters of variables with ...
2
votes
0answers
26 views

Departure from uniformity in a continuous (time) distribution

I know how to quantify the departure from uniformity ( or a uniform distribution) for discrete distributions. Assume you have a distribution set of P: ...
2
votes
1answer
26 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
0
votes
0answers
36 views

Mutual Information: Are these two equations equal?

I'm working with Multivariate Mutual Information (MMI), specifically with three variables $(X,Y,Z)$, applied to RNA sequences. The MMI equation that I use for three variables is based on entropy ...
0
votes
2answers
41 views

Partition-based entropy of a sequence

The entropy $H$ of a discrete random variable $X$ is defined by $$H(X)=E[I(X)]=\sum_xP(x)I(x)=\sum_xP(x)\log P(x)^{-1}$$ where $x$ are the possible values of $X$, $P(x)$ is the probability of $x$, ...
0
votes
1answer
27 views

How to calculate entropy from a set of samples?

entropy (information content) is defined as: $$ H(X) = \sum_{i} {\mathrm{P}(x_i)\,\mathrm{I}(x_i)} = -\sum_{i} {\mathrm{P}(x_i) \log_b \mathrm{P}(x_i)} $$ This allows to calculate the entropy of a ...
1
vote
0answers
38 views

Derivative of the Kullback Leibler Divergence

If: $$ H (\pi(t)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log \frac{\pi_i(t)}{\mu_i(t+1)} $$ How do I interpret: $\nabla H(\pi(t) | \mu(t+1) )$? Would it be the vector: $$ \left ( \frac{\partial ...
0
votes
1answer
48 views

Noiseless Channel Capacity

Nyquist theorem proves that a signal of $B$ bandwidth, in order to be sampled correctly thus avoid aliasing, has to be sampled with a $f_c > = 2B$. When it comes to calculating the capacity of a ...
1
vote
1answer
46 views

Is conditional entropy ever taken to be a random variable?

In probability theory, the conditional expectation $E(X|Y)$ and variance $V(X|Y)$ er usually taken to be random variables, st. the value of $E(X|Y)$ depends on what value $Y$ ends up taking. I've ...
1
vote
1answer
22 views

Finding C from $\Delta C$

Define: $\Delta A(t) = A(t+1)-A(t)$ and let $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log ...
1
vote
0answers
64 views

Trellis Diagram - Viterbi decoding

I have the trellis diagram below which is used as Viterbi decoder. The coded message is the sequence of bits at the bottom of the picture. My question is this. t=0:The decoder starts from state 00 ...
1
vote
0answers
25 views

Vector Differential in specific form

for the operator: $\Delta A(t) = A(t+1)-A(t)$, let : $$ \Delta C = \sum^{T-1}_{t=0} [~~H(\pi(t+1)~|~\mu(t+1))~~ - ~~H(\pi(t)~|~\mu(t+1))~~] $$ Where $H (\pi(t+1)|\mu(t+1)) = \sum^n_{i=1}\pi_i(t) \log ...
0
votes
1answer
18 views

Shannon-Hartley theorem for other bases

The Shannon-Hartley theorem is given with terms referring to a binary signal. What if a channel does not transmit via binary, but instead in another system, such as ternary or base-4?
0
votes
2answers
17 views

Information limit for digital signal

Wikipedia give the Shannon-Hartley theorem as: $$ C = B \log_2 \left(1+ \frac{S}{N}\right) $$ Where $S/N$ is the signal to noise ratio, with each quantity measured in watts. What if the channel is ...
0
votes
1answer
39 views

Kullback - Leibler Divergence and the Triangle Inequality

The KL Divergence, or relative entropy for two probability distributions $p,q$ on $\Omega$ is defined as: $$ H(p|q) = \int_{\Omega} p(\omega) \log \frac{p(\omega)}{q(\omega)} d\omega $$ This is a ...
0
votes
1answer
23 views

A doubt regarding KL-divergence for estimating a distribution

Suppose given a probability distribution $q$. I'm trying to estimate it by $p$ such that the KL-divergence between $p$ and $q$ is minimized. Now which one of the two: $KL(p||q)$, $KL(q||p)$ should be ...
1
vote
0answers
27 views

Mutual information as a fraction of entropy?

Suppose I have two (discrete) random variables $(X,Y)$ with some joint distribution $P$. The mutual information $I(X;Y)$ is informally defined as the reduction is the remaining entropy in $X$ once the ...
1
vote
1answer
27 views

Function of Determinant convexity via information theoretic methods

In Cover and Thomas, "Elements of Information Theory", second edition, I encountered this question: Let $K$ and $K_0$ be symmetric positive definite matrices of same size (s.p.d.m). Then show that ...
1
vote
3answers
62 views

Combining Markov chains

If the following Markov chain relations hold: $$X \rightarrow Y \rightarrow Z,$$ $$Z \rightarrow W \rightarrow Y,$$ can we combine them to have $$X \rightarrow Y \rightarrow Z \rightarrow W ...
0
votes
1answer
52 views

Campbell's Source coding

In the usual Shannon's source coding problem one chooses code words that minimize $E[L]:=\sum_i p_il_i$ over all $L=(l_1,l_2, \dots), l_i\ge 0$ such that $\sum_i e^{-l_i}\le 1$ (Kraft inequality), ...
0
votes
1answer
50 views

What modification is this of the notion of Renyi divergence?

Given two probability distributions $P$ and $Q$ over the same outcome and event space (assume finite if needed) one defines their Renyi divergence as $D_\alpha (P \vert \vert Q) = \frac{1}{\alpha -1} ...
3
votes
1answer
53 views

Fano's Inequality Proof

For an information theory class, I am studying the proof for Fano's inequality, i.e.: $H(P_e) + P_elog(|X|) \geq H(X|\hat{X}) \geq H(X|Y)$ Where $H(X)$ is the entropy of the random variable X ...
1
vote
1answer
23 views

Four Variable Data Processing Inequality

While Solving problems in "Elements of Information Theory" by Cover and Thomas, I found this problem in the last chapter. Let $X \to Y \to (Z,W)$ be a Markov chain i.e. $p(x,y,z,w)= ...
0
votes
0answers
17 views

Optimal decision for sampling a distribution.

I was wondering which probability distribution is best sampled with $\pm\alpha^n, n\in\{1,2,\cdots\}$ for various values of alpha. Sampling means to pick the one which is closest, store the sign and ...
1
vote
0answers
43 views

Weak continuity of K-L divergence function

If $P_n$ and $Q_n$ are two pmf's of a discrete set (say $A$) with common support and $P_n \to P$ and $Q_n \to Q$ where the convergence is pointwise here (even weak would be fine here I guess), then $$ ...
0
votes
1answer
30 views

Mutual Information: How these two equations are equal?

I'm a biologist trying to apply the Mutual Information (MI) to some RNA secondary structure. I know that there exists two MI equation that, mathematically, are equal: $I(X,Y) = \sum_{x,y} p(x,y) ...
2
votes
1answer
43 views

Puzzle: Determining the structure of a bipartite graph

Consider the bipartite graph $G = (X, Y, E)$, with $|X| = |Y| = n$. We can think of $X$ and $Y$ as clusters of $n$ switches on either end of a long hallway. Each switch on one end of the hallway has ...
0
votes
1answer
37 views

Derivation of equation for self information

I am trying to understand how the formula I(x) = -log(p(x)) for self information was derived. From what I have read, 2 constraints were imposed on the properties ...