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.
2
votes
1answer
42 views
How to test the convexity of mutual information using leading principal minors?
I read from textbooks that the mutual information function $I(X;Y)$ is a concave function of $p(x)$ for fixed $p(y|x)$ and a convex function of $p(y|x)$ for fixed $p(x)$.
I tried to test the ...
6
votes
2answers
137 views
Can the entropy of a random variable with countably many outcomes be infinite?
Consider a random variable $X$ taking values over $\mathbb{N}$. Let $\mathbb{P}(X = i) = p_i$ for $i \in \mathbb{N}$. The entropy of $X$ is defined by
$$H(X) = \sum_i -p_i \log p_i.$$
Is it possible ...
1
vote
0answers
30 views
How do I measure the similarity of two bivariate time series?
Suppose I have two bivariate time series:
$$ ts1 = [<a_1, b_1>, <a_2, b_2>, \cdots, <a_N, b_N>] $$
$$ ts2 = [<c_1, d_2>, <c_2, d_2>, \cdots, <c_N, d_N>] $$
Which ...
0
votes
1answer
64 views
Space : Kolmogorov complexity :: time and space : ___?
It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
10
votes
1answer
216 views
metric in the Wasserstein space of gaussian measures
I am reading the paper "Wasserstein Geometry of Gaussian measures" by Asuka Takatsu (section 3 is of interest to me) and I have difficulties understanding how the metric is used.
In particular, I am ...
1
vote
0answers
53 views
d,k - codes for error detection and correction
My question may sound a bit strange but i'm trying find out anything about the d,k-codes. I've been give a kind of home task to learn what is d,k-code and how it works. The problem is I can't find ...
6
votes
1answer
151 views
Empirical distribution vs. the true one: How fast $KL( \hat{P}_n || Q)$ converges to $KL( P || Q)$?
Let $X_1,X_2,\dots$ be i.i.d. samples drawn from a discrete space $\mathcal{X}$ according to probability distribution $P$, and denote the resulting empirical distribution based on n samples by ...
1
vote
1answer
128 views
What discrete memoryless channels have zero capacity?
Let $W$ be a $n \times n$ square (discrete memoryless) channel matrix (hence stochastic) and let $p^{(W)}$ be a capacity-acheiving distribution for $W$. Let $1$ denote the vector of all ones. If we ...
1
vote
1answer
108 views
Information theory - is every optimal prefix code a Huffman code?
I'm not sure about it but it seems true for me. I know that for every optimal code there exists a prefix code that is optimal, but I'm not sure if it's Huffman code.
Thanks in advance.
1
vote
3answers
194 views
Probability books useful for Information Theory?
Can you recommend me a list of good Probability Books for self-studying, with good explanations and introductions for Information Theory and not for the typical statistical subjects?
2
votes
2answers
110 views
Proving an asymptotic property regard the fraction of ‘1’ and ‘0’ in binary sequences
Consider the set of sequences of zeroes and ones of length $N$ with $k$ ones (or, $Np$ ones where $p = k/N$). We draw randomly and uniformly a sequence from this set.
I want to show that with ...
0
votes
2answers
77 views
Huffman code with probabilities $p_1, p_2,\ldots, p_n$
I have solved the first two subsections of an assignment, but I can't solve the last subsection.
We have a Huffman code with probabilities $p_1,p_2,\ldots, p_n$ and we know that ...
0
votes
1answer
57 views
Entropy of a Binary Source with a random until first other result is given.
I was studying for an exam and i found an interesting exercise, but very very bad redacted.
A coin is thrown until the first face is found. Denote as X the number of throws required. And find:
a) ...
0
votes
0answers
272 views
Binary symmetric channel capacity or mutual information inequality
I proved that
I(X,Y) <= 1 - H(p)
to the following way:
How can I prove if I start in that way I(X,Y) = H(X) - H(X|Y), I ...
0
votes
0answers
37 views
Proving Symmetrized Kullback-Leibler divergence
Kullback in his "Information theory and statistics" gives the symmetrized divergence as follows
$J(1,2)=\iint(f(x,y)-g(x)h(y))log{\frac{f(x,y)}{g(x)h(y)}}$
Later (p.8), he states that symmetrized ...
1
vote
0answers
25 views
mutual information based estimation
let $Y_1 = X_1 + X_2 + X_3 + X_4 $
and $Y_2 = X_1 + X_2 + X_5 + X_6 $
where $X ~ iid $ Binary valued RVs
I want to estimate $X_1$ and $X_2$.
How can calculating $I(Y_1;Y_2)=H(Y_1)-H(Y_1/Y_2)$ help ...
1
vote
1answer
35 views
Mutual Information Notation
I am confused about the difference which the use of ";" and "," causes in the following expressions for defining mutual information between X and Y
$ I(X ; Y) $ and $ I(X , Y) $
3
votes
1answer
140 views
A generalisation of a well known result in information theory
It is well known that Entropy is additive, and that it is the only sensible choice for measuring uncertainty if we want additivity to hold, i.e.
$H(XY) = H(X)+H(Y)$
or more explicitly, if we have ...
2
votes
2answers
52 views
Poker probability conundrum
You deal your friend five cards from a standard shuffled deck. He looks at his hand and says either "Oh! I have at least one $X$!" or "I don't have any $X$s," where $X$ is the name of a rank. Your ...
0
votes
1answer
43 views
Poker communication problem
You've been dealt five cards from a standard deck, and you wish to communicate the exact contents of your hand. The catch is that you're only allowed to make utterances of the form "I have an $X$" or ...
0
votes
1answer
80 views
p-lim inf definition (limit inferior in probability)
For an arbitrary sequence of real-valued random variables $\{Z_n\}_1^\infty$ , we define limit inferior in probability as follow :
$$ p-\liminf_{n\to \infty} Z_n \equiv \sup \{ \beta|\lim_{n\to ...
3
votes
1answer
63 views
How to guess a binary code with feedback
Suppose I want to guess a binary code, where the quality of my guess is provided by an evaluation function. I imagine a safe, where the user enters a binary code by flipping $N$ switches. After ...
1
vote
0answers
90 views
Mutual Information of Correlated Bivariate Uniform Distribution
We have correlated bivariate uniform distribution, where X and Y have a correlation coefficient $\rho$ and they uniformly distributed in the following rectangle. What is the mutual information of $X$ ...
2
votes
1answer
81 views
Intuition about the relation of combinations and entropy
It is not difficult to show that
$${n \choose \lambda n} \leq 2^{H(\lambda)n}$$
where $H$ is the binary entropy function:
$$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$
I was ...
9
votes
3answers
286 views
Has error correction been “solved”?
I recently came across Dan Piponi's blog post An End to Coding Theory and it left me very confused. The relevant portion is:
But in the sixties Robert Gallager looked at generating random sparse ...
7
votes
2answers
267 views
In what sense is the Jeffreys prior invariant?
I've been trying to understand the motivation for the use of the Jeffreys prior in Bayesian statistics. Most texts I've read online make some comment to the effect that the Jeffreys prior is ...
3
votes
0answers
47 views
Calculate sums of logs in precision
I am encountering a situation where I cannot calculate exact sum of a seris of logorithms in calculating entropy. Suppose we have a series of numbers $p_i$ and we want to calculate $\sum_ilog(p_i)$, ...
2
votes
1answer
48 views
Quantify the gain of information of a new information.
Information theory is not at all my field of expertise, so maybe my question will be a bit naive.
As said in title, I would like to quantify the gain of information of a new information.
For ...
6
votes
4answers
259 views
Is probability objective?
As we know, probability is a measure of events. However, is it an objectively attribute of events, or just an illusion in ones' mind?
For example, suppose that there is an empty black box with an ...
1
vote
1answer
229 views
Variations of the Hamming code.
What types of basic variations of the Hamming code are there and what are their objectives? I was taught the following version:
$$ L = n + k $$
$$ n \geq \log_2M $$
$$ k \ge \log_2(n+k+1) $$
where ...
1
vote
1answer
128 views
How do i calculate the probability of erroneous transmission?
In information theory, how do I calculate the probability of an erroneous transmission? Let's take for instance a binary symmetric channel with an error probability $ 1-d=0.25 $ and send codewords of ...
5
votes
2answers
206 views
Inverse of binary entropy function for $0 \le x \le \frac{1}{2}$
I'm trying to find the inverse of $H_2(x) = -x \log_2 x - (1-x) \log_2 (1-x)$[1] subject to $0 \le x \le \frac{1}{2}$. This is for a computation, so an approximation is good enough.
My approach was ...
4
votes
0answers
209 views
Universal Correlation measure — ranking correlations
I have time series data of experimental observations for two related processes.
I want to measure correlation for use in further analysis.
Correlation of the series changes over time and across ...
2
votes
2answers
63 views
Given $\forall x \in \mathbb{R} \: h(p^t(x))=th(p(x))$, how to get $h(p(x)) \propto \ln p(x)$?
The whole question is in the title. $p(x)$ is a probability distribution, and $h$ is continuous and monotonic in $p(x)$.
The purpose is to motivate that the "degree of surpise", or the "amount of ...
3
votes
1answer
161 views
Linearity of uncertainty
I've always used Shannon's entropy for measuring uncertainty, but I wonder why to use a logarithmic approach. Why shouldn't uncertainty be linear?
For instance, consider the following pairs of ...
0
votes
0answers
67 views
Covering number of a set of matrices
Suppose that we are given $n$ vectors $x_1,x_2,\ldots,x_n$ in $\mathbb{R}^d$ that are in general position. Now consider the set $\mathcal{X}=\lbrace\sum_{i=1}^n\gamma_i x_i x_i^\mathrm{T} \mid ...
1
vote
2answers
64 views
Do equal distance distributions imply equivalence?
Let $A$ and $B$ be two binary $(n,M,d)$ codes. We define $a_i = \#\{(w_1,w_2) \in A^2:\:d(w_1,w_2) = i\}$, and same for $b_i$. If $a_i = b_i$ for all $i$, can one deduct that $A$ and $B$ are ...
1
vote
1answer
112 views
Simple trace distance problem
I am self studying a course on information theory and came with the following question:
$A$ and $B$ represent two possibly different probability distributions representing two different independent ...
1
vote
1answer
63 views
How to incrementally reveal information
Please give a protocol to incrementally reveal information.
A politician wishes to make a yes/no announcement with out shocking the economy. They set a date 100 days in the future, and every day ...
2
votes
0answers
116 views
rényi entropy as a derivative
Let $x=(x_i)$ be a probability measure on $\{1,\ldots,n\}$. Suppose $1<p<\infty$. The Rényi entropy of $x$ is
$$
H^p(x)=\frac{1}{1-p}\log \sum_{i} x_i^p.
$$
Does there exist a formula for ...
0
votes
1answer
70 views
How to match a discrete distribution to a continuous distribution in information theoretic sense?
Let
$$
S \sim N(\mu, \sigma^2)
$$
be a normally distributed random variable with known $\mu$ and $\sigma^2$. Suppose, we observe
$$
X = \begin{cases} T & \text{if $S \ge 0$}, \\ -T & ...
0
votes
1answer
85 views
Meaning of the term single letter formula
It is common in information theory to look for single letter formulas or to dismiss a result as suboptimal if no single letter formulas are available.
Could someone clarify the meaning of what is a ...
1
vote
2answers
119 views
Entropy expression optimization with Langrange multipliers
I have recently encountered variants of the following expression:
\begin{equation}
S = H(a,b,c,d)-H(a+b,c+d)
\end{equation}
where $H$ is the Shannon entropy function, that is $H(X)=\sum_{x\in X}-x\log ...
1
vote
1answer
51 views
Variational distance basic properties
The variational distance between two probability distributions $X$ and $Y$ taking values on the same alphabet $\mathcal A$ is defined as
\begin{equation}
\delta (X,Y)=1/2\sum_{a\in A} ...
0
votes
0answers
45 views
Mutual information, handling start and end
In my homework, I am supposed to use Brown algorithm to compute word classes. I need to compute mutual information for some data and looking in my results and official results, I am probably making ...
1
vote
1answer
53 views
Types and Typical sequences
Joint types can often be given in terms of the type of x and a stochastic matrix \begin{equation} V:X\rightarrow Y \end{equation}such that $
P_{x,y}(a,b)=P_{x}(a)V(b|a)$ for every $a\in X$ , $b\in Y$.
...
2
votes
1answer
108 views
What is the mutual information $I(X;X)$?
$X$ is a random variable with normal distribution, assume $Y=X$, what is the mutual information $I(X;Y)$?
I guess that $h(Y|X)=0$ since when $X$ is known, $Y$ is completely known, so ...
1
vote
1answer
93 views
A Measure for Number of Unique N-Tuples
Suppose I have a multiset of numbers. I'm interested in the number of unique n-tuples that can exist using the numbers from this multiset. Now of course a closed form is of interest here, but what I'm ...
4
votes
2answers
564 views
What is the trellis diagram for a linear block code?
For the convolutional codes there is so-called trellis diagram,
for which the definition is rather clear for me, however in mathematical sense is not.
I have heard that it can be defined for linear ...
1
vote
1answer
87 views
Maximally entropy preserving irreversible functions. (CS related)
The topic/problem is related to hashing for data structures used in programming, but I seek formal treatment. I hope that by studying the problem I will be enlightened of the fundamental limitations ...
