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)

1
vote
1answer
30 views

Splitting a file into $m$ pieces of size $1/n$, such that any $n$ pieces allow you to recover the file?

Let's say we have a file (which we could define as a finite sequence of 0's and 1's (or any other two symbols)). For $m > n$, can you create $m$ pieces (which are themselves files), each $\frac 1n$...
0
votes
2answers
28 views

Minimum distance for large codes

The minimum distance is easy to compute, and so determine the error correcting/detection capabilities of a code, by enumerating all possible pairs of codewords and computing the hamming distance ...
1
vote
0answers
26 views

KL Divergence between the sums of random variables.

The relative entropy or Kullback–Leibler distance between two probability density functions $g(x)$ and $f(x)$ is defined as $$D(g\|f) = \int_{x} g(x)\log\frac{g(x)}{f(x)} dx .$$ We have two random ...
0
votes
0answers
27 views

Explaining something in Kraft-McMilan inequality proof

I was asked to present the Kraft-McMillan inequality, but I have trouble in understanding why in the following segment of the proof: there is a $$k\ge0 $$such that: $$ a^{-l_1}+a^{-l_2}+.....+(k+1)a^{...
0
votes
0answers
21 views

How to use the log-sum inequality to prove convexity of KL-divergence?

I'm trying to read up on information theory, and found the following: http://homes.cs.washington.edu/~anuprao/pubs/CSE533Autumn2010/lecture3.pdf Which states that the convexity of KL-divergence can ...
0
votes
0answers
30 views

Is there a name for the property of a code where symbol “space” is left unused?

For example, say I have the symbols A, B, C and D. If I encode these as A = 1, B = 01, C = 001 and D = 0001 (for a very simple example), I have a very simple prefix code. However, I know straight ...
0
votes
1answer
38 views

Help in proving inequalities in information theory-Kraft-McMillan

I was given a task of proving some inequalities that are related to Kraft-McMillan's inequalities, and i have been scratching my head for quite some time trying to prove it: $$ F(x)= \frac{1}{1-Q(x) }...
2
votes
2answers
109 views

Formula for proportion of entropy

Let's say we have a probability distribution having 20 distinct outcomes. Then for that distribution the entropy is calculated is $2.5$ while the maximal possible entropy here is then of course $-\ln(\...
1
vote
0answers
16 views

Cumulants of square of Poisson distribution

I'm writing up a derivation of an expression for mutual information between weakly interacting Poisson processes. I'm running into an expression that looks like this: $$\log\mathbb{E}\left[e^{\...
1
vote
1answer
21 views

Deriving the Power Spectral Density of a Maximum Entropy Process

In Elements of Information Theory, Chapter 12, Section 6 Burg's Theorem is derived: Presented with the first $p$ values of the autocovariance function $R(k) = E[X_i X_{i+k}]$ a stochastic process ...
0
votes
0answers
16 views

How can I show that any integrable Passband or Baseband signal is also a finite energy signal?

I have supposed that, as the definition of a baseband/passband signal says, the function x(t) is integrable, continuous and bounded due to the fact that it forms a Fourier Transform pair with x'(f) (...
-1
votes
0answers
95 views

I need help in Entropy question (information Theory)

I need help in proving an inequality: $1 - H(p,q) \leq |p-q|$ and $H(p,q) \geq 2p$ and $H(p,q)\geq 2 \min(p,q)$? Thanks in advanced!
1
vote
1answer
43 views

information measure for matrix that is analogous to rank

Is there a measure for matrix that is analogous to rank of the matrix, but it is continuous on matrix elements? Say, we could say the information in identity matrix $I_n$ is $n$, and when the off-...
0
votes
1answer
23 views

MLE in introductory probabilistic information theory

Consider sending a bit that is either $\{0,1\}$ through a noisy symmetric channel, such that for a given input $x$ and a given (potentially noisy) output $y$, $\forall i,j \in \{0,1\}. P(y = i | x = j)...
4
votes
0answers
118 views

How to keep up when converting between bases?

Here is a schematized binary channel that neatly conveys a decimal number. $ \require{begingroup}\begingroup \def\T {{ \cal T }} \def \Ti {{ \T \raise5mu{ \text- \scriptsize 1 } }} \def\Bx #1{{ ~ ...
2
votes
1answer
68 views

Concavity of Shanon's information

It is known fact for random variables $(X,Y) \sim p(x,y)=p(x)p(y|x)$ the mutual information is concave function of $p(x)$ for fixed $p(y|x)$. I have two confusions in interpreting the above fact: 1) ...
2
votes
1answer
45 views

why can't sort 12 elements in 29 comparisons

The information theoretic lower bound for sorting 12 elements is using 29 comparisons, but actually we can't sort them in less than 30 comparisons. My problem is that why we can't reach the ...
0
votes
1answer
32 views

Does the following function define a distance metric?

For real numeric vectors of length $N$, let $a_n \succ b_n$ be one if true and zero if false. The distance between $A$ and $B$ is $$\sum_1^N a_n \succ b_n$$ Note that this is very similar to the ...
1
vote
2answers
47 views

Proof of Cyclic Redundancy Check validity

I'm looking to understand the use of a Cyclic Redundancy Check, in combination with the mathematics behind it. So far I have 1) For any message $$M(x)\cdot x^n = Q(x)G(x) + R(x)$$ Where $Q(x)$ is ...
0
votes
0answers
14 views

Specific examples of Side Information?

I'm starting to apply information theory to gambling. There is something called Side information (see details in [1]), which I understand is additional information about the outs of the game. It could ...
1
vote
1answer
35 views

Conceptual Question : Relationship between entropy and a technique for source coding

I want to encode the messages to a sequence of 1s and 0s (subsequently called "bits"). This is called "source coding". Shannon's source coding theory states that the entropy of a source that emits a ...
0
votes
1answer
21 views

Proving some inequalities related to Information Theory

I've been working on some inequalities related to the information theory section of my decision theory course, and I could use some help on some of the derivations for one of the inequalities. As a ...
0
votes
0answers
19 views

Kullback-Leibner divergence true distribution

I have an image with an object which I treat as 2-dimensional Gaussian random vector with mean equal to the center of the object surrounded by, roughly, 3-sigma ellipsoid. On the other hand I feed the ...
3
votes
3answers
400 views

Do Gödel numbers have a practical use?

Is there any example of Gödel numbers being actually used in practice? If so for what purpose?
0
votes
1answer
22 views

For convex $f$, why is $(p,q) \mapsto q \, f(p/q)$ convex on $\mathbb{R}_+^2$?

This fact was stated in the Wikipedia article on $f$-divergences to explain why they are jointly convex.
2
votes
1answer
15 views

Lower bound for limit of length of codeword

Here is the question I'm trying to solve. I don't really have any idea how to approach it/what theorem to use. For $ p, \lambda >0$, let $m(n,p,\lambda)$ be defined to be the least $m$ ...
2
votes
1answer
24 views

Significance of Convex Sets for I-Projection

I have been reviewing the literature on information theoretic methods in statistics, and in particular, the method of I-projections. Given a discrete, finite alphabet $\mathcal{X}$, let $\prod$ denote ...
0
votes
1answer
17 views

How to prove $2d_H(\{XY\},\{X\}\{Y\})^2 \le I(X,Y)$?

Let $X$ and $Y$ be discrete random variables. Denote the joint distribution of $X$ and $Y$ by $\{XY\}$ and their marginal distributions by $\{X\}$ and $\{Y\}$. Let $\{X\}\{Y\}$ denote the product of ...
0
votes
0answers
20 views

Kullback-Leibler Divergence (KL) and Approximation Symmetry Property

The Kullback-Leibler Divergence doesn't satisfy the symmetric property. But, it can be approximated (bounded) to such a value. in this paper: Compressing Interactive Communication under product ...
0
votes
0answers
10 views

Checking if a code can be unambiguously decoded

The source of information is A = {a, b, c, d}. More info is given in the table below. I have to find the average length of the codes, compare it to the entropy of ...
2
votes
1answer
69 views

$λ=log(2)$ for the tent map – which basis for the logarithm?

If $\lambda$ is the largest positive Lyapunov exponent of a piecewise linear dynamical chaotic discrete in time map, then is there a relationship between the entropy $h$ and its $\lambda$. According ...
8
votes
4answers
111 views

Guess the number despite false answer

This is the Guess-The-Number game with a twist! Variant 1 Take any positive integer $n$. The game-master chooses an $n$-bit integer $x$. The player makes queries one by one, each of the ...
1
vote
1answer
19 views

The relationship between AEP and compression

So i've been reading up on AEP, and trying to get a grasp on it (and to figure out why it is important). I understand the general definitions, and that the whole idea is the knowlegde of typical ...
0
votes
0answers
25 views

Lower bound on binomial tail

In something I am reading, the following statement is mentioned in passing as something obvious: if $X_1,\ldots,X_n$ are i.i.d. Bernoulli with parameter $1/2 + \delta$, then $\mathbb{P}(\sum_{i=1}^n ...
1
vote
0answers
29 views

Information in Filtrations

Is the “information” kept track of by filtrations the same as information-theoretic “information”? If not, is there some way the two concepts can be reconciled?
1
vote
3answers
38 views

Approximation of an indefinite integral

Consider this integral $$\frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t$$ When $d$ goes to zero, $$\lim _{d\to 0} \frac{1}{2d}\int_{-d}^{d}f(x-t) \, \mathrm{d}t = f(x)$$ but what is the second ...
1
vote
1answer
19 views

Relative entropy between discrete and continuous random variables

Is this possible to define relative entropy between discrete and continuous random variables? Say $P$ is a discrete pmf and $Q$ is a continuous pdf, what is $D(P||Q)$?
0
votes
0answers
8 views

Monte-Carlo estimation of Mutual Information over AWGN channel

I'm trying to solve a problem I was tasked with. Basically I have to generate a 100k 16QAM inputs and transmit them over a AWGN channel. With this I have to use the Monte-Carlo estimation to figure ...
2
votes
1answer
34 views

Maximizing sum of logarithms (Z-channel capacity)

In the context of information theory, I am trying to maximize the following function (mutual information of the Z-channel's input and output) with respect to $p$ in order to derive Z-channel's ...
0
votes
2answers
41 views

Relative entropy (KL divergence) of sum of random variables

Suppose we have two independent random variables, $X$ and $Y$, with different probability distributions. What is the relative entropy between pdf of $X$ and $X+Y$, i.e. $$D(P_X||P_{X+Y})$$ assume all ...
0
votes
1answer
32 views

Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that $$H((f(X,Y), g(X,Y)))\leq H ((f(X,Y),...
0
votes
1answer
45 views

Proof regarding size and dimension of linear codes

The problem is stated as follows: Let C be a binary linear code of length n, dimension k and distance d and assume that C contains at least one element of odd weight. Let C' be the subset of C ...
0
votes
2answers
38 views

Repetition code and binary symmetric channel, where error is near 1/2

I want to send one bit $x$ over a noisy channel, specifically, a binary symmetric channel with error probability $p$, where $p=(1-\epsilon)/2$ and $\epsilon$ is small. In other words, the error ...
1
vote
1answer
19 views

For a Fisher Information, $\mathcal{I}(\theta)$, why does $\mathcal{I}(\theta) = n\mathcal{I}_1(\theta)$ not hold for multiple dimensions?

Suppose we have that $X_1, \ldots, X_n$ are iid from a distribution with ONE parameter, $\theta$. Then, under regulatory conditions, the Fisher Information may be written as: $$ \mathcal{I}(\theta) = ...
1
vote
0answers
22 views

$K(xy)\leq K(x)+K(y) +c$?

Could anyone show that for any $c$, some strings $x$ and $y$ exist, where $K(xy)>K(x)+K(y)+c$? Here $K(x)$ is the Kolmogorov complexity. I already know that $K(xy) \leq 2K(x) + K(y) +c$ and $K(xy) \...
13
votes
5answers
404 views

(Elegant) proof of an inequality: $h(x) \geq 1- (1-\frac{x}{1-x})^2$, where $h$ is the binary entropy function

I am looking for the most concise and elegant proof of the following inequality: $$ h(x) \geq 1- \left(1-\frac{x}{1-x}\right)^2, \qquad \forall x\in(0,1) $$ where $h(x) = x \log_2\frac{1}{x}+(1-x) \...
1
vote
0answers
15 views

Channel capacity of sum of symmetric channels

I've got a channel matrix $P$ of the form $\begin{bmatrix} Q \\ R \end{bmatrix}$ where $Q,R$ are channel matrices of symmetric channels, so they now have different input alphabets but the ...
0
votes
1answer
26 views

Basic Entropy Inequality and Identity question

This is a solution to a problem I am working on: \begin{equation} \begin{aligned} H(X|Y) + H(Y|Z) &\ge^? H(X|Y, Z) + H(Y|Z) \\ &=^\text{?}H(X,Y |Z) \\ &= H(X|Z) + H(Y|X, Z)\\ &\ge H(X|...
4
votes
1answer
71 views

Why do we like sticking random variables into their own distributions?

Let $X$ be a random variable taking values in the set $S$. It has some distribution $f(s)$. Often in statistics, we are interested in the real valued random variable $f(X)$. Here are some examples: ...
1
vote
0answers
12 views

Representation of the optimal filter measure as the measure of a diffusion process

In "Mitter SK, Newton NJ. A Variational Approach to Nonlinear Estimation. SIAM J Control Optim. 2003 Jan;42(5):1813–33", it is shown that the path estimation measure $P_{X|Y}(\cdot,y)$ for the ...