Questions tagged [information-theory]
Questions about Information theory, entropy, and information content of various sources
264
questions
0
votes
0answers
11 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
9 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
20 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
30 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
110 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 ...
2
votes
2answers
62 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
38 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
24 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
22 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
18 views
Capacity of broadcast channels
It is given in the book by El Gamal that
The capacity region of the DM-BC depends on the channel conditional
pmf $p(y_1 , y _2 |x)$ only through the conditional marginal pmfs $p(y_1 |x)$ and $p(y_ 2 |...
0
votes
0answers
30 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)$$
...
0
votes
0answers
12 views
Joint typicality and distance between the vectors
In the book by Cover and Thomas,the author says that
We first review the single-user Gaussian channel studied in Chapter 9.
P
Here Y = X + Z. Choose a rate R < 12 log(1 + N
). Fix a good ($2^{nR}$ ...
1
vote
1answer
23 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
44 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.
...
1
vote
1answer
21 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
142 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
41 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
58 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
22 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
26 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
34 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
65 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
55 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 ...
1
vote
1answer
29 views
Encoding System that Assign Same Number of Bits for Each Character
I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that ...
1
vote
1answer
37 views
What is the difference between rateless and online encoding?
Definitions of Rateless encoding and Online encoding are as follows.
Error-correcting codes that employ no fixed block length are called rateless or fountain codes.
Online encoding refers to the ...
1
vote
0answers
24 views
Auxiliary random variables in the analysis of the private information of wiretap channels
I am following Section 13.2 of Mark Wilde's book. I reproduce the question here for completeness.
Consider a wiretap channel $X\rightarrow Y,Z$ defined by the conditional probabilities $p(y,z|x)$ for ...
1
vote
0answers
45 views
Decomposition of Mutual Information
I came across a book where the author uses the following property of mutual information:
Let $X$,$Y$,$Z$ be arbitrary discrete random variables and let $W$ be an indicator random variable.
$$
(1)\ \ ...
2
votes
1answer
175 views
Collision entropy definition
The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by
$$\mathrm{H}_{2}(X)=-\log \sum_{i=1}^{n} p_{i}^{2} \tag{1}$$
Take two random variables $X$ and $X'$ ...
2
votes
1answer
58 views
Information theory of instruction set architecture design?
Information theory to a large extent deals with how to efficiently encode messages given a probability distribution over messages.
Intuitively, it seems like we can think of machine instructions (or ...
1
vote
1answer
26 views
Example of a prefix-free code
I came across the following question:
A source $X$ emits symbols from the alphabet $A_x$ with $|A_x| = 8$. We want to construct a prefix-free source code for this source.
We want to find a code with ...
0
votes
1answer
34 views
Capacity of a discrete memoryless channel
For an integer $I$, the input-output relationship of a discrete memoryless channel is given by:
$Y = X + Z$ (mod $I$, i.e. sum indicates a modular addition)
where $I ≥ 2$,
and
• $X$ is an integer ...
0
votes
0answers
17 views
Is there a word for the fact that all data representations are equal?
For programming languages, we have the concept of Turing completeness which expresses the fact that all computers and all languages are equal in their ability to represent any algorithm so long as we ...
3
votes
1answer
37 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
57 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
55 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
138 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
37 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
52 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
35 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
1answer
58 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
58 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
109 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
74 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
32 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
52 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
73 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
119 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 ...
