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)

2
votes
1answer
17 views

Capacity of a Binary Deletion Channel

It is well known that a communication channel with a randomly induced 50% bit error rate has zero capacity but determining the capacity of a binary deletion channel is still an open problem. Why ...
0
votes
1answer
35 views

How come that HSL can contain more information than RGB?

I have noticed weird thing when working with HSL - unlike RGB, it has some blind spots where certain value just does not matter. I'm sure we were taught about this when I had Linear algebra lectures ...
1
vote
0answers
22 views

Kolmogorov complexity of a computer?

Warning: Vague, unclear question ahead. Proceed at your own risk. The Shannon entropy and Kolmogorov complexity give you in broad informal terms how unpredictable a string is and to what degree the ...
1
vote
1answer
30 views

Given a Markov chain $X \rightarrow Y \rightarrow Z$, why is $I(X;Y|Z) \leq I(X;Y)$?

A Markov chain $X \rightarrow Y \rightarrow Z$ is given, where $X,Y,Z$ are random variables characterized by the probability distribution $p(x,y,z) = p(x)p(y|x)p(z|y)$. It follows that $I(X;Y) \geq ...
0
votes
1answer
37 views

What is the exact meaning of $I(X;Y|Z)$ in Information Theory?

I am wondering: is the notation $I(X;Y|Z)$ used to denote the mutual information between probabilities of $X$ and $Y|Z$ or between $X|Z$ and $Y|Z$?
0
votes
1answer
32 views

Which one is bigger $D(P\Vert Q)$ or $D(Q \Vert P)$?

In general the Kullback-Leibler divergence is asymmetric. If $P$ and $Q$ are two distributions $D(P\Vert Q) \ne D(Q\Vert P)$. However, I was wondering if there are situations where we can say which ...
1
vote
2answers
45 views

If $g$ is a function of the random variable $X$, is it true that $H(X) = H(X) + H(g(X)\mid X)$?

I think my homework about entropy is formulated incorrectly. The question is the following: let $X$ be a discrete random variable. Show that the entropy of a function $g$ of $X$ is less than or ...
0
votes
0answers
17 views

Where can I read about Shannon's source compression problem and how to derive $-logP_{X}(x)$ from an optimization problem

I was reading the following question about the measure of information. and in it mentioned that $l_i = log \frac{1}{p_{X}(i)}$ is the solution to "Shannon's source compression problem." I have ...
1
vote
1answer
25 views

Justifying $\log{\frac{1}{P_{X}(x)}}$ as the measure of self information

I was reviewing self information and then came to realize that there is one idea that I have that I believe should be wrong but don't know why. Let self-information associated with a random variable ...
1
vote
1answer
25 views

What is the significance of strictly convex?

I am learning the definition of convex (in a book on information theory). The book says that that if equality holds only when lambda is 0 or 1 then the function is "strictly" convex. ...
1
vote
1answer
23 views

Channel Coding Theorem: What does it mean to find a maximising input distribution?

I seem to have a fundamental confusion regarding the channel coding theorem which I would like to resolve. In the theorem, we say that there exists an input distribution which maximises $I(X; Y)$ and ...
0
votes
1answer
27 views

Highest pairwise Hamming distance between k bitvectors of length n

What is the highest achievable pair-wise Hamming distance $d$ between all possible pairs from $k$ bitvectors each having a length of $n$ bits? The content of each bitvector can be arbitrary, only the ...
0
votes
1answer
13 views

Is there a way to quantify the 'unsortedness' of a given vector/1D array with respect to a reference vector.?

I've been working on a statistical learning problem and seem to have hit a roadblock. It's basically regarding somehow measuring how randomized or unsorted a given vector is, with respect to a ...
1
vote
1answer
28 views

Calculation of polynomial in the finite field

I'm trying to understand the McEliece cryptosystem and I'm looking to this paper http://www.mif.vu.lt/~skersys/vsd/crypto_on_codes/goppamceliece.pdf On page 26 they are calculating syndrome and ...
1
vote
1answer
35 views

Renyi entropy (zeroth order)

I am reading a book on information theory, therein has been introduced Renyi entropy of order $\alpha$ as $S_{\alpha} = \frac{1}{1-\alpha}\log(Tr\rho^{\alpha})$, where $\rho$ is density matrix. It ...
0
votes
0answers
22 views

Explaining of lost probalbity over random loss channel

I am reading a paper about packet loss probability over random loss channel. In this paper, the author give a equation about loss probability as $(1)$. However, I cannot understand the meaning of it. ...
1
vote
0answers
58 views

