Questions tagged [information-theory]

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

Filter by
Sorted by
Tagged with
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
111 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
85 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
63 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
45 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
103 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
71 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
48 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
45 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
113 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
46 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
24 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
49 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
327 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$, ...
2
votes
2answers
144 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
1
vote
1answer
123 views

Practicality of compressing data with hashing algorithms

I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string. I ...
2
votes
1answer
230 views

Why does the time/space tradeoff exist

I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff. Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff. ...
2
votes
2answers
5k views

Prove that Hitting Set is NP-Complete

The Hitting Set Problem (HS) is defined as follow. Let $(C,k$) $C = \{ S_1, S_2, ..., S_m \}$ collection of subset of S i.e. $ S_i \subseteq S , \forall i$ $k \in \mathbb{N}$ We want to know if ...
3
votes
2answers
53 views

Are typical sets larger, when information is messier?

Let $0\le q<p\le \frac{1}{2}$, and let $P,Q$ be two Bernoulli Random Variables such that: $$Pr[P=1]=p ; Pr[P=0]=1-p$$ and $$Pr[Q=1]=q ; Pr[Q=0]=1-q$$ My question: Does it follow that, for any $\...
4
votes
3answers
125 views

Do most bitstrings expand if they halt when executed by a Universal Turing machine?

According to the counting argument, most bitstrings are incompressible or only slightly compressible. However, the counting argument does not work in the opposite direction, since there are an ...
4
votes
1answer
639 views

Understanding of self-information

I am trying to fully understand the meaning behind the self-information of events. While I totally understood how to calculate it, all explanations I find online lack of an explanation why less likely ...
0
votes
0answers
65 views

[Choosing tunable parameter M in Golomb/Rice Encoding]

I am a Computer Science student and I study Data Compression now. I read many methods but Golomb-Rice Encoding was not clear for me. I understand the method how it works but in the algorithm there is ...
2
votes
1answer
50 views

Bound covariance of two discrete random variables

Let $X,Y$ be two random variables over a discrete probability space, such that $X \in [0,1]$ and $Y \in [0,1]$. I want to prove that $$ |\text{Cov}[X,Y]| \leq \sqrt{0.5 \; I[X,Y]}$$ where $I[]$ is ...
1
vote
1answer
43 views

What is The correct terminology for expressing *this* notion of complexity

Say for example, I have an algorithm $Al_i$ that produces output from the set $S = \{s_i\}$ for problems from the set $P = \{p_i\}$, and another algorithm $Al_j$ that also produces output from the set ...
0
votes
0answers
490 views

How does youtube do video quality change/video compression?

After uploading a high definition video in youtube, youtube automatically makes a low definition(standard definition) version of the video. I would like to know what algorithm they use to reduce the ...
1
vote
0answers
104 views

Second-order Markov text generation?

Looking at this video starting at 1:45, the author claims to be using a second-order approximation for a Markov text generation. He has one letter which he outputs followed by another letter which ...
1
vote
1answer
87 views

Calculating the information density of an encoding system

How do I calculate the information density of an encoding system? This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major ...
0
votes
1answer
394 views

How can I estimate Bhattacharyya parameter for BSC channel, used for Polar codes

In polar codes, the frozen bits in each message are determined through the worst channel, where the relevant parameter is the Bhattacharyya . How can I estimate Bhattacharyya parameter for BSC ...
2
votes
2answers
844 views

Conceptual overview: Self-information, Mutual information, uncertainty, entropy

I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x_i, y_i$ as events of experiments $X, Y$. Self-information, ...
1
vote
1answer
102 views

What should be the way to design code for such a situation?

I have a graph as given below: Let us assume one node as transmitter and another as receiver. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
0
votes
1answer
125 views

Choosing a shortest representative number from interval in arithmetic coding

In arithmetic coding a word is coded as the binary encoding of a number in a certain interval. The interval is determined from a sequence of nested intervals according to the probability distribution ...
7
votes
1answer
425 views

Impossibility for Byzantine Generals Problem where $n \leq 3m$

Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the ...
1
vote
1answer
150 views

Higher order empirical entropy is not the entropy of the empirical distribution?

Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H_k(x)$ (see "Backround" at the end of this post for more information) for a given string $...
26
votes
6answers
10k views

Efficient compression of simple binary data

I have a file containing ordered binary numbers from $0$ to $2^n - 1$: 0000000000 0000000001 0000000010 0000000011 0000000100 ... 1111111111 7z did not compress ...
0
votes
0answers
59 views

Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
0
votes
1answer
174 views

Calculate joint entropy of a Hamming Code over a Binary Symmetric Channel?

I have a normal (7,4,3) Hamming Code over GF(2) and a parity check matrix for it (not posted, because I don't think it's involved). I have a set X of 4 bit source vectors called x. They all have ...
3
votes
1answer
90 views

Finding the dichotomy that maximizes information gain for a classifier?

Suppose that $\Omega$ is a finite probability space,with measure $P$ (we can take $P$ uniform). Let $C \in \{\pm 1 \}$ be a random variable on $\Omega$, the classifier. Let $$H(C) = H(C, \Omega, P) = ...
2
votes
1answer
102 views

Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley. Does there exist a compact instantaneous binary encoding ...
2
votes
0answers
264 views

The meaning of ontology in computer science

I am reading a paper and ran into this word Ontology-based, What does it really mean? I did searching about it but still ambiguous to me, can someone elaborate this ...
2
votes
1answer
42 views

Repeated fingerprinting after array updates

I've got a microprocessor and want to quickly identify the settings of my application (stored in some eeprom regions) via a fingerprint instead of having to dump the entire memory every time. So I ...
3
votes
1answer
216 views

Minimum bits needed when representing a value in a set

I'm reading a paper entitled "Succincter" which discusses a compression scheme that involves encoding a value as a sequence of $M$ bits, along with a "spillover" value which can be recursively encoded....
5
votes
3answers
605 views

Arithmetic coding and “the optimal compression ratio”

Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be ...
11
votes
3answers
1k views

PRNG for generating numbers with n set bits exactly

I'm currently writing some code to generate binary data. I specifically need to generate 64-bit numbers with a given number of set bits; more precisely, the procedure should take some $0 < n < ...
1
vote
1answer
63 views

Can the set of all $2^{24}$ colors be expressed as a ternary linear code?

Consider the usual RGB color palette, for which each color (red, green, blue) has $256$ distinct intensities. Can the set of all $2^{24}$ colors be expressed as a ternary linear code? If so, give a ...
3
votes
1answer
167 views

Algorithms that achieve better compression for more data

I'm interested in compression algorithms where the compression ratio increases as the amount of data to be compressed increases. Let's call this "super compression". Could super compression be ...
0
votes
0answers
72 views

If you want to archive (and compress) a number of files into one archive is it more efficient to archive first and then compress?

When compressing multiple files, is it more efficient to (1) first compress each individual file separately and then concatenate/merge the results, or (2) first concatenate/merge the files into a ...
0
votes
1answer
31 views

Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$

Prove that $H_r(S) = H(s) / \log_2r$. I'm not sure how to prove this. Any help would be greatly appreciated!
6
votes
3answers
271 views

Are there lossless data compression techniques that do not exploit repetitive patterns?

Lossless Data compression (source coding) algorithms heavily rely on repetitive pattern (redundancy). Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern ...
1
vote
1answer
32 views

Problems with the proof of Huffman Optimality in Cover's book

There is a some question that arise from the proof of Lemma 5.8.1 of Cover's book on information theory that confuse me. First question is why he assumes that we can "Consider an optimal code $C_m$. ...