Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
286
questions
0
votes
0answers
11 views
Information contained or received
In my lecture, the lecturer introduced without much explanation that the following applies:
Given a discrete random variable $X$
$N$ possible values: $x_{1}, x_{2}, \ldots, x_{N}$
Associated ...
0
votes
0answers
7 views
Is there an entropy evaluation method with an unified length?
For entropy, the most common one is Shannon entropy, however, it ignores time series of data. For instance, data 0x00001111 and 0x01010101 are given the same entropy. It is obvious that the second ...
0
votes
0answers
11 views
What is the difference between erasure coding and RAID if your erasure code is parity check?
I'm reading about erasure coding and saw that one of the erasure codes is parity check. As far as I can tell this is just a generalization of something like RAID5. If you select something like parity ...
2
votes
0answers
20 views
Proof in the "Reaching Agreement in the Presence of Faults"
I am reading the "Reaching Agreement in the Presence of Faults", M. Pease et al and trying to understand their proof for the $n \geq 3m+1$ case.
In the induction step $m \gt 0$ it says the ...
2
votes
0answers
11 views
Information theory - Expurgation step to go from average error to worst case error in the large error regime
Consider a discrete memoryless channel $N$. We use a code to send messages over this channel.
Shannon showed that if we have a code $C$ with a finite number of codewords $|C|$ such that the average ...
1
vote
2answers
53 views
What is the entropy of an unordered list?
I'm trying to compress unordered lists of a few thousand integers for transmission over HTTP, and Claude Shannon is disappointing me with his mathematical ambiguity :)
Each integer is 6-digits, so ...
1
vote
3answers
57 views
Is every binary sequence the output of some meaningful-text-input algorithm?
Here is the problem: Let's say we have a random binary sequence, just an arbitrary sequence of zeroes and ones (of some arbitrary length of digits). Can we find an algorithm that would decode/...
1
vote
1answer
35 views
Is an AI upscaler incapable of reducing entropy?
I was reading the description of Anime4K (a video upscaler software) and I found a statement triggering my attention:
[upscaling is done] without any meaningful decrease in entropy (lost information
...
2
votes
1answer
61 views
Deriving a lower bound on the conditional entropy, conditioned on an event
I came across Lemma 19 in Certifying Equality With Limited Interaction, which states the following for jointly distributed random variables $Z$, $W$, where $Z$ takes values in $\{0,1\}^n$, and some ...
2
votes
0answers
13 views
Asymptotically Optimal Universal Code In Other Bases
Universal codes are fairly well studied, and many asymptotically optimal universal codes exist for binary data (see https://en.wikipedia.org/wiki/Universal_code_(data_compression) especially https://...
3
votes
1answer
48 views
Capacity of Binary Erasure Channel
Consider the the binary erasure channel, with input and output alphabet $\{0,?,1\}$ and channel matrix
\begin{bmatrix}
1-\lambda-\mu & \mu & \lambda\\
0 & 1 & 0\\
\lambda & \mu &...
1
vote
0answers
27 views
Why does attempting to estimate the entropy of text by randomly choosing chars in it and counting how often they are equal give wildly wrong results?
Why does attempting to estimate the entropy of a string, by randomly choosing pairs of (not necessarily adjacent) characters in it, and counting how often the selected characters in the pairs are ...
0
votes
1answer
29 views
Essential bit content - prove that we can't use less bits than that
Let $H_0$ be $\log_2(|A|)$, where $A$ is a set.
Let $C$ be a compressor $C\colon A \to \{1,0\}^l \cup \bot$.
This is a silly question, because intuitively it seems obvious.
How can I prove that $l$ ...
1
vote
1answer
27 views
Algorithmic information theory with stochastic algorithms?
Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, ...
2
votes
1answer
19 views
How Data Compression relates to Estimating Distribution?
I recently read this paper Mahoney, 1999.
And encountered this line,
optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (...
1
vote
0answers
41 views
How to calculate the entropy of a system with multiple states
I'm stuck in trying to compute an overall entropy calculation with an agent.
Let me first introduce some background of the problem. Basically, I'm doing some work with the contextual bandit problems. ...
2
votes
1answer
81 views
Information-theoretic lower bound for succinct string dictionary of the Unicode Name property
Background
The literature on succinct data structures refers often to the “information-theoretic lower bound” of encoding data, i.e., the minimum number of bits needed to store the data – a concept ...
0
votes
1answer
30 views
Maximal prefix codes and maximal length
Let $X$ a maximal prefix code on an alphabet $A$, $m(X)$ its maximal length, $F = X \cap A^{m(X)}$ and $F’ \subseteq A^{m(X)}$. Let $X’ = X \setminus F \cup F’$ a maximal prefix code. Why is it true ...
0
votes
1answer
123 views
what is the relationship between entropy and variance?
Consider a simple Bernoulli variable X
X = 1 with probability p
X = 0 with probability (1-p)
The variance is simply p(1-p). The ...
1
vote
1answer
178 views
Must a Turing machine tape be binary?
I once asked why does computer data bits are usually organized on binary (base 2) sets, rather than on unary (base 1) sets, aiming to also understand why its not also ternary (base 3), heptary (base 7)...
2
votes
1answer
34 views
Shared randomness does not increase capacity of a noisy channel - Why?
Why is it the case that when Alice and Bob use a noisy channel for communication, the capacity of the channel does not increase even if they are allowed to share pre-distributed randomness?
This is ...
0
votes
0answers
16 views
Compressing the output of a discrete memoryless channel
Let $x\in \mathcal{X}$ be a symbol from an input alphabet, let $p(y|x)$ be a conditional probability distribution corresponding to a discrete memoryless channel and let $y\in\mathcal{Y}$ be an output ...
0
votes
0answers
10 views
Achieving the capacity of an AVC under random coding
Is there any work that shows how to achieve the random coding capacity in an Arbitrarily Varying Channel (AVC)? The best I can find is in the book 'Information Theory: Coding Theorems for Discrete ...
1
vote
1answer
14 views
How to interpret parametric formulation of information bottleneck?
I'm reading this paper on latent representations with the information bottleneck https://arxiv.org/pdf/1804.06216.pdf and in section three, the authors write that the parametric formulation of the ...
0
votes
1answer
25 views
How to build 4 codewords with a code distance of 5?
I wonder how can I construct 4 (distinct) codewords given the fact that code distance is 5. As far as I know that the code distance is the number of distinct bits between any 2 codewords. How to ...
1
vote
1answer
52 views
How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?
I am struggling to find how can I know the number of errors that can be corrected and detected using (n=10) bit code with a (k=550) codewords.
As far as I know, to calculate the number of errors to be ...
0
votes
0answers
13 views
Understanding deterministic capacity of AVC
In the paper by Csiszar & Narayanan where they proved the deterministic capcity of an AVC, can someone please explain the decoder logic?
The second condition used by the decoder is
$$ I(XY;X'|S) \...
1
vote
0answers
12 views
Channel capacity of DMC with each transmission having different distribution
I got this doubt while reading about AVC in Csiszar Korner's book.
Corollary 12.3 The $\epsilon$-capacity of the AVC {$W : X \to Y$}
average probability of error equals, for every $0 < \epsilon &...
1
vote
1answer
26 views
Upper bound on size of minimal binary coverage code
Let $1 \le r \le n$ b e integer(with $n$ large) and let $\mathscr X_n$ be the set set of all $2^n$ binary strings of length $n$. A binary $r$-coverage code is a subset $S$ of $\mathscr X_n$ such that ...
1
vote
1answer
34 views
Converse proof for random coding capacity of AVC
I want to see the converse proof for the random coding (shared randomness) capacity of AVC. All I can find online is Csiszar Narayan's AVC paper which looks at deterministic coding. Further, the proof ...
3
votes
2answers
123 views
Information-theoretic limits for a weighing puzzle
Consider the following problem:
You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can ...
3
votes
2answers
84 views
Is Prediction the same as Compression?
Just came across this transcript that states:
The principle is that prediction is the same thing as compression. And
what that means is that whenever you have a prediction algorithm, you
can also get ...
2
votes
0answers
73 views
Is arithmetic coding slightly more efficient than rANS?
I'm extending a framework for lossy compression of multidimensional floating-point data. At some point in the pipeline, sequences of symbols from a non-uniform distribution are losslessly compressed ...
0
votes
1answer
68 views
Probability of loss using a binary symmetric channel
Today we talked about Information Theory and the binary symetric channel.
For newbies here is a little explanation :
For instance if I want to send a binary to someone :
The bit will be "flipped&...
1
vote
1answer
23 views
AEP with a Twist!
We know by AEP that if random variables $X_1,X_2,...$ are i.i.d. drawn from $P_X$ then the probability of the vectors in the weak typical set $$A_{\epsilon}^n = \{\vec x \in \mathcal{X}^n: |\frac{-1}{...
2
votes
1answer
31 views
Intuitive explanation on why stochastic encoding performs better in channel coding
I am a little confused about stochastic encoding in channel coding. For example, in the identification problem (R. Ahlswede and G. Dueck, “Identification via channels”), the authors claim that we can ...
0
votes
0answers
32 views
Proving an entropy inequality
I am given that $Z$ is independent of $(X,U)$, where $Z$ and $X$ are binary random variables while $U$ is an arbitrary random variable. I need to prove the following:
$$ H(X\oplus Z|U) \geq H(X|U)$$
...
2
votes
1answer
105 views
How is expected value in entropy derived?
I was self learning about entropy and came across this equation.
$$
H = - \sum p(x) \log p(x)
$$
The equation for entropy in expected value,
$$
H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
2
votes
1answer
50 views
Why is channel capacity of AWGN infinite?
My professor taught us that channel capacity of AWGN channel is infinite without any input power constraints. The noise is $Z \sim \mathcal{N}(0,\sigma^2) $. There is no constraint on input signal. I ...
0
votes
0answers
20 views
Significance of model in arithmetic coding
I am trying to understand the concept of arithmetic coding, i understand how the range is subdivided after each character is read from the string. But i am unable to understand why using a more ...
11
votes
6answers
1k views
Find the number using binary search against one possible lie
We all know this classic problem, "there is some hidden number and you have to interactively guess it.", which could be solved using binary search when we know that maximum number that we can guess.
...
2
votes
1answer
31 views
Worked out example of Slepian-Wolf Theorem
Note: First posted this on Theoretical Computer Science Stack Exchange, but deleted it from there since it seems to be off-topic.
The Slepian-Wolf theorem states that sequences of outputs from two ...
1
vote
3answers
164 views
What is implied probability, in the context of universal codes?
From Wikipedia:
Each universal code, like each other self-delimiting (prefix) binary
code, has its own "implied probability distribution" given by $ p(i)
={2}^{-\ell(i)} $ where $\ell(i)$ is ...
2
votes
1answer
44 views
Sums of $2^{-l}$ that add to 1
Consider the following problem:
You are given a finite set of numbers $(l_k)_{k\in \{ 1, ..., n \}}$ such that $\sum_{k=1}^n2^{-l_k}<1$. Describe an algorithm to find a set $(l'_k)_{k\in \{ 1, .....
3
votes
0answers
91 views
Capacity of channels: Why do we need Blahut-Arimoto algorithms?
The capacity of a noisy channel $\mathcal{E}_{X\rightarrow Y}$, where the channel is given as a conditional probability distribution $p(y|x)$, is
$$C = \max_{p_X}I(X:Y),$$
where $I(X:Y)$ is the ...
1
vote
0answers
24 views
Complexity of maximization of entropy of Hamming distance of bitstrings
We have a set of possible "key"s $S$ represented by bitstrings of length $k$. In other words, $S$ contains an arbitrary subset of all bitstrings of length $k$. For example, when $k=3$, it can be $S = \...
2
votes
1answer
40 views
on-the-fly decompress a flat-file database
I'm facing the following problem. I have a flat-file database (e.g. CSV).
Since it's relatively large to store in memory, I'd like to compress it.
Given a key, I need to return the uncompressed text (...
0
votes
1answer
56 views
Equivalence of two definitions of mutual information
I am learning quantum computing and as a background study, I am currently learning fundamentals of classical information theory.
I thought it best to ask my doubts here.
In Nielsen and Chuang, it is ...
1
vote
2answers
141 views
Data Compression :Compress a Compressed File
Suppose we have file A that has been compressed by the the method B and the output-file is C, now if I am not wrong We can not compress C more by method B, but there might another method=algorithm D ...
0
votes
1answer
120 views
How a Data Compression Software Reads a File as pure Binary File and makes Output?
I have an hybrid compression technique I want to implement, my implementation is (so far): I can encode a string into a encoded compressed string. These are binary strings. For example,
I read texts ...