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
14 views

A simple formula for pseudo-random binary string

I'm trying to illustrate the concept of Kolmogorov complexity by comparing two seemingly-random binary strings, but showing that one of them is in fact describable by a program shorter than its length ...
1
vote
2answers
37 views

Upper bound on the entropy of a sum two random variables

Let $X$ be a random variable such that $|X| \leq A$ almost surely, for some $A > 0$. Let $Z$ be independent of $X$ such that $Z \sim {\cal N}(0, N)$. My question is: How large can the entropy ...
0
votes
1answer
31 views

Erasure Codes with Simplex Locality

In here, theorem $1.1$. there is this line 'Since $G$ has full rank it is possible to enlarge $N$ to a set $N^{'}$ ... exactly $k-1$. Note that the enlargement operation ... any of the leaders' in the ...
12
votes
7answers
1k views

Intuitive explanation of entropy?

I have bumped many times into entropy, but it has never been clear for me why we use this formula: If $X$ is random variable then it's entropy is: $$H(X) = -\displaystyle\sum_{x} p(x)\log p(x).$$ ...
0
votes
0answers
19 views

Mathematics branch concerned with availability of information

Is there a branch of mathematics that study about availability of information? For example, if I want to search for something on the internet, is there a branch of mathematics that can predict how ...
-1
votes
1answer
34 views

Analysis of Kullback-Leibler divergence

Let us consider the following two probability distributions ...
0
votes
1answer
18 views

mutual information of coupled variables

I have been looking for a method for evaluating the mutual information between a combination of source variables, $X_0, X_1$ and a target variable, $Y$. $$I(Y;X_0,X_1)$$ When I look on wikipedia's ...
2
votes
0answers
38 views

Good low-rate, short-length block codes

I am highly unsure whether this question is appropriate for this site (as it is at no point a math problem), yet searching in the stackexchange universe for similar topics showed the most hits on ...
1
vote
2answers
49 views

Ways to code two arbitrary binary strings into one without loss of information, and relevant bounds

If the title was not clear, I'm examining methods of taking two binary strings as input and outputting one binary string in such a way that the two original strings can be extracted from the output, ...
8
votes
1answer
209 views

Error correction code handling deletions and insertions

I have data which is expressed in form of fixed-length sequence of decimal digits, typically 10 digits in length. I'm looking for error correction code that would allow me to append one or more ...
2
votes
1answer
41 views

partition with infinite entropy?

Let $P$ be an infinite partition of the interval $[0,1]$. Let $P$ have elements $I_i$ which has Lebesgue measure $m(I_i)$. Then the entropy of $P$ is defined by $\sum_i -m(I_i)\log m(I_i)$. Can this ...
1
vote
0answers
15 views

Mutual information staying constant under composition of channels

Consider the following scenario: one has 2 communication channels $C_1$ and $C_2$. Let $p_0(x)$ be some arbitrary but fixed input probability distribution. The mutual information between the input ...
1
vote
1answer
216 views

Is maximizing the Shannon differential entropy equivalent to minimizing the predictability and/or minimizing the maximum density?

For a real-valued, 1-dimensional, continuous random variable X with density f(x), I am trying to determine if maximizing the Shannon differential entropy of f(x) is mathematically equivalent to ...
-2
votes
0answers
35 views

Maximum number of compressed RLE strings under any given length

Given a random string of length L (for instance, "01100010000101" of length "14"), and knowing that this string is only numerical, how many other strings under the form Y one can achieve by ...
7
votes
0answers
195 views

Entropy of matrix vector product

Consider a random $n$ by $n$ circulant matrix $M$ whose entries are chosen independently and uniformly from $\{0,1\}$. Let $M'$ be the $m$ by $n$ matrix which is formed by taking the first $m$ rows of ...
0
votes
0answers
46 views

Special case of Kullback-Leibler additivity

I have three random variables $X,Y,Z$. If $(X,Z)$ are an independent pair and $(Y,Z)$ are an independent pair, then the additive property of the Kullback-Leibler divergence says $K(X,Z|Y,Z) = K(X|Y) ...
2
votes
1answer
14 views

Confusion about non-negative mutual information

