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

Shannon inequalities

I have some difficulties in showing the relationship between mutual information $I(X; Y |Z)$ and $I(X; Y)$? What is larger?
0
votes
1answer
43 views

The information of a Bernoulli random variable and surprisingness

Consider a random variable $\mathbb{X}$ with: $f(x;p) = 2^{-n}$ if x = 1 and $f(x;p) = 1-2^{-n}$ Then the information gained from an experiment where x=1 is ...
10
votes
3answers
260 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
2
votes
0answers
55 views

Computing Relative entropy?

I am doing a project for my CS class and I was wondering if the following would work. I have 50 different people who have rated the same 50 books. The rating system is as follows: negative 5 = hate ...
0
votes
1answer
48 views

Possible Mistake in Calculating Posterior of Distribution using Bayes Rule and Integration

I have been struggling on a homework question where I have to compute the posterior density of a distribution. While I can compute the posterior, I believe I made a mistake because the area under the ...
7
votes
3answers
184 views

Measure of how much information is lost in an implication

In an implication like $p \implies q$, is there some measure of how much information is lost in the implication? For example, consider the following implications, where $x \in \{0,1,\ldots,9\}$: ...
3
votes
0answers
87 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
1
vote
0answers
64 views

convexity of the product of two entropy-like functions

Consider the functions $T_p(q)= \sum_i q_i^p$, where p>1 and q is a finite-dimensional vector satisfying $\sum_i q_i = 1, q_i >0$ (ie, a probability mass function). In information-theoretic terms, ...
1
vote
1answer
51 views

Entropy: Is $H(X_{1},X_{2}) = H(X_{1})$ true?

Question: If $X_{1}, X_{2}$ are two discrete random variables. $X_{1}, X_{2}$ have the same probability distribution can we then deduce that: $H(X_{1}, X_{2}) = H(X_{1})$ is true? Remark: ...
0
votes
1answer
50 views

Easy bound involving logs and binomial coefficients

I am currently working on an information theory problem where I have to bound the divergence between two distributions. The divergence can be simplified to: $$\sum_{k=0}^N \ {N\choose k} ...
0
votes
1answer
46 views

i.i.d binary random variable question

Suppose there are i.i.d. binary random variables $X_i \sim X$ with distribution $P(X=1) = 0.75$ and $P(X=0) = 0.25$ i) For $n=5$ and $e=0.1$, which sequences fall in the typical set $A_e^n$? What is ...
0
votes
1answer
98 views

Help deciphering Levenshtein formula

I am trying to completely understand the Levenschtein formula, and I have been reading the Wikipedia article on this. However, the description of the mathematical formula confuses me: ...
0
votes
1answer
47 views

Expanding information capacity of Gaussian Channel

I'm currently try to understand a Gaussian Capacity Channel. I found litterature on internet, and some expand the information capacity of a Gaussian Channel as follow: $$I(X,Y)= h(Y) -h(Y\mid X) = ...
4
votes
3answers
128 views

Does any error correction code still work in such situation?

I'm looking for a kind of error correction code or solution that can correct my codeword in this case: My message holds k bits, and 2*k bits codeword (rate is 1/2) is produced by the generator ...
2
votes
1answer
60 views

Amount of information a hidden state can convey (HMM)

In this paper (Products of Hidden Markov Models, http://www.cs.toronto.edu/~hinton/absps/aistats_2001.pdf), the authors say that: The hidden state of a single HMM can only convey log K bits of ...
11
votes
6answers
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).$$ ...
10
votes
3answers
348 views

What is the least amount of questions to find out the number that a person is thinking between 1 to 1000 when they are allowed to lie at most once

A person is thinking of a number between 1 and 1000. What is the least number of yes/no questions that we can ask and know what that person's number is given that the person is allowed to lie on at ...
28
votes
2answers
308 views

Information-theoretic aspects of mathematical systems?

It occured to me that when you perform division in some algebraic system, such as $\frac a b = c$ in $\mathbb R$, the division itself represents a relation of sorts between $a$ and $b$, and once you ...
2
votes
1answer
71 views

Infinite Bias in a Maximum Likelihood Estimator

I'm having some problems calculating the bias of a ML estimator in the following problem: Let $\mu$, $x$, $y$ be random variables such that: $y|x$ is distributed as $\exp(x)$ so that $p(y|x) = ...
1
vote
1answer
91 views

Expression for the size of type class, or multinomial coefficient.

