5
votes
2answers
100 views

How to Count the number of words over an alphabet subject to restrictions on letter count?

For an alphabet $X$, is there a method of computing how many words over $X$ of length $n$ there are where the number of occurrences of each letter must satisfy a system of equations? For example if ...
2
votes
1answer
71 views

Is there a combinatorial explanation for this identity related to Kraft's inequality?

Kraft's inequality involves the quantity: $$\sum_{x \in X} \frac 1 {b^{\ell(x)}} \tag 1$$ Where we are considering a code mapping symbols in the alphabet $X$ to strings in an alphabet of $b$ ...
1
vote
1answer
25 views

Information content of an unlabelled matrix

I'm trying to get an idea of the amount of information that is "stored" in an "unlabelled" matrix. I assume that the vector $(x,y,z)$ contains more information than the set $\{x,y,z\}$. But purposely ...
0
votes
0answers
16 views

Can small subsets of a large set be lossily compressed with one-sided error?

Because I'm allowing error, my question is not a duplicate of Compressing a short list of very large numbers?, although they are very similar. For large finite sets $U$ and non-negative integers $n$ ...
2
votes
0answers
32 views

A question regarding binomial coefficient

This question arose during solving an information theory problem. Suppose $l$ is the smallest integer such that $$2^l\geq {n\choose k}$$ define $\rho=\frac{k}{n}$. How we can characterize $\rho$ as a ...
2
votes
0answers
30 views

Is it true that $\sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}$?

Given $q \in \mathbb N$, $q\geq 2$ is it true that \begin{equation*} \sum _{i=0}^a (q-1)^i\binom {n}{i} \leq q^{H_q(a/n)n}? \end{equation*} Here $H_q(x) = x\log _q(1/x) + (1-x)\log _q(1/(1-x))$ is the ...
2
votes
1answer
91 views

3-bit sensors — A question about Hamming distance in signals

I came across this question on Willy Wu's riddle site You have two 3-bit sensors, A and B, that measure the same thing, whatever it is -- temperature of the room, radioactivity levels, whatever. ...
1
vote
0answers
36 views

Hiking trip distribution

I have a real life problem. My friends and I are going on a hiking trip and there's a bunch of items (mostly food) that we want to distribute among us so everyone carries approximately equal weight. ...
0
votes
1answer
50 views

Easy bound involving logs and binomial coefficients

I am currently working on an information theory problem where I have to bound the divergence between two distributions. The divergence can be simplified to: $$\sum_{k=0}^N \ {N\choose k} ...
28
votes
2answers
310 views

Information-theoretic aspects of mathematical systems?

It occured to me that when you perform division in some algebraic system, such as $\frac a b = c$ in $\mathbb R$, the division itself represents a relation of sorts between $a$ and $b$, and once you ...
1
vote
1answer
98 views

Expression for the size of type class, or multinomial coefficient.

The notations follow those in Cover&Thomas, "Elements of Information Theory", 2ed. I saw from a paper that the size of type class $T(P)$ can be expressed as ...
1
vote
1answer
69 views

generalization of base-n notation from naturals to fractions

not exactly sure how to best ask this. base-$n$ notation involves a series of digits written where each digit is a natural number less than $n$. is there some math/theory generalization of ...
3
votes
1answer
90 views

How to guess a binary code with feedback

Suppose I want to guess a binary code, where the quality of my guess is provided by an evaluation function. I imagine a safe, where the user enters a binary code by flipping $N$ switches. After ...
3
votes
1answer
145 views

Intuition about the relation of combinations and entropy

It is not difficult to show that $${n \choose \lambda n} \leq 2^{H(\lambda)n}$$ where $H$ is the binary entropy function: $$H(\alpha) = -\alpha \lg \alpha - (1-\alpha)\lg (1-\alpha)$$ I was ...
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
424 views

How to calculate/approximate expectation of function of a binomial random variable?

I am stuck at following problem in my research. Suppose that $M=m$ is a random variable with binomial distribution and parameters $n,p$. The constants $r$ and $\gamma$ are greater than zero. ...
15
votes
3answers
2k views

Expanding and understanding the poison pills riddle

You might have heard of the riddle that asks you to identify one fake pill (poisoned) among 12 pills of identical appearance, with the fake pill being either lighter or heavier than the others. You ...