A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

Questions tagged [information-theory]

Questions about Information theory, entropy, and information content of various sources

Filter by
Sorted by
Tagged with
2
votes
0answers
15 views

Information bottleneck function

On the Wikipedia page, the information bottleneck function is defined in the following way. For some random variable $X$ containing information about the relevant variable $Y$, we have some joint ...
3
votes
1answer
28 views

Upper bound for set disjointness under product distributions

For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some ...
0
votes
0answers
30 views

combination network

Can any one help me find a reference about how to describe the connectivity between the nodes (H relays) and users in combination network ? I mean how exactly I can draw the connection for any number ...
1
vote
2answers
29 views

Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
3
votes
2answers
47 views

In information theory, why is the entropy measured in units of bits?

In information theory, we have the quantity "information". Suppose we have some discrete random variable $X$, that can take values $\{{a,b,c\}}$ with corresponding probability distribution $\{{\frac{...
0
votes
2answers
33 views

Fundamental motivation behind the use of bits and binary representation

This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory? If for technical reasons building ternary computers ...
3
votes
1answer
46 views

Standard information-theoretic lower bound?

There should be a simple argument, but I'm struggling to see it. Suppose Alice has a string $x \in \{0, 1\}^n$ and sends a message $s = s(x)$ to Bob. And suppose that given $s$, Bob can reconstruct ...
0
votes
1answer
24 views

Parity vs Parity bit vs Parity sum

Assume that $B_b$ denotes the finite set of bitstrings of length $b$, if we are given its subset $A = \{e_i\}, i \in \{0,... n\}$, such that $e_i \in B_b$, what is "the parity sum of As bitstrings" ($...
4
votes
0answers
41 views

Understanding simulated annealing information theoretically

So I recently rediscovered simulated annealing though a path that others seem to be well aware of. I was aware of Metropolis-Hastings as a sampling algorithm that creates a Markov-Chain who's ...
1
vote
1answer
38 views

How to calculate conditional entropy

I'm new to information theory and I am struggling to understand this problem. Let $p(x,y)$ given by: How can we calculate $H(X|Y)$? I know $H(X|Y)=H(X|Y=0)+H(X|Y=1)$ but then I don't know how to go ...
1
vote
1answer
74 views

Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
2
votes
1answer
36 views

Proof on lower bound of search in unsorted array with information theory?

I know there are proofs using an adversary technique. I've seen other proofs for search in a sorted list using information theory. But I haven't come across a proof using it to prove the lower bound ...
1
vote
0answers
27 views

Can we think of information theory in terms of “a measure on set of information”?

In information theory, we deal with the quantities $I(X;Y), H(X),H(Y), H(X|Y), H(Y|X)$. These are just numbers, but I intuitively think of them as the "measure" of a set of information. There is at ...
4
votes
1answer
42 views

How connected are information theory and algorithmic information theory?

In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth). As far as I understand, algorithmic information ...
1
vote
2answers
40 views

What is a symbol code?

I am a physicist learning a bit of information theory. I have encountered a term ("symbol codes") on Wikipedia, and cannot find what it means: Source coding theorem for symbol codes Let $\...
3
votes
3answers
102 views

Is it possible to have high compression but low predictability?

Can you have a process that generates a binary sequence with high compression rate (low entropy) but impossible to predict next symbol? 'impossible to predict' - sequence cannot be predicted ...
1
vote
0answers
14 views

Example of channel where capacity is achieved without a uniform distribution on the output alphabet

The capacity of a discrete memoryless channel is given by the maximum of the mutual information over all possible input probability distributions. That is \begin{align} C &= \max_{p_X} I(X:Y) \\ &...
1
vote
1answer
45 views

Is a complete code always optimal?

According to wikipedia, Kraft's inequality holds with equality when a code is complete. Huffman encoding produces a complete code that is optimal. Are all complete codes optimal and vice versa?
0
votes
0answers
24 views

Information Theory: Comparing surprisal of words with varying count frequency

This is a very broad question, I'm not sure if cstheory is the better place. How can I compare the conditional surprisal of words that vary in frequency? $S(w|context)=−log(p(w|context))=−log(\frac{...
0
votes
1answer
54 views

information theory, find entropy given Markov chain

There is an information source on the information source alphabet $A = \{a, b, c\}$ represented by the state transition diagram below: a) The random variable representing the $i$-th output from this ...
2
votes
1answer
74 views

Is the capacity achieving input of a discrete memoryless channel unique?

Consider a classical discrete memoryless channel (DMC). Let $p$ be an input probability distribution and $Q$ be the channel's transition matrix. $q = Qp$ is a valid output probability distribution. ...
1
vote
0answers
16 views

Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?

Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound? https://en.wikipedia.org/wiki/Bekenstein_bound
1
vote
1answer
41 views

Examples of exact computation of Kolmogorov complexity?

First question: It is known that Kolmogorov Complexity (KC) is not computable (systematically). I would like to know if there are any "real-world" examples-applications where the KC has been computed ...
2
votes
1answer
23 views

Prove that the upper bound in the Noiseless-coding theorem is strict

Given a probability distribution $p$ across an alphabet, we define redundancy as: Expected Length of codewords - entropy of p = $\ E(S) - h(p)$ Prove that for each $\epsilon$ with $0 \le \epsilon \...
1
vote
1answer
35 views

Reaching Shannon capacity of a channel

Suppose I have the following from alphabet $\mathcal{X} = \{0 ,1\}$ to $\mathcal{Y} = \{0 ,1\}$. The channel simply does \begin{align} 0 \rightarrow 0&\quad \text{with probability 1} \\ 1 \...
0
votes
0answers
36 views

Is entropy a good indicator of the quality of a lossy compression?

Say I want to quantitively evaluate the effectiveness of several color-to-grayscale conversion algorithms, which can be considered as lossy compression. Would entropy be a good indicator? To ...
0
votes
1answer
44 views

Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

For data compression, every codding that I've seen is binary. It means we convert a language with $N$ symbol size to a language with $M=2$ symbol size. For example, in Huffman coding, the goal is to ...
0
votes
0answers
21 views

go back n protocol scenario consequences

i am not sure with tihs question. i will post it here along with my attempt: the following scenario is regarding go back protocol n, with 3 bits for sequential numbering, assuming that the following ...
2
votes
1answer
29 views

Given two data feeds, find out if they capture the same information

Say, there are two camera feeds, how can I establish if they were filming the same scene? It seems plausible that there are algorithms that somehow calculate mutual information and detect "causality ...
0
votes
1answer
83 views

How to calculate information gain in ID3?

I am trying to implement a decision tree classifier using ID3 algorithm. According to Aritificial Intelligence - A Modern Approach, information gain of attribute A ...
0
votes
0answers
57 views

finding the overhead and distance of an unknown code based on message making algorithm

for an information word M with m bits that is coded as following: M is coded into a word A using an unknown code that allows detection of not more than one error. the code word is the word obtained ...
0
votes
1answer
56 views

Is it possible to achieve greater than perfect compression using machine learning and big data?

Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using ...
3
votes
2answers
761 views

Under what conditions does the function C = f(A,B) satisfy H(C|A) = H(B)?

Suppose we have a function $f$, $$ C = f(A,B), $$ where $A$, $B$ and $C$ are random variables. I notice that when the random variables are binary ($\{0, 1\}$) and $f$ is the XOR operation, we have ...
2
votes
1answer
76 views

What doest it mean: “computer is an intelligence amplifier”?

There is one example in Kolmogorov complexity books and related articles: Consider we have a monkey at a typewriter and a monkey at a computer keyboard. If the monkey types at random on a typewriter,...
1
vote
1answer
35 views

Sphere packing inequality for error-correcting codes

i am wondering if the following inequality is correct: if a code allows repairing of no more than k errors (inclusive, included) and m is the number of information bits and r the check bits, then $$∑^...
31
votes
2answers
2k views

Simulating a probability of 1 of 2^N with less than N random bits

Say I need to simulate the following discrete distribution: $$ P(X = k) = \begin{cases} \frac{1}{2^N}, & \text{if $k = 1$} \\ 1 - \frac{1}{2^N}, & \text{if $k = 0$} \end{cases} $$ The most ...
1
vote
2answers
40 views

Prove that $I(A;B|C)=0$ given $I(A;B)=0$

Let $A$, $B$ and $C$ be 3 discrete random variables. If $A$ and $B$ are independent ($I(A;B) = 0$, where $I$ represents the mutual information), how can we prove that $I(A;B|C)=0$? When I draw a Venn ...
9
votes
2answers
2k views

Does a binary code with length 6, size 32 and distance 2 exist?

The problem is to prove or disprove the existence of $C$, s.t., $|c| = 6,\forall c\in C$; $|C| = 32$; $d(c_i,c_j)\geq2,1\leq i<j\leq32$. ($d$ stands for hamming distance) I tried to construct a ...
1
vote
1answer
17 views

Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?

The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as $$ (S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in ...
3
votes
2answers
35 views

How to show that in noiseless coding theorem, the bound $\mathrm{MinACL}<H(P)+1$ is tight?

The theorem states that $$ H(P)\leq\mathrm{MinACL}(P)<H(P)+1 $$ where, $\mathrm{MinACL}$ means the minimum average code word length of a given information source, i.e. the average code word ...
0
votes
0answers
240 views

Huffman Coding vs Arithmetic Coding

Are there conditions under which given text $T$ that huffman code and arithmetic code will produce the exact encoding of $T$?
2
votes
2answers
44 views

What is the term for two file formats that describe the same amount of information?

I am working on file formats conversion. Some of them can be converted back and forth to others without losing any information (fields or precision of the numbers encoded), others file format do not ...
2
votes
0answers
44 views

What is the compressibility of this simple “book”?

Compressibility is defined as $$C=\frac{2^{HN}}{2^{H_{max}N}}$$ The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$ ...
1
vote
2answers
103 views

Why it is not a Huffman code

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was: $\{00,01,10,110\}$ This code is not Huffman becuase it has just one ...
35
votes
6answers
7k views

Do lossless compression algorithms reduce entropy?

According to Wikipedia: Shannon's entropy measures the information contained in a message as opposed to the portion of the message that is determined (or predictable). Examples of the latter ...
3
votes
1answer
96 views

Dependency on adjacent blocks decreases as block count increases

The following is an excerpt from Information Theory: A Tutorial Introduction, page 65. Now, supposing the identity of each letter in English does not depend on any letter that is more than 10 ...
-1
votes
3answers
229 views

I think you can always compress compressed data, is it true?

In compressed data, repetition of same pattern is not a lot, so, you can expect it to be with space inside to contain always. I found a way to compress data without limitation. Is it right? Am I ...
2
votes
0answers
43 views

Computing/sketching essential bit content of a binary source

I'm given the Bernoulli distribution of a biased coin toss with probability distribution $P_X = \{0.2, 0.8\}$ over the alphabet $\mathcal{A}_X=\{0,1\}$. I want to sketch the normalized essential bit ...
14
votes
3answers
2k views

Shannon Entropy of 0.922, 3 Distinct Values

Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits ...
1
vote
1answer
20 views

How many prefix code we can find for a given distribution of probability?

A source emits 5 signals s1, s2, s3, s4 and s5 whose probabilities are as follows: 1/3, 1/3, 1/9, 1/9, 1/9, 1/9. How many prefix codes we can construct on A={a, b, c}? And how many are there with the ...