A probabilty of error calculation

Let's assume I have $N$ binary strings $\{T_1,T_2,\ldots,T_N\}$ of length $L$. All these strings satisfy a minimum hamming distance with respect to a reference binary string R with $\|R\|_1$ ones and ...
0
votes
0answers
15 views

Fewest number of questions to find subinterval

I need some help with the following question: Let $S=${$x_1$,... $x_n$} be a set of $n$ real numbers listed in ascending order: $x_1<x_2<...<x_n$. Given a real number $r$ that exists in ...
4
votes
1answer
35 views

Applications of information theory in economics?

What are some direct applications of information theory in economics theory and/or finance? Any relevant articles, surveys, or book references are appreciated (especially if they are targeted to ...
0
votes
1answer
18 views

High mutual information = (almost) deterministic relationship?

If two random variables $X, Y$ have high mutual information $I(X;Y)$, intuitively does that mean $X,Y$ have almost deterministic relationships, say $Y=f(X)+\epsilon$ where $\epsilon$ is a noise random ...
0
votes
1answer
29 views

What is the sum-capacity for a non-symmetric interference channel for information theorists?

This question is dedicated for people who are experts in information theory. An interesting result for a two user interference channel in information theory, is the sum-capacity to within one bit. It ...
2
votes
3answers
57 views

Code is not cyclic for any q

I have code $C$ over $F_p$ with generator matrix which looks like $G = \begin{pmatrix} 0 &0& 0& 1& 0& 1& 1 &1\\ 1& 0 &0& 0 &1 &0 &1& 1\\ ...
0
votes
0answers
25 views

Information Content of an event and its probability

From a group of candidates, 25% are not suitable for the University admission. As the result of selection process only 75% of these unsuitable students are rejected. Overall 50% of students are ...
0
votes
1answer
36 views

Entropy of noisy signal

We have input signal $X$, the output signal Y and random noise $Z$, then: $$Y=X+Z$$ Of course, the mutual entropy: $$I(Y,X)=H(X)-H(X\mid Y)=H(X)-H(X-Y\mid Y) \geq H(X)-H(X-Y)$$ Could we say that ...
0
votes
1answer
54 views

Conditional Entropy in rolling a dice

A 6-sided die is tossed once. Two events X and Y are defined. X is the event in which an even number comes up and Y is the event in which the number is a multiple of 3. The value of H(X|Y) needs to be ...
2
votes
0answers
39 views

How to deconstruct Shannon Joint Entropy H(X,Y,Z) equation for semi-related variables?

Background The purpose of this is to produce a shuffle correction for Transfer Entropy estimation: TEx->y = H(Xt+τ) - H(Xt) - H(Xt+τ,Yt,Xt) + H(Xt,Yt) In order to produce a shuffling ...
1
vote
1answer
29 views

What does it mean for something to be “more” Gaussian?

I'm currently reading this paper on information theory and the brain. Within the text (p. 16) they say: It is important to note that the above expression [the mutual information between a signal ...
1
vote
1answer
14 views

If gen matrix has even weigth rows, do codewords have even weigth for non binary code?

Is that true that in a non binary code C every codeword has even weight if and only if every row of G has even weight?
1
vote
1answer
18 views

Subset of linear dual code

Hi I need to show that $$C_1 \subseteq C_2 \Leftrightarrow C_2^{⊥} \subseteq C_1^{\perp}$$ In guess I need to use standard form matrices for generator matrix and parity check matrix(also parity ...
0
votes
2answers
25 views

(7,4) Hamming Code with 2 bit errors

I need help proving that a HammingCode with 2 bits flipped can create a new codeword by flipping just one more bit. I worked through the problem and created an example of my own but am having ...
1
vote
1answer
28 views

Channel Capacity of a Cycle Graph

I have the following problem: Given a discrete memoryless channel $Y = X + Z \mod5$, where $X$ is selected from one of 5 symbols (0, 1, 2, 3, 4), $Z$ randomly selected from (-1, 0, 1), and $X$ and $Z$ ...
0
votes
1answer
23 views

prove a theorem about an upper bound of entropy of a random vector

There is a theorem that: if Z is any zero-mean, complex random vector with covariance $E[ZZ^H]=R_z$, then $H(Z)\leq \log|{\pi eR_z}|$, with equality holding if and only if Z has a circularly ...
0
votes
0answers
16 views

Analytical calculation of mutual information of a sine time series

Suppose I have the following time series $$ x_t=\sin(0.02\pi t) $$ and I want to calculate the mutual information $I_{x_t,x_{t-\tau}}$ which by definition is $$ ...
0
votes
0answers
13 views

estimating mutual information via nearest neighbourhood

I am not sure this is the best place to ask this kind of question about discussing the content of a paper. Anyway, here is my question: There is a famous paper from Physical Review E 69, 066138(2004) ...
0
votes
0answers
8 views

Cardinality of Time Sharing Random Variable for Multiple Access Channel

it is well know that capacity of MAC is \begin{align} R_1 \le I(X_1;Y|X_2,Q)\\ R_2 \le I(X_2;Y|X_1,Q)\\ R_1 \le I(X_1,X_2;Y|Q)\\ \end{align} where $|Q| \le 4$. How is the bound on $Q$ derived?I ...
1
vote
0answers
56 views

Information set of a linear code

I am trying to prove a couple of statements about information sets of linear codes, but i am having trouble with these proofs or i am not sure if i understand correct what i should prove. I would ...
0
votes
1answer
29 views

Huffman code with specific source

There is n-ary Huffman code. Source has the following relative frequencies of t symbols: 1, $n$, $n^2$, $n^3$, . . . , $n^{t−1}$, where $t = 1 + k(n − 1)$ for some positive integer $k$. I need to find ...
0
votes
1answer
20 views

Conditional entropy of repetition code over BSC

Consider the channel that takes in a bit, repeats it $k$ times, then sends the result over a binary symmetric channel with transition probability $p$. For example, if $0$ was sent over the channel ...
0
votes
2answers
53 views

Derivative of mutual information

Here is the definition of mutual information $I(X;Y) = \int_Y \int_X p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)} \right) } \; dx \,dy,$ where $x$ and ...
4
votes
0answers
118 views

