The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
32 views

Mutual information intuition

I was creating an example for a casual talk on mutual information. I considered a system of two coins, which with probability 1/2 are copies of each other, and with probability 1/2 are independent. ...
1
vote
1answer
17 views

Entropy sources: Weaver (1949) typo?

In Recent Contributions to The Mathematical Theory of Communication (Weaver 1949), aka The Mathematics of Communication (Weaver 1949) (various copies exist online), and also published as Part I of The ...
1
vote
1answer
29 views

Why the alphabet of the digital information is composed of 2 elements? [duplicate]

please don't offer an answer about "it's an electronic thing" or something like that, just keep reading. I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the ...
2
votes
1answer
51 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...
3
votes
1answer
39 views

Error-correction code for transmission only with bit-flipping from 0 to 1

I am using a transmission system that uses a Bloom filter (this part is out of my control). I want to send a small amount of data (32 bits) using this system. For each bit [0,31], I add its index to ...
3
votes
1answer
88 views

Conceptual question about entropy and information

Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that ...
2
votes
0answers
29 views

How to compare conditional entropy and mutual information?

I am solving a problem of information theory. The problem reads, Consider a stationary memoryless channel specified by the channel matrix $T = \begin{pmatrix}1-q&q\\r&1-r\end{pmatrix}$. ...
0
votes
1answer
33 views

Number of phrases of LZ compression

It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds: $$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$ With ...
2
votes
3answers
120 views

Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?

The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers. An ...
0
votes
1answer
99 views

Bayesian Nets & Markov Blanket

As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem. In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to ...
1
vote
1answer
27 views

Mutual Information in a Binary Erasure Channel

Imagine a Binary Erasure Channel as depicted on Wikipedia. One equation describing the mutual information is: $$ \begin{align*}I(x;y) &= H(x) - H(x|y) \\ &= H(x) - p(y=0) \cdot 0 - p(y=?) ...
0
votes
1answer
61 views

Information loss of a 9-input majority gate [closed]

According to information theory, the logic gates AND, NAND, OR, NOR all lose 1.189 bits of information each with two bits of information at their inputs and with all inputs being independently and ...
24
votes
7answers
2k views

Can PRNGs be used to magically compress stuff?

This idea occurred to me as a kid learning to program and on first encountering PRNG's. I still don't know how realistic it is, but now there's stack exchange. Here's a 14 year-old's scheme for an ...
1
vote
1answer
21 views

On Shannon Capacity

Let $G$ be a graph whose Shannon Capacity is $\Theta(G)$. Is there any graph product for which the Shannon Capacity is $\Theta(G)^k$ where $k$ is the number of times the product is taken?
1
vote
1answer
24 views

Do the two huffman trees have the same corpus?

Consider the following Huffman trees: I was asked if those trees can have the same corpus. My answer was no, based on these calculations: For the right tree: $a_1 \le a_2$ $a_1 + a_2 \le a_5$ ...
5
votes
1answer
60 views

Showing that the entropy of i.i.d. random variables is the sum of entropies

The shannon entropy of a random variable $Y$ (with possible outcomes $\Sigma=\{\sigma_{1},...,\sigma_{k}\}$) is given by $H(Y)=-\sum\limits_{i=1}^{k}P(Y=\sigma_{i})\;\log(P(Y=\sigma_{i}))$. For a ...
2
votes
1answer
122 views

Gap between the average length of a Huffman code and its entropy

Difference between “average length” and “entropy” gives the percent of optimal. The optimal case is when the average length of a code is equal to the entropy. For example if average length is 1 and ...
3
votes
2answers
134 views

Compressing normally distributed data

Given normally distributed integers with a mean of 0 and a standard deviation $\sigma$ around 1000, how do I compress those numbers (almost) perfectly? Given the entropy of the Gaussian distribution, ...
0
votes
2answers
38 views

Arithmetic code: from interval to code value

I've not clear how to pass from final interval to code value, for example: Suppose we have the set of symbols={0,1,2,3} with probability={0.2, 0.5, 0.2 , 0.1} and that we have to encode a source ...
0
votes
1answer
40 views

Information capacity of Ternary-based system over Binary-based

Some researchers are trying to get a memory cell capable of having 3 states instead of 2. 1) How many memory cells, in principle and as a rough estimate, does a typical 1 megabyte memory chip has? is ...
1
vote
2answers
51 views

Why are bytes treated like the base unit?

If bits are the base unit of information, why are bytes treated like the base unit? For example, usually values are expressed in Mega/Giga/Tera/Exa bytes instead of bits. I am aware that bits are ...
1
vote
1answer
122 views

LZW decoding process

I'm trying to understand how LZW decodes a string. For example suppose that we have a dictionary where: a=0 b=1 and we have to encode the string "aabbabaabb", so the output of the encoding ...
2
votes
0answers
52 views

Notions of computational hardness in terms of information flow?

If we consider polynomial-time (or log-space) computable reductions $<_p^m$ as transformations between computational problems, then the following definitions of known complexity classes suggest ...
2
votes
1answer
124 views

Estimate entropy, based upon observed frequency counts

Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution. I can count the ...
3
votes
3answers
182 views

compressed information = randomness?

Suppose I have a compressed file and it is not possible to compress it more without loss of information. We say that this file is random or pseudorandom. So, if the randomness means not ...
1
vote
3answers
105 views

Is there a correlation of zip compression ratio and density of information provided by a text?

I'll phrase my question using an intuitive and rather extreme example: Is the expected compression ratio (using zip compression) of a children's book higher than that of a novel written for adults? ...
-1
votes
1answer
70 views

Information of a stream of bits

