Articles of information theory

Justifying $\log{\frac{1}{P_{X}(x)}}$ as the measure of self information

I was reviewing self information and then came to realize that there is one idea that I have that I believe should be wrong but don’t know why. Let self-information associated with a random variable realization be: $$I_{X}(x) = \log{\frac{1}{P_{X}(x)}}$$ The main idea is that realizing rare events contains more information that realizing event that […]

How to make the encoding of symbols needs only 1.58496 bits/symbol as carried out in theory?

I’m reading the tutorial of Information Gain, and I see the following page: I know in the example above, I can encode this way: A 0 B 10 C 11 and then this will need $1/3*1+1/3*2+1/3*2=1.6667$ bits per symbol. But how can I code to achieve the 1.58 goal in theory? Is that possible in […]

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 most one of her answers.

Have Information Theoretic results been used in other branches of mathematics?

consider this a soft-question. Information Theory is fairly young branch of mathematics (60 years). I am interested in question, whether there have been any information theoretic results that had impact on other seemingly ‘unrelated’ branches of mathematics? Looking forward to hearing you thoughts.

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 assignments $\{l_i\}$ satisfying the Kraft inequality $\sum 2^{-l_i}\le 1$. Also $H(p)=\log \frac{1}{p}$ is additive in the following sense. If $E$ and $F$ are two independent events with […]

Lower bound on binomial coefficient

I encountered the following claim $$\frac{1}{n+1}2^{nH_2(k/n)} \le \binom{n}{k} \le 2^{nH_2(k/n)}$$ where $H_2$ is the binary entropy function. The upper bound is rather well known but how does one show the lower bound?

what is the mutual information of three variables?

mutual information of tow variables is $\displaystyle\sum\sum p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$ what is the mutual information of three variables? is it $\displaystyle\sum\sum\sum p(x,y,z)\ln\frac{p(x,y,z)}{p(x)p(y)p(z)}$?

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 form “Is $x$ (strictly) less than $k$?”. The game-master answers each query immediately, always truthfully except at most once. At the end the […]

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 wrong to use binary vector data in cosine similarity function.

What is necessary to exchange messages between aliens?

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 meet. Is it possible to transfer information between both species? What would be the mathematical precondition for information […]