Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
56 views

Binary compression algorithm with decompress by index

I have a list of 256-bit binary data to store. Any algorithm for doing lossless compression on it in a way I can retrieve an entry by its index without decompressing the whole data (if possible). The ...
user avatar
1 vote
1 answer
27 views

Chain rule for mutual information

I am a bit confused in the following definition: what does comma mean. I know I(X;Y) is the mutual information between X and Y but I am not sure how to interpret the I(X_1,X_2;Y)).
user avatar
  • 143
1 vote
1 answer
170 views

Undecidability in optimal data compression

There is this certain slide in Coursera Computer Science: Algorithms, Theory, and Machines course: I think it is saying finding the optimal size of given data is undecidable. However, I thought there ...
user avatar
  • 143
1 vote
0 answers
36 views

Is there a method for information transfer without copying the data?

What I mean is, if in real life I had an object and I gave it to you, I would not have it anymore. I did not give you a copy of the object. Is there a way to do that with information?
user avatar
  • 11
0 votes
0 answers
22 views

How to compress highly correlated arrays?

I want to write a compression algorithm for a specific use case that I have. I have many arrays which are for the most part, very similar. Each value in the array is an integer and is related to the ...
user avatar
1 vote
4 answers
1k views

What is the name of the following binary encoding?

S is a the set of binary strings in Shortlex order: [0,1,00,01,10,11,...] I want to encode / decode natural numbers with the following scheme: Encoding N: For ...
user avatar
  • 287
1 vote
0 answers
15 views

What does it mean for an algorithm to not resample points?

The No Free Lunch theorems for search and optimization demonstrate that for search/optimization problems in a limited search space, where the points being searched through are not resampled, the ...
user avatar
0 votes
1 answer
45 views

If all words have the same frequency, is the generated Huffman tree a balanced binary tree?

If all words have the same frequency, is the generated Huffman tree a balanced binary tree? At the same time, is the generated Huffman tree a complete binary tree?
user avatar
  • 11
1 vote
0 answers
19 views

Noisy channel coding: how to design a code for a discrete channel

When determining the capacity of a discrete channel, we maximise mutual information, and in doing so find the optimal input distribution for that channel. I know that the noisy-channel coding theorem ...
user avatar
1 vote
1 answer
44 views

Entropy of $\{X_1,\ldots,X_T\}$ where $X_1,\ldots,X_T \in_R [Q]$

I have a noiseless T-user multiple access channel. Let $[Q] = \{1, \dots , Q \}$. The users send symbols $X_i ∈[Q], i = 1, \dots , T$ . The channel is defined as follows $$(X_1, X_2, \dots , X_T) → Y$$...
user avatar
0 votes
1 answer
59 views

Upper bound of sum of codewords lengths

I need to show that for any binary optimal code for $n$-letter source the following inequality holds: $$\sum_{i=1}^n l_i \leq 0.5(n + 2)(n −1).$$ By $l_i$ denoted the length of the sequence ...
user avatar
1 vote
1 answer
43 views

Sorting lower bound is linear when only a constant number of distinct keys?

I saw this proposition on Sedgewick's lecture slides on QuickSort, and I've been wondering why the number of comparisons is linear in the case of a constant number of distinct keys. I tried to ...
user avatar
0 votes
0 answers
11 views

What does it exactly mean by information management as a function of O/s

I have read that information management is a function of O/s by which it A) Manages, stores, retrieves,modify data. It makes sure that right people have access to their information. B) Some of the ...
user avatar
0 votes
0 answers
12 views

How many code alphabets do we need in order for a Huffman Code and a Shannon-Fano Code to be the same for the same source symbols probability

For example, If we have a source with alphabet $\{x, y, z\}$ with probabilities $\{0.5, 0.3, 0.2\}$ , What is the smallest integer $\mathbf{D}$ such that the expected length of a D-ary Shannon-Fano ...
user avatar
  • 1
1 vote
0 answers
34 views

How to decode shortened Reed-Solomon code?

I am working with a shortened version of $[n,k,d]$ Reed-Solomon code. I am encoding a message of size $k−l$ which gives a shortened code of size $n−l$ (this is equivalent to encoding the same message ...
user avatar
0 votes
0 answers
10 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 ...
user avatar
0 votes
0 answers
15 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 ...
user avatar
3 votes
1 answer
52 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 ...
user avatar
  • 31
2 votes
0 answers
13 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 ...
user avatar
1 vote
2 answers
77 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 ...
user avatar
1 vote
3 answers
66 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/...
user avatar
  • 111
1 vote
1 answer
56 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 ...
user avatar
  • 113
2 votes
1 answer
99 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 ...
user avatar
2 votes
0 answers
19 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://...
user avatar
3 votes
1 answer
70 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 &...
user avatar
1 vote
0 answers
31 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 ...
user avatar
0 votes
1 answer
31 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$ ...
user avatar
  • 21
1 vote
1 answer
30 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, ...
user avatar
  • 3,464
2 votes
1 answer
23 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 (...
user avatar
  • 131
1 vote
0 answers
59 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. ...
user avatar
  • 11
2 votes
1 answer
95 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 ...
user avatar
  • 123
0 votes
1 answer
42 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 ...
user avatar
  • 115
0 votes
1 answer
439 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 ...
user avatar
1 vote
1 answer
314 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)...
user avatar
  • 25
2 votes
1 answer
65 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 ...
user avatar
1 vote
1 answer
15 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 ...
user avatar
  • 13
0 votes
1 answer
77 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 ...
user avatar
3 votes
2 answers
118 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 ...
user avatar
2 votes
0 answers
21 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 &...
user avatar
1 vote
1 answer
34 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 ...
user avatar
  • 121
1 vote
1 answer
36 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 ...
user avatar
3 votes
2 answers
135 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 ...
user avatar
3 votes
2 answers
98 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 ...
user avatar
2 votes
0 answers
101 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 ...
user avatar
0 votes
1 answer
106 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&...
user avatar
1 vote
1 answer
27 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}{...
user avatar
2 votes
1 answer
40 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 ...
user avatar
0 votes
0 answers
36 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)$$ ...
user avatar
2 votes
1 answer
250 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)] = -\...
user avatar
  • 131
2 votes
1 answer
56 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 ...
user avatar

1
2 3 4 5 6