15
The intended answer is probably that the length of the longest codeword is approximately $$-\log_2 10^{-6} = 20.$$ But this is wrong. The information given doesn't come close to specifying the length of the longest codeword. Even the entire probability distribution doesn't specify the length of the longest codeword.
One can see this by constructing a ...
11
The answer is no.
I'll give an example of a language $L$ which is regular in binary but not in unary:
Consider $L=\{10^k|k\in \mathbb{N}\}$. The corresponding language in unary is $L'=\{1^{2^k}|k\in \mathbb{N}\}$.
It's easy to see that $L$ is regular while $L'$ is not even context free.
L'' also isn't regular either, by the link @Sylvain posted in his ...
8
From a mathematical perspective: Try
1) Handbook of coding theory - Huffman and Pless
2) Fundamentals of Error-Correcting Codes - Huffman and Pless
3) Introduction to coding theory - Ron Roth
4) Algebraic Geometric Codes: Basic Notions - Vladut, Nogin and Tsfasman
5) Introduction to Coding Theory - Van Lint
6) Algebraic ...
7
When the base k representation is regular, the set is called k-automatic
The wikipedia article on these reads:
For given "k" and "r", a set is "k"-automatic if and only if it is "k^r"-automatic. Otherwise, for "h"and "k" multiplicatively independent, then a set is both "h"-automatic and "k"-automatic if and only if it is 1-automatic, that is, ultimately ...
6
The answer is $C_{n-1} n!$ . That is, the $(n-1)$st Catalan number times $n$ factorial.
There are $C_{n-1}$ ways of making a complete binary tree with $n$ leaves, and there are $n!$ ways of assigning these leaves to the symbols to get a Huffman code.
This sequence goes 2, 12, 120, 1680, 30240, and is listed in the Online Encyclopedia of Integer Sequences ...
6
Sphere packings give a nice analogue of codes over $\mathbb{R}$. A sphere packing is a set $\mathcal{P} \subset \mathbb{R}^n$ such that $d_{\mathcal{P}} := \inf_{x,y \in \mathcal{P}, x \neq y} \|x - y\| > 0$, where $\|\cdot \|$ is the Euclidean norm. This is called a sphere packing because we can place a(n open) sphere of radius $d_{\mathcal{P}}/2$ at ...
5
It is possible to define codes over infinite fields, but it is usually not as useful as codes over finite fields. The original motivation for error-correcting codes comes from the needs to transmits bits over a noisy channel. Over such a channel, it is usually not possible to send real numbers with arbitrary precision.
However, there have been some works ...
5
As pointed out by others, the obvious definition of an "adequate" coding is that it is equitranslatable with any standard one. The question is therefore to characterize such codings in terms of more elementary properties.
(Historical note. Smullyan studied this question in the context of combinatory logic. When I was a student, Henk Barendregt suggested ...
5
What you're looking for is called a "succinct" or "implicit" dictionary. The best solution I know of is Backyard cuckoo hashing, by Arbitman et al from FOCS 2010, which "guarantees constant-time [insert, delete, lookup] operations in the worst case with high probability" while using $B + o(B)$ bits, where $B$ is the lower bound you mention.
If you need ...
4
$\newcommand{\Alg}{\mathsf{Alg}\ }$
$\newcommand{\NatF}{\mathsf{NatF}\ }$
$\newcommand{\Nat}{\mathsf{Nat}}$
$\newcommand{\map}{\mathrm{map}\ }$
$\newcommand{\Z}{\mathrm{Z}}$
$\newcommand{\S}{\mathrm{S}}$
I don't think this is an actual counter-example.
Parametricity implies:
$$∀(α : \Alg \NatF t) (g : r → t)(x : \NatF r). \\
α\ [r]\ g\ x = α\ [t]\ (λx.x)\ (\...
4
Note: See the edit at the bottom for an argument showing that there is an unbiased algorithm which has variance strictly lower than $1/12$ for all $x \in [0,1]$.
We can at least prove that if $x$ is chosen uniformly from $[0,1]$, then the average variance must be at least $\pi^2/64 - 1/12$. There is a dithering algorithm that achieves this average-case ...
4
Answer to question 1: $\left\lceil \log_2 \binom{M-1}{r-1} \right\rceil$ bits suffice to encode the variables.
Proof: Count how many ways there are to choose $y_1,\ldots,y_r$ such that $y_i \ge 0$ and $\sum y_i = M-r$. There are exactly $\binom{M-1}{r-1}$ such ways (see e.g. here). Now, if there are only $k$ possible values for a variable, then $\lceil \log ...
4
Lecture notes of the course "An Algorithmic Introduction to Coding Theory," by Madhu Sudan.
Publication Date: 2001. The first chapter offers useful comments regarding several textbooks on coding theory.
Available at http://people.csail.mit.edu/madhu/FT01/scribe/overall.pdf.
4
This is not an answer. It is an elaboration of the question, that looks interesting to me and maybe should deserve more attention than it actually received.
First of all, let me say that there is an important condition in Barendregt's definition that has been omitted by Brennan, namely the fact that $\lceil M \rceil$ must be in normal form, that immediately ...
3
$S_δ$ is not a subset of the typical set. As you mentioned, the most probable element is a member of $S_δ$ but it is not necessarily a member of the typical set.
The only reason to use the typical set instead of $S_δ$ is to make the proof of the source coding theorem easier. (See the paragraph at the top of page 84 in your book.) The typical set along with ...
2
Before we try to get into ergodic or whatever else, let's try to understand what phenomenon a mathematician or scientist is trying to (or could be trying to) model with AEP. Well
Asymptotic for very large $n$, a lot of coin flips, after a long time, etc ...
Equipartition Equally distributed amongst some boxes or bins, Uniformly random, Equilibrium ...
2
excellent 50p survey by leading expert/member Luca Trevisan from 2004 also tracking recent/latest research in the field
Some Applications of Coding Theory in Computational
Complexity
sections:
Introduction
Error-Correcting codes
Sublinear Time Unique Decoding
Sublinear Time List Decoding
Locally Testable Codes
2
My favorites for the first part of your question:
Neal Koblitz: "A Course in Number Theory and Cryptography"
$\rightarrow$ Very good introduction for mathematical treatment
Oded Goldreich: "The Foundations of Cryptography"
$\rightarrow$ More applications, but also a good book for basical interests
Thomas M. Cover and Joy A. Thomas: "Elements of ...
1
I define a random variable X which samples a bit uniformly at random from C∗. Should I expect Prob[X = 0] to be close to 1/2?
Roughly, yes. The compression algorithm is lossless (bijective), so the entropy of the input is the same as the entropy of the output. Under your hypothetical, the output's length is asymptotically larger than its entropy, so ...
1
It's possible to do a Gödel numbering that assigns every term in System F to a unique natural number?
The answer is yes, pick your favorite way of coding terms in F, simply because they are countable number of expressions.
Just being able to assign numbers to expressions in a system is not useful by itself, the question is can it be done in a manner that ...
1
The answer by Peter Shor is correct. But for an optimal case when the symbols can only be placed at unique leaf nodes the number of possible Huffman codes drops to $C_{n-1}2^{n-1}$.
Only top voted, non community-wiki answers of a minimum length are eligible