Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
217
questions
1
vote
0answers
13 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
36 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
20 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
44 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
19 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
14 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
28 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
21 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
31 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
35 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
43 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
19 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
36 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
55 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
52 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
743 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
65 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
28 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 $$∑^...
30
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
37 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
15 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
27 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
217 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
42 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
41 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
60 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 ...
0
votes
0answers
9 views
Finding the 'capacity' of a network by treating it as a channel
Let's say I have a fairly basic network with two senders and two receivers. I'm wondering if I can treat this network as an effective communication channel that takes an input alphabet made up of the ...
34
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
92 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
202 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
37 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
16 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 ...
0
votes
1answer
21 views
What is the relation between the quantity of information of $A_i$ and $A$, where $A=\bigcup_iA_i$?
Let $A$ be an event divided into 4 events $A_i$ with the same probability. Why does the quantity of information of $A_i$ satisfy
$$ I(A_i) = I(A) + \log (4)?$$
1
vote
0answers
24 views
How to use HITS algorithm to rank pages
I am trying to implement a simple web search engine mechanism with using HITS algorithm. I understand how the algorithm work and produce hubs and authority values for each page. But how can I use this ...
1
vote
1answer
69 views
fully homomorphic encryption with information-theoretic security?
An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can ...
1
vote
1answer
47 views
what does the redundancy of a code means?
I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits.
But what does that means? I was ...
1
vote
2answers
77 views
Infinite Huffman Tree
We have to derive an optimal binary encoding for the infinite set of symbols $\{s_1, s_2, \dots \}$. They're distribution is given by
$$p(s_i) = 9 \cdot 10^{-i}$$
My intuition was to use a Huffman ...
2
votes
0answers
25 views
Classify/Distinguish between 8008 binary grids, with 13 queries
I have $8008$ binary grids of size $6 \times 10$ (they are all grids with the property described below), which I want to distinguish between with at most $13$ queries. A query will determine if the ...
1
vote
1answer
41 views
Maximizing entropy under constraint
How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
2
votes
0answers
31 views
How to know a certain grammar is parse-able
Is it possible to parse all kinds of structured data and give them a semantic meaning? For example, C++ is a really complicated language and I could never imagine a parser would be possible for it.
...
16
votes
4answers
5k views
Can data be compressed to size smaller than Shannon data compression limit?
I was reading about data compression algorithms and the theoretical limit for data compression. Recently I encountered a compression method called "Combinatorial Entropy Encoding", the main idea of ...
3
votes
2answers
76 views
Finding the total capacity of two communication channels
I have the transition matrices of two communication channels. I am able to find the capacity of each by performing an optimization calculation, however I need the total capacity of the two channels. ...
0
votes
1answer
34 views
How hexadecimal representation is more compact and intelligible for documentation?
My textbook says,
"Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as ...
1
vote
1answer
30 views
Does data entropy depend on the arrangement of the characters in a file?
From what I understand data entropy controls the limit of data compression and it depends on the probability of the characters in the file. Assuming that we have a file of size 256 bytes containing ...
4
votes
1answer
80 views
A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements
I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision ...
1
vote
1answer
70 views
Proof of Lower Bound for Deterministic Distinct Elements Algorithm
There is a proof in this document (page 8, Section 4, Lemma 3: https://inst.eecs.berkeley.edu/~cs170/fa16/lecture-11-29.pdf) that mirrors a proof my professor gave in my algorithms class. The lemma ...
0
votes
1answer
96 views
Applying Shannon Entropy to data storage
I know Shannon Entropy is defined for messages. When it's said the size of a file stored in a HDD is 1 MB, are we talking about the Shannon Entropy? If so, how do we extend the definition to static ...
