Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

3
votes
1answer
28 views

Understanding the flaw in a proof attempt of the Communication Complexity of Equality

I'm new to communication theory and I've been wondering where the following simple argument fails: Equality Problem We have two players, player 1 Alice who gets an $n$-bit vector $X$ and player 2 Bob ...
2
votes
1answer
103 views

Lovasz theta of even cycle

How does one show Lovasz theta of even $n$-cycle ($n$ is even) is of form $\frac{n}{2}$? Why is the Lovasz theta of such cycles not of form $\frac{n \cos(\frac{\pi}{n})}{1+\cos(\frac{\pi}{n})}$. Could ...
0
votes
0answers
13 views

G1, G2, H1, H2 are submatrices of the generator and parity check matrices of a code as described below. Can G1 * H2' and G2 * H1' both be all zeroes?

$ G $ and $ H $ are the generator and parity check matrices respectively of a linear block code. Let $ G_1 = G(:, 1:n-s) $ (Matlab style representation of sub matrices). That is, $ G_1 $ is equal to ...
2
votes
1answer
46 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters? ...
4
votes
1answer
44 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
19 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
53 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
54 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
98 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
30 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
38 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 ...
3
votes
3answers
144 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
103 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
31 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
65 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
22 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
25 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
67 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
198 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
149 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
40 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
132 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
128 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
186 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
107 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
123 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
324 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
105 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
113 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
452 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
137 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
144 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
315 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
249 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
482 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
682 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
80 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
885 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
265 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
187 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
211 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
159 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
123 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 ...