The formula I was given for calculating information for a specific stimulus $s_x$ is: $$I(R,s_x) = \sum_i p(r_i|s_x) \log_2{p(r_i|s_x)\over p(r_i)} $$ It was also said that information is always ...
6
votes
3answers
116 views

Using decimals of $\pi$ to store data

I read recently about an idea to, instead of storing actual data, converting the data to a string of digits and then store the index of where this pattern occurs in some number, for example $\pi$. The ...
1
vote
1answer
300 views

Maximum entropy joint distribution from marginals?

How does one find the maximum entropy joint distribution of two random variables X and Y given their marginal probability mass functions? I know: I have the marginals, meaning p(x) and p(y) are ...
3
votes
1answer
49 views

Upper Bound on Mutual Information

I am interested in an upper bound on mutual information that I have been encountering frequently in the statistics and probability literature. I have yet to see the "purest" form of the inequality, so ...
-1
votes
0answers
18 views

Conditional Mutual Information of Markov Chains

I'm attempting to use conditional mutual information to determine the order of a Markov chain, but having trouble relating notation used in a specific reference on this topic to the actual quantities. ...
2
votes
0answers
33 views

Mutual Information for Gaussian Process (and also Fano's Inequality)

According to this presentation: Bounding Gaussian Process Information Gain we have a closed-form expression for the information gain as follows: $$ I\left(\vec{y} \mid f\right) = \frac{1}{2} \log\det ...
3
votes
2answers
130 views

Estimating the entropy

Given a discrete random variable $X$, I would like to estimate the entropy of $Y=f(X)$ by sampling. I can sample uniformly from $X$. The samples are just random vectors of length $n$ where the entries ...
1
vote
0answers
27 views

Do 2 timeseries represent the input better than one?

I only have a very basic familiarity with signal processing and information theory so I'm sorry if this is a very straight forward question. I have a very brief input signal and two timeseries as ...
4
votes
1answer
92 views

Relationship between two measures of inequality

Let $A = \{a_1,\dots,a_n\}$ be a multi-set and let $B$ be the set of distinct elements in $A$. Now define $H(A) = -\frac1n \sum_{x \in B} f(x) \log_2(f(x)/n)$ where $f(x)$ is the number of times $x$ ...
4
votes
1answer
123 views

Definition of entropy of an ergodic measure

I'm reading a paper in which it is stated that The entropy of an ergodic measure is defined as $$\lim_{n \to \infty} -\frac{1}{n} \sum_{|w|=n} \mu[w] \log \mu[w].\tag{1} \label{eq:1}$$ Here ...
5
votes
2answers
98 views

How to Count the number of words over an alphabet subject to restrictions on letter count?

For an alphabet $X$, is there a method of computing how many words over $X$ of length $n$ there are where the number of occurrences of each letter must satisfy a system of equations? For example if ...
0
votes
1answer
21 views

Bounds for Mutual Information

$V_1$, $V_2$ be two binary strings with equal number of bits (say the length is $l$). Then the mutual information of $V_1$, $V_2$ can be defined as: $I(V_1;V_2)$ = $\sum_{y \in Y} \sum_{x \in X} ...
1
vote
2answers
48 views

Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
0
votes
1answer
23 views

Equality of Information Gain and Mutual Information

I am curious about definition of information gain and mutual information in the context of feature selection. If looks like two these measures define exactly the same thing, however I didn't find ...
0
votes
1answer
37 views

How is the formula of Shannon Entropy derived?

From this slide, it's said that the smallest possible number of bits per symbol is as the Shannon Entropy formula defined: I've read this post, and still not quite understand how is this formula ...
1
vote
1answer
39 views

Calculate Huffman code length having probability?

Having an alphabet made of 1024 symbols, we know that the rarest symbol has a probability of occurrence equal to 10^(-6). Now we want to code all the symbols with Huffman Coding. How many bits ...
0
votes
1answer
40 views

Using binary entropy function to approximate log(N choose K)

I am not a mathematician and struggling with the exercises while reading this book Information Theory, Inference and Learning Algorithms. The author introduced the binary entropy function at the ...
2
votes
0answers
46 views

Shannon-Fano analysis, Binary-search-like

Prove that the codewords of the Shannon-Fano code satisfy $l_i \leq \left \lceil \log _2 \frac1{p_i}\right \rceil$. Elementary wording: given positive numbers in descending order $p_1,...,p_n$, ...
5
votes
1answer
153 views

Entropy of the induced transformation

I need help with this problem: Let $(X,\mathcal{B},\mu,T)$ be a ergodic dynamical system in the probability space $(X,\mathcal{B},\mu)$. Let $A \in \mathcal{B}$ with $\mu(A)>0$. We define the ...
0
votes
0answers
12 views

Few questions regarding applications of conditional entopy

I have the idea of entropy and conditional probability etc and having few conditional entropy related questions: 1. What does actually conditional entropy $H(Y|X)$ mean? How can we explain this term ...
0
votes
1answer
24 views

Mutual information decrease with coarse-graining

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$. Is it true that: If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus ...
4
votes
1answer
47 views

Prove that bitstrings with 1/0-ratio different from 50/50 are compressable

I'm looking for a proof, that $$ \sum_{i=0}^{\lambda n} \binom{n}{i} \le 2^{nH(\lambda)} $$ with $n>0$, $0 \le \lambda \le 1/2$ and $ H(\lambda)=-[\lambda log \lambda + (1-\lambda) log (1-\lambda)] ...
-3
votes
1answer
63 views

What's the Shannon entropy of the prime numbers?

Here's a note that calculates it as 1. Do you know of any other calculations? http://www.math-math.com/2014/05/shannon-entropy-shannon-entropy-of.html
2
votes
1answer
70 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
0
votes
1answer
44 views

Entropy of sum is sum of entropies

Having $X$ and $Y$ discrete random variables above finite set. Z is defined as $Z=X+Y$ when does the following happen: $$H(Z)=H(X)+H(Y)$$
0
votes
3answers
134 views

Similarity between two probability distribution

I am not sure how to put the question. I am not even sure if this question makes sense at all. I know that the similarity of two discrete (or continuous) distributions can be quantified by ...
0
votes
1answer
34 views

A question on Markov chain

Suppose for two random variables $X$ and $Y$ we have $X\perp\!\!\!\perp Y$ and also assume that three random variables $X$, $Y$ and $Z$ form the following Markov chain: $X\to Z\to Y$. Do these two ...
1
vote
0answers
34 views

What is the “true” entropy of a binary string?

Consider an infinite binary string $\sigma$ and define its entropy $$H_1 = -(p_0 \log_2 p_0 + p_1 \log_2 p_1)$$ with $p_i = \lim_{N\rightarrow \infty} N(i)/N$, $N(i)$ the number of $i$'s among the ...
3
votes
0answers
19 views

Entropy of Group Action by Knowing Finiteness of Unidimensional Subaction

I've been trying to solve the following problem " Considering a measurable dinamical system $(X, \mathcal{B}, \mu, \mathcal{T})$ where $\mathcal{T}$ is an action of a semigroup $G = N^d$ on $X$ for ...
0
votes
0answers
40 views

Problem with calculating probability of symbols

I've a $100 \times 100$ binary matrix it`s constructed with this probability table : i want to apply extended Huffman on this matrix my idea is to compress each column individually . - so starting ...
2
votes
0answers
29 views

Is there an information theory for continuous time signals?

Information theory books talk about entropy and mutual information of discrete time processes, such as a sequence of symbols sent with a symbol period $T_s$ and there received sequence. Can we talk ...
1
vote
2answers
85 views

Fano's inequality and error rate

The Wire-tap channel II (http://link.springer.com/chapter/10.1007%2F3-540-39757-4_5) article in proof of Theorem 1 uses Fano's inequality to estimate the entropy $H(S|\hat{S}) \leq K \cdot h(P_e)$ ...
-4
votes
2answers
75 views

How is Goedel's 1st incompleteness theorem related to the Axioms of a theory

i am thinking of various connections and formulations of Goedel's 1st incompleteness theorem. Apart from connections to Turing's Halting Problem and Algorithmic Complexity Theory, i am looking for ...
3
votes
0answers
59 views

Doubts in Bayes' Theorem

I meet one problem on the probability and statistic theory. "Assume given the probability spaces $(X,S,\mu_i)$, $i=1,2$, and the probability space $(X,S,\lambda)$. And there exsit functions ...