-1
votes
0answers
22 views

Entropy of sum of two dependent random variables [on hold]

What is the entropy of sum of two dependent random variables, $$h(X+Y)$$ when X y Y have the same distribution. In particular, is it larger or smaller than the entropy of the sum of two ...
1
vote
2answers
49 views

Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
1
vote
0answers
16 views

Encoder based on large similar data

Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...
10
votes
3answers
266 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
3
votes
0answers
88 views

Which takes more energy: Shuffling a sorted deck or sorting a shuffled one?

You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
1
vote
1answer
98 views

Space : Kolmogorov complexity :: time and space : ___?

It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
1
vote
1answer
125 views

A Measure for Number of Unique N-Tuples

Suppose I have a multiset of numbers. I'm interested in the number of unique n-tuples that can exist using the numbers from this multiset. Now of course a closed form is of interest here, but what I'm ...
1
vote
1answer
170 views

Maximally entropy preserving irreversible functions. (CS related)

The topic/problem is related to hashing for data structures used in programming, but I seek formal treatment. I hope that by studying the problem I will be enlightened of the fundamental limitations ...