Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
-1
votes
0answers
16 views
Could Web 3.0 exist without cloud and vice-versa? [on hold]
I would want to know if could web 3.0 exist without cloud and vice-versa? Would I want to know also why? and some examples. Thank you.
1
vote
2answers
32 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
21 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
43 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
40 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
39 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
35 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
8 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
86 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 ...
0
votes
3answers
137 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
33 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
12 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
19 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
17 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
59 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
22 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
63 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
24 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
39 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
30 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
51 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
30 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
28 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
74 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
49 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
72 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 ...
2
votes
0answers
25 views
Is there a universal metric of “size of a program”?
There is a universal metric of information: amount of bits. It's universal in the sense that if we write a piece of information in DNA (4-ary digits), we can simply multiply by 2-log-4 to get the ...
2
votes
1answer
98 views
How realistic is the i.i.d assumption in the definition of Shannon's entropy?
Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a ...
0
votes
0answers
15 views
Deep neural networks and deep learning generate Markov chain of representation
When and why do deep neural networks and deep learning generate a Markov chain of representations of input patterns? How can be understood why the representations of the input patterns generated by ...
2
votes
1answer
134 views
Kolmogorov Complexity proving there exists a constant for when if two strings are equal length
When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be
...
5
votes
1answer
1k views
The Entropy of the phrase “Eile Mit Weile”
I want to calculate the Entropy of the phrase "Eile mit Weile". I found the probability of each letter as the following
$$P(e)=\frac{4}{12}$$
$$P(i)=\frac{3}{12}$$
$$P(l)=\frac{2}{12}$$
$$P(m)=\frac{...
1
vote
3answers
107 views
Is there a method to compress all data without loss (lossless compression)?
I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I ...
1
vote
1answer
67 views
Problem with determining the shape and direction of the Huffman Diagram
I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters;
$$a=5$$
$$b=3$$
$$c=1$$
$$d=2$$
$$r=2$$
But I'm not sure as to how the ...
0
votes
1answer
57 views
Finding the Entropy of a random experiment with probability of $\frac{1}{3}$
Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} ...
3
votes
1answer
41 views
Calculating Frequency of Terms with Zipf's Law
I'm studying for an exam and came across this question. I feel like it's much simpler than I am making it out to be, but I'm not sure.
Suppose we have a corpus in which Zipf’s Law holds. If the most ...
0
votes
1answer
68 views
Entropy and Information Gain for multi attributes
Is there any way that for specific dataset I can measure entropy and information gain for two or more attributes together? Let's say we have the following dataset:
$\begin{array}{cccccc|c}
x1 & ...
0
votes
0answers
70 views
Is it possible for a [futuristic] computer to contain the information of the whole universe?
(This is a question of information theory, data compression and entropy, so I believe it fits CS forum)
Does the fact that the computer itself is a part of the universe make it logically impossible ...
1
vote
1answer
41 views
Inequality over the entropy of an integer-valued random variable
I stumbled upon this inequality over a course on Information Theory :
If $Z\in\mathbb{N}$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})$ where $h$ is the binary entropy function
...
2
votes
1answer
41 views
Analysis of brute force decoder in a $q$-ary erasure channel
Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$.
For a ...
1
vote
1answer
93 views
Binary symmetric sources and information theory
How can we generate 3 or more binary Sources using BSC channel.
As we know, BSC can be easily used to generate 2 binary sources with some cross-over-probability(say p). Eg, length of codeword(say n) <...
1
vote
0answers
43 views
How an insertion can be decoded in Varshamov and Tenengolts (VT) codes
I have a good idea of how deletion can be decoded in VT codes using Levenshtein algorithm. However, I don't have any idea how can an insertion be decoded? Can anybody give me a small example using a ...
0
votes
0answers
23 views
Secrecy rate of eavesdropper channel?
I want to find secrecy rate of a main channel in case of Gaussian broadcast channel. e.g. I have a single transmitter and a receiver where eavesdropper wants to eavesdrop the communication over ...
2
votes
2answers
42 views
Conditions to apply Source Coding Theorem
I was wondering what are the conditions to apply source coding theorem (SCT).
1. Is it applied only to uniform-length coding, what about variable-length coding, does it also satisfy SCT?
I was ...
3
votes
2answers
277 views
What Good Is Kolmogorov Complexity Since It Is Relative?
Kolmogorov complexity is relative to a choice of Universal Turing Machine. Because of the Invariance Theorem, the difference in complexity assigned by two Universal Turing Machines is bounded by a ...
2
votes
1answer
51 views
Algorithm to determine a set given the size of its intersection with sets you choose
I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, ...