The notations follow those in Cover&Thomas, "Elements of Information Theory", 2ed. I saw from a paper that the size of type class $T(P)$ can be expressed as ...
0
votes
0answers
85 views

Rigorous formulation of Shannon-Hartley theorem

The Shannon-Hartley theorem gives an expression for the capacity of a bandwidth and power limited channel. How would one formulate this theorem mathematically (rigorously)? I understand the formula ...
3
votes
0answers
237 views

Intuition for Fisher information metric

In statistical maniolds $S=\{p_\theta\}$,$\theta=(\theta_1,\dots,\theta_n)$, the Riemaanian metric usually defined is the Fisher information metric $$g_{ij}(\partial_i,\partial_j)=\int \partial_i(\log ...
0
votes
1answer
42 views

Decoding used in Algorithms

Using a transposition matrix of size 4 by 6 (4 columns, 6 rows) and key ‘time’ decode the following message: RLAPET HWBUIE EIERSS TELSRT I am just looking for either a starting point or a step by ...
0
votes
1answer
90 views

mutual information problem

Consider the following problem: What is $I(X;Y)$ where $X$ is the outcome of a roll of a fair 6-sided die and $Y$ is whether the outcome of THAT SAME ROLL was even or odd? Intuitively, I thought ...
0
votes
1answer
171 views

Entropy Problem: mutual information

I have a problem about entropy and mutual information that I have attempted, but would like feedback on. 30% Boas 20% Anaconda 50% Cobra Half of the Cobras were medium sized, and the other half were ...
1
vote
1answer
75 views

About the differential entropies of well-known continuous distributions

Assume that the continuous random variable $X$ has a distribution (in a closed form expression) with differential entropy $h(X)$. Q) Then, is it true for any continuous distribution that the ...
1
vote
0answers
159 views

Random variables identities - how to make a formal proof.

Let $X, Y, Z$ be three random discrete variables. Consider the below random variables: $A = X\vert Y\vert Z$ ,$B= X\vert Y,Z$ Question: Can I conclude that $A$ and $B$ are the same ...
1
vote
1answer
76 views

One cannot know if a number could be written any shorter according to Gödel's incompleteness theorem

I am reading Tor Nørretranders (cannot find the English version, sry) and he states that Gödel's incompleteness theorem implies that we cannot know if we can write a number any shorter (e.g. ...
1
vote
2answers
79 views

Ask for a question about independence

This is the question I met while reading Shannon's channel coding theorem. Assume a random variable $X$ is transmitted through a noisy channel with transition probability $p(y|x)$. At the receiver a ...
0
votes
1answer
42 views

A question about independence of bivariate random variables

Assume we have two bivariate random variables $(X_1,X_2)$ and $(Y_1, Y_2)$ and the distribution satisfies $p(y_1,y_2|x_1,x_2)=p(y_1|x_1)p(y_2|x_2)$. I can prove that if $X_1$ and $X_2$ are ...
1
vote
1answer
237 views

How to prove the following entropy formula?

Could anyone show me a proof or redirect to a source where the following entropy equation is proved? =) $$H(X,Y|Z)=H(X|Z)+H(Y|X,Z)$$ Thank you!
7
votes
1answer
245 views

Does “50/50 chance of.. . ” convey information?

I distinctly remember the professor in the undergrad introductory systems & control course saying that "when weather forecasters say there's a 50% chance of precipitation, they are conveying no ...
7
votes
0answers
184 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 ...
1
vote
0answers
45 views

$f(n) = n^2 \lceil \log n \rceil$ is time constructible

I have a question, I want to show, that: $$f(n) = n^2 \lceil \log n \rceil $$ is time-constructible. I have no idea how to do this. I know that $n^2$ is time-constructible and I know that $\log n$ ...
2
votes
0answers
78 views

Simple / Fast way to calculate the period of a arbitrary polynomial?

If I get a polynomial, say $u^5 + u^4 + u^2 + 1$, what is a simple and fast (by which I mean not to much to write) way to get the period of this term? Should I first test whether the polynomial is ...
0
votes
1answer
88 views

rule for adding nested sums with a common index

I've just started learning information theory and have stumbled upon a roadblock due to my apparently not understanding how summation works. I do not understand why this is true: $- ...
1
vote
1answer
69 views

generalization of base-n notation from naturals to fractions

not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$. is there some math/theory generalization of ...
2
votes
1answer
52 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 ...
7
votes
2answers
274 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
38 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
95 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 ...
11
votes
1answer
308 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
104 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
343 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
211 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
206 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
296 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
115 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
169 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
171 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) ...