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
2answers
15 views

Channel code for multiple bit errors

I've been exploring information theory out of personal interest and have a cursory understanding of Hamming Codes. From what I can tell, they're designed to exclusively detect the location of a single ...
0
votes
0answers
26 views

From Orthogonal vectors to Useful Bivector

If we have set of orthogonal vectors (X) can we form a set of orthogonal bivectors from that set? I am trying to find if there is a way to get 'more information' from an orthogonal matrix by some ...
1
vote
1answer
25 views

Understanding an application of Entropy

I'm struggling with the following exercise on entropy. Suppose that your friend Alice chooses a number $X$ uniformly at random from $[1,n]$, which she writes down using $\log n$ bits; you can assume ...
0
votes
0answers
39 views

Random Codebook Generation

I do generate a random codebook $\mathcal{C}$ by generating $2^{NC}$ codewords $X^N=[X_1\;X_2\;\cdots\;X_N]$ randomly and independently, each according to some distribution $p_{X^n}(x^n)=\Pi_{i=1}^n ...
0
votes
1answer
30 views

Relation between independence number and channel capacity

Suppose $P_{Y|X}$ is a discrete memoryless channel with confusability graph $G$ and capacity $C = max_{P_X}I(X; Y )$. I want to prove the following relation: $\log{\alpha(G)}\le C$ where $\alpha(G)$ ...
9
votes
0answers
163 views

Determining information in minimum trials (combinatorics problem)

A student has to pass a exam, with $k2^{k-1}$ questions to be answered by yes or no, on a subject he knows nothing about. The student is allowed to pass mock exams who have the same questions as the ...
0
votes
0answers
21 views

Description length in model coding

In class, our professor posted the following: We will discretize $\theta$ (some model) into $1/\sqrt{n}$ distinct values. Intuitive argument: with N data points, our estimation error for $\hat ...
0
votes
0answers
58 views

Can we use the distance to nearest prime to approximate large integers?

Let's say we have two oracles, NearestPrime and IndexOfPrime, defined as follows: Given some integer x, NearestPrime yields the prime number nearest to x that is not greater than x. ...
0
votes
1answer
24 views

Is this formula a KL divergence?

As everyone knows KL divergence's formula is $KL(p||q) = \sum_{i=1}^{n}p(i)\log (p(i)/q(i))$. In the image, formula(9) is really calculate KL(X||($(UZ^TA^T)$)) , however i have no idea why there is ...
0
votes
3answers
76 views

Isn't this the most compact binary representation of all numbers?

Here is the transformation: $$\begin{align*} &1\to(0)\\ &2\to(1)\\ &3\to(10)\\ &4\to((1))\\ &5\to(100)\\ &6\to(11)\\ &7\to(1000)\\ &8\to((10))\\ &9\to((1)0)\\ ...
1
vote
0answers
24 views

Generalized Form of Fano's Inequality

The Wikipedia article on Fano's Inequality presents a generalization as follows: Let $\mathbf{F}$ be a class of probability densities with a subclass of $r+1$ densities denoted $f_{\theta^{(i)}}$ ...
2
votes
0answers
20 views

Error correcting codes for asymmetric channels

Most work in error correction coding theory (Hamming, Cyclic, BCH, Reed-Solomon, Turbo Codes, LDPC...) deals with linear codes. Now, a linear code binary code is a good fit (only?) for a symmetric ...
2
votes
1answer
24 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
37 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
31 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
33 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
40 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
34 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
18 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
30 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
27 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
14 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
29 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
36 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
23 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
60 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 ...
1
vote
1answer
20 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
38 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
19 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
35 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
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
62 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
53 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
20 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
27 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
31 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
24 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
12 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
57 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
31 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
22 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
54 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 ...