Here is my problem. I have to compute the amount of information that is possible to encode in a string of bits. This string of bits represent a stream. Let us call such stream as ...
0
votes
1answer
120 views

Notions of information content and randomness of binary square matrix

We have well established theory for measuring the information content and randomness of binary strings. Notions such as Shanon entropy and Kolmogorov-complexity were developed for binary strings. For ...
14
votes
2answers
319 views

What's harder: Shuffling a sorted deck or sorting a shuffled one?

You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a < b$) and a truly random source of bits ...
6
votes
1answer
104 views

How are data types related to information theory?

I was just reading from wikipedia the following about information: From the stance of information theory, information is taken as a sequence of symbols from an alphabet, say an input alphabet χ, ...
2
votes
1answer
107 views

Mutual information and moment generating functions

I went to listen to a workshop and someone from the audience asked the presenter how the moments can improve the mutual information. I am learning about MI (Mutual Information) so didn't have enough ...
3
votes
1answer
435 views

Pointwise mutual information vs. Mutual information?

I am learning about information theory and mutual information. However, I am quite confused with MI(Mutual information) vs. PMI(Pointwise mutual information) especially signs of MI and PMI values. ...
4
votes
1answer
133 views

Information theory from a (very pure) mathematician's perspective

I'm a pure mathematician interested in learning about information theory. Unfortunately, I'm about as pure as they come - my specialty is mathematical logic, and I have absolutely no experience with ...
3
votes
1answer
95 views

$\ell_1$ Minimization of Probability Distribution and KL-Divergence

Suppose through $\ell_1$ minimization I obtained two sparse probability distributions $P, Q$ which may contain many zero terms. Then I would like to compute the KL-Divergence of them $D(P || Q) = ...
2
votes
2answers
139 views

Generalized data structure

Data structures are seen as important, equal to algorithms. This view is especially encouraged in situations, where appropriate data structure is the main factor that allows an algorithm to exist and ...
6
votes
1answer
301 views

Generalizing the Comparison Sorting Lower Bound Proof

Let's start with the comparison sorting lower bound proof, which I'll summarize as follows: For $n$ distinct numbers, there are $n!$ possible orderings. There is only one correct sorted sequence of ...
8
votes
1answer
237 views

Rényi entropy at infinity or min-entropy

I'm reading a paper that refers to the limit as n goes to infinity of Rényi entropy. It defines it as ${{H}_{n}}\left( X \right)=\dfrac{1}{1-n} \log_2 \left( \sum\limits_{i=1}^{N}{p_{i}^{n}} \right)$. ...
4
votes
1answer
443 views

What units should Shannon entropy be measured in?

The only examples I've seen use bits as a measurement of entropy, but all these examples happen to use binary code alphabets. If we wanted to see how well a coding with a code alphabet of length n ...
2
votes
4answers
653 views

Is there any theoretically proven optimal compression algorithm?

Is Huffman coding always optimal since it uses Shanon's ideas? What about text, image, video, ... compression? Is this subject still active in the field? What classical or modern references should I ...
4
votes
1answer
79 views

What are the rudimentary types of information connectivity i.e. model types?

I am looking at a modelling tool and are trying to determine all the types of ways that you can model (at a rudimentary level) I remember seeing a list of ways in which you can connect or categorise ...
5
votes
3answers
793 views

Is Huffman Encoding always optimal?

The requirement of the encoding to be prefix free results in large trees due to the tree having to be complete. Is there a threshold where fixed-length non-encoded storage of data would be more ...
6
votes
1answer
256 views

Measuring entropy for a table (e.g., SQL results)

We're running some benchmarks for an approximative query-answering system. It's sufficient to just think of it as running some SQL queries with joins. We are counting the results returned as part of ...
3
votes
1answer
186 views

Source entropy and other questions related to information theory

Kolmogorov-Sinai entropy (KS) explains the mathematical concept behind KS entropy. $$h ( T ) =\sup\limits_{\xi} \, h ( T , \xi )$$ defines the formula for KS where the left-hand side is nothing but ...
0
votes
1answer
207 views

Time series probability and mutual information

There is a time series of say $100$ data points. I wish to assign symbols of $0, 1, 2$ for each unique data point. The issue is I have tried but got stuck since no matter I specify the symbols, the ...
3
votes
1answer
157 views

Operations on OBDD: negation through Shannon's expansion

I have a problem with the application of the Shannon expansion for to obtain the negation of a formula boolean, than will need for implement the negation operator on OBDD (Order Binary Decision ...
7
votes
1answer
122 views

Prove fingerprinting

Let $a \neq b$ be two integers from the interval $[1, 2^n].$ Let $p$ be a random prime with $ 1 \le p \le n^c.$ Prove that $$\text{Pr}_{p \in \mathsf{Primes}}\{a \equiv b \pmod{p}\} \le c ...
2
votes
1answer
380 views

Can the Bell-LaPadula model emulate the Chinese Wall model?

I have been reading on security policies and the question wether Bell-LaPadula can be used to implement Chinese Wall. Does anyone know more about it?
5
votes
1answer
103 views

Why are blocking artifacts serious when there is fast motion in MPEG?

Why are blocking artifacts serious when there is fast motion in MPEG? Here is the guess I made: In MPEG, each block in an encoding frame is matched with a block in the reference frame. If the ...
12
votes
3answers
304 views

Difference between “information” and “useful information” in algorithmic information theory

According to Wikipedia: Informally, from the point of view of algorithmic information theory, the information content of a string is equivalent to the length of the shortest possible ...
8
votes
1answer
147 views

Error-correcting rate is misleading

In coding theory, 'how good a code is' means how many channel errors can be corrected, or better put, the maximal noise level that the code can deal with. In order to get better codes, the codes are ...