Convergence of mutual information

Let $P_n (x,y)$ be a sequence of (cumulative) probability distributions defined on $\mathcal{X}\times \mathcal{Y}$ (of arbitrary cardinality), that weakly converges to $P(x,y)$: $$ P_n (x,y) ...
0
votes
1answer
39 views

what is the mutual information of three variables?

mutual information of tow variables is $\displaystyle\sum\sum p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$ what is the mutual information of three variables? is it $\displaystyle\sum\sum\sum ...
1
vote
1answer
105 views

Prove there exist a $p$ so that the inequality holds

I am stuck with the following problem. Given the Gaussian mixture distribution $f(\cdot)$ $$ f(x) = ...
1
vote
0answers
24 views

Minimum of an Entropy based function

This question is a small part of a bigger problem I am working on. Let $h(p)$ be the binary entropy function. That is, for $p \in (0,1)$ $$h(p) = -p\log_2(p) - (1-p)\log_2(1-p)$$ Define the ...
0
votes
0answers
55 views

How to compute the topological entropy of a permutation?

I have a permutation, say as ${4,1,7,2,3,5,6}$, given by its induced matrix. According to this paper (Proposition 11 on p. 82), To compute its topological entropy, one can compute the ...
0
votes
1answer
30 views

What is the meaning of E and d in this formula?

I am trying to learn the information bottleneck method. On slide 15, they give this equation. I think I understand that X is a random variable (but do not understand the meaning of the exponent, n). I ...
1
vote
0answers
71 views

optimization problem gaussian maximizes entropy

Let $X_1, X_2, Z_1$ be random variables and define $$Y=aX_1+bX_2+Z_1$$ I have the following optimization problem of difference of entropies, $$f=\max_{p(x_1x_2)} h(Y) - h(Y|X_2)= \max_{p(x_1,x_2)} ...
1
vote
0answers
29 views

Mutual information between two Gaussian distribution

Suppose we have two variables $x_i$ and $x_j$ with covariance matrices $P_i$ and $P_j$ and cross-covariance $P_{ij}$. I'd like to find the mutual information on them. From reverse engineering of some ...
1
vote
0answers
22 views

KSE and Shannon entropy

Is there a theoretical connection between Kolmogorov-Sinai and Shannon entropies? What is it?
1
vote
1answer
40 views

How many points does it take to identify a low-order polynomial in $\mathbb{Z}_N$?

I want to split the Bush's Baked Beans recipe into $M$ parts so that any set of $N<M$ people can reconstruct the recipe, but with the following constraints: Each person knows only a yes or no ...
0
votes
1answer
43 views

Probability density function of entropy of a gaussian variable

I have a problem finding the probability density function of entropy of a normally distributed sample. It is known that the entropy of a gaussian variable $X$ equals $H=h(X)={1\over2}\log(2\pi ...