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
2answers
49 views
How can you use a (fair) coin to draw straws among 3 people? (Information Theory)
The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay.
How can you use a (fair) coin ...
5
votes
3answers
119 views
Another Information Theory Riddle
The following nice riddle is a quote from the excellent, free-to-download book: Information Theory, Inference, and Learning Algorithms, written by David J.C. MacKay.
In a magic trick, there are ...
1
vote
3answers
275 views
Is it wrong to use Binary Vector data in Cosine Similarity?
I am doing Information Retrieval using Cosine Similarity.
My data is binary vector.
Since most of all reference I read is using non-binary vector (non-binary matrix) data, I am wondering if it is ...
0
votes
0answers
35 views
Intregral of exponential of Shannon Entropy Function
Here I am going to ask a similar question as rde asked , that is what is the integral of exponential of entropy function. That is what is the value of
$F[H(x)]=\int_{-1}^{+1} e^{ikH(f(x^2))} dx$
...
1
vote
1answer
70 views
Information content associated with an outcome
I have the following exam question for a multimedia exam in college:
Assume that you roll a single ordinary six-sided die twice, and
observe that the second number rolled is greater than the ...
2
votes
4answers
90 views
What exactly is a probability measure in simple words?
Can someone explain probability measure in simple words? This term has been hunting me for my life.
Today I came across Kullback-Leibler divergence. The KL divergence between probability measure P ...
7
votes
3answers
130 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\}$:
...
0
votes
1answer
95 views
How information works?
I am really confused after reading wikipedia...
What I don't get is how can something "bring" information, and in mathematics, how a mathematical object (like a set) can "have" information.
For ...
0
votes
0answers
11 views
Hellinger distance between 3-parameter Weibull distributions
I found Wikipedia to have listed Hellinger distance between pairs of 2-parameter Weibull distributions sharing the same shape parameter
http://en.wikipedia.org/wiki/Hellinger_distance
However, I ...
0
votes
1answer
17 views
What is being maximised in the channel capacity formula?
The channel capacity formula is given as such:
$$C=\max_{p(x)}I(X,Y)$$
Does this mean that it is the maximum probability multiplied by the mutual information, or is something else being maximised ...
1
vote
1answer
26 views
Entropy vs predictability vs encodability
Imagine there's a guessing game where a series of binary symbols are presented and a human must decide quickly if the symbol is the same as the previous or different. There's a property of the ...
0
votes
1answer
21 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 ...
1
vote
1answer
28 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?
3
votes
4answers
118 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)$
Why ...
11
votes
3answers
170 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
28 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 ...
4
votes
1answer
165 views
measure of information
We know that $l_i=\log \frac{1}{p_i}$ is the solution to the Shannon's source compression problem: $\arg \min_{\{l_i\}} \sum p_i l_i$ where the minimization is over all possible code length ...
0
votes
1answer
28 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 ...
0
votes
0answers
30 views
Why is K-L divergence defined as it is?
Why is the K-L divergence defined this way:
if $P$ and $Q$ are probability measures over a set $X$, and $P$ is absolutely continuous with respect to $Q$, then the Kullback–Leibler divergence from ...
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
0answers
71 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 ...
0
votes
0answers
29 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
29 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
27 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} ...
4
votes
2answers
151 views
Are there simple examples of capacity-achieving block codes for discrete memoryless channels?
The title pretty much says it all, but I am particularly interested in the case where the number of input and output symbols are equal and the transition matrix defining the DMC is nondegenerate. I am ...
0
votes
1answer
31 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
33 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
32 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
94 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
32 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 ...
1
vote
2answers
73 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 ...
2
votes
1answer
81 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 ...
7
votes
3answers
182 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 ...
2
votes
1answer
47 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) = ...
6
votes
0answers
67 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 ...
5
votes
2answers
231 views
Theoretical basis for overfitting
There are many examples in which making more "precise" predictions gives worse performance (e.g. Runge's phenomenon). My professor implied that there was a sound basis for choosing "simple" functions ...
1
vote
1answer
55 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
45 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 ...
1
vote
0answers
91 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 ...
3
votes
0answers
101 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
0answers
62 views
Proof for the upper bound on entropy $H(S)$?
I was trying to prove the upper bound on $H(S)$ using the inequalities $\ln(x)\le(x-1)$ and $\ln(1/x)\ge(1-x)$ for independent and memory less source symbols $s_1,\dots,s_q$ .
I am trying to prove ...
0
votes
1answer
36 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 ...
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 ...
1
vote
1answer
56 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 ...
0
votes
1answer
51 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
56 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
65 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. ...
0
votes
1answer
28 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
0answers
37 views
Multivariate Generalizations of the Mutual information
I'm interested in Multivariate generalizations of the Mutual information. So I'm just wondering if anyone can point me to a list of all such generalizations currently proposed. I've heard about the ...
0
votes
1answer
85 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? =)
Thank you!
