Notes for Miscellaneous Lectures
Leonid A. Levin
(https://www.cs.bu.edu/fac/lnd/)
Boston University∗
arXiv:cs/0503039v25 [cs.DM] 16 Jun 2025
Abstract
Here I share a few notes I used in various course lectures, talks, etc. Some may be
just calculations that in the textbooks are more complicated, scattered, or less specific;
others may be simple observations I found useful or curious.
Contents
1 Nemirovski Estimate of Common Mean of Distributions 2
2 Leftover Hash Lemma 3
3 Disputed Ballots and Poll Instabilities 4
4 A Magic Trick 5
Copyright ○
c 2025 by the author. Last revised: June 17, 2025.
∗
College of Arts and Sciences, Computer Science department, Boston, MA 02215, USA
1
2 Notes for Miscellaneous Lectures Leonid A. Levin
1 Nemirovski Estimate of Common Mean of
Arbitrary Distributions with Bounded Variance
The popular Chernoff bounds1 assume severe restrictions on distribution: it must be cut-off, or
vanish exponentially, etc. In [Nemirovsky Yudin]2 an equally simple bound uses no conditions
at all beyond independence and known bound on variance. It is not widely used because it is
not explained anywhere with an explicit tight computation. I offer this version:
Assume independent variables Xi (\omega ) with the same unknown mean m and known lower
bounds Bi2 on inverses iv(Xi ) = \mathrm{d}\mathrm{f}
1/var(Xi ) of their variance. We estimate m as M (\omega ) with
probability p\pm = P (\pm (M - m)\geq \varepsilon ) < 2 - k for k close to i (Bi \varepsilon )2 /12. We scale Xi to set \varepsilon =1.
\mathrm{d}\mathrm{f}
\sum
Additivity. Variance of sum of pairwise independent variables is additive.
So, it grows linearly,\sum not quadratically, \sum with the number of variables.
Weighted mean X= i wi Xi / i wi shrinks the variance. The maximal \sum shrink is
with weights wi = iv(Xi ). In this case it is iv that is additive: iv(X) = i iv(Xi ).
First, we spread Xi into n groups, and take in each group j its iv(Xi )-weighted mean
xj (\omega ). Using additivity of iv we grow groups to get b2j = \mathrm{d}\mathrm{f}
iv(xj ) \geq 6, to increase the sum k
- 1 2
of heights hj = log2 ((bj +bj )/2). (b = 6 scales precision/\sigma = \varepsilon b to \approx 2.45, makes h > 1/2,
\mathrm{d}\mathrm{f}
nearly maximizing h/b2 . These values can be taken below instead of b2j , hj , for simplicity.)
2
\prod
For s \subset [1, n], let bs = \mathrm{d}\mathrm{f}
j\in s bj . Let L be the set of light s: with bs < b[1,n] .
Let Lt consist of s whose largest superset s\prime in L has \| s\| +t elements. \bigr) As s \in L\sqrt{}
t make an
anti-chain (do not include each other), by Sperner theorem, \| Lt \| \leq \lceil nn/2\rceil < 2n+1 / \pi (2n+1).
\bigl(
Our M is the (log bj )-weighted median of xj . Then \pm (M (\omega ) - m) \geq 1 means
S \pm (\omega ) =
\mathrm{d}\mathrm{f}
\{ j : \pm (xj - m) < 1\} \in L. By Cantelli's inequality, p\pm j = P (j \not \in S ) \leq 1/(bj +1).
\mathrm{d}\mathrm{f} \pm 2
As bj are just bounds we can assume p\pm 2
j = 1/(bj +1). If s \in Lt , S (\omega ) = s has probability
\pm
\prod b2s\prime b[1,n] \prod 2 \prod
p\pm
s = b2s / (b2j +1) < t 2 / (bj +1) < 6 - t bj /(b2j +1) = 6 - t 2 - (k+n) .
j\leq n
6 bs\prime j\leq n j\leq n
\sum \sum \sum \sqrt{} \surd
So, p\pm \leq p\pm
s \leq ( 6 - t )2 - (k+n) 2n+1 / \pi (2n+1) < 2 - k / n.
t\geq 0 s\in Lt t\geq 0
1
First studied by S.N. Bernstein: Theory of Probability., Moscow, 1927. Tightened by Wassily Hoeffding
in: Probability inequalities for sums of bounded random variables, J.Am.Stat.Assoc. 58(301):13-30, 1963.
2
A.S.Nemirovsky, D.B.Yudin. Problem Complexity and Method Efficiency in Optimization. Wiley, 1983.
Leonid A. Levin Notes for Miscellaneous Lectures 3
2 Leftover Hash Lemma
The following Lemma is often useful to convert a stream of symbols with absolutely unknown
(except for a lower bound on its entropy) distribution into a source of perfectly uniform
independent random bits b \in Z2 = \{ 0, 1\} .
The version I give is close to that in [HILL]3 , though some aspects are closer to that
from [GL]4 . Unlike [GL], I do not restrict hash functions to be linear and do not guarantee
polynomial reductions, i.e. I forfeit the case when the unpredictability of the source has
computational, rather than truly random, nature. However, like [GL], I restrict hash functions
only in probability of collisions, not requiring pairwise uniform distribution.
Let G be a probability distribution on Z2n with Renyi entropy - log x G2 (x) \geq m.
\sum
Let fh (x)\in Z2k , h\in Z2t , x\in Z2n be a hash function family in the sense that for each x, y\not =x
the fraction of h with fh (x)=fh (y) is \leq 2 - k + 2 - m . Let U t be the uniform probability
- t - 1
distribution on Z2t and s = m - k - 1. Consider a distribution \sum P (h, a) = 2 G(fh (a))
t
generated by identity and f from U \otimes G. Let L1 (P, Q) = z | P (z) - Q(z)| be the L1
i
distance between distributions P and Q = U , i = t + k. It never exceeds their L2 distance
\sqrt{}
\sum
L2 (P, Q) = 2i (P (z) - Q(z))2 .
z
Lemma 1 (Leftover Hash Lemma). L1 (P, U i ) \leq L2 (P, U i ) < 2 - s/2 .
Note that h must be uniformly distributed but can be reused for many different x.
These x need to be independent only of h, not of each other as long as they
have \geq m entropy in the distribution conditional on all their predecessors.
Proof.
\sum \sum \sum
(L2 (P, U ))2 = 2i P (h, a)2 + 2i (2 - 2i - 2P (z)2 - i ) = 2i P (h, a)2 - 1
h,a z h,a
\sum \sum
= - 1 + 2i G(x)G(y)2 - 2t \| \{ h : fh (x) = fh (y) = a\} \|
x,y a
\sum
= - 1 + 2k - t G(x)G(y)\| \{ h : fh (x)=fh (y)\} \|
x,y
\Biggl( \Biggr)
\sum \sum
= - 1 + 2k - t G(x)2 2t + G(x)G(y)\| \{ h : fh (x)=fh (y)\} \|
x x,y\not =x
k - m - m
\leq - 1 + 2 2 +2 k - t
(1 - 2 )2t (2 - k + 2 - m ) < 2 - s .
3
Johan Hastad, Russell Impagliazzo, Leonid A. Levin, Michael Luby.
A Pseudorandom Generator from any One-way Function. Section 4.5. SICOMP 28(4):1364-1396, 1999.
4
Oded Goldreich, Leonid A. Levin. A Hard-core Predicate for any One-way Function. Sec.5. STOC 1989.
4 Notes for Miscellaneous Lectures Leonid A. Levin
3 Disputed Ballots and Poll Instabilities
Here is another curious example of advantages of quadratic norms.
The ever-vigilant struggle of major parties for the heart of the median voter makes many
elections quite tight. Add the Electoral College system of the US Presidential elections and
the history may hang on a small number of ballots in one state. The problem is not in the
randomness of the outcome. In fact, chance brings a sort of fair power sharing unplagued
with indecision: either party wins sometimes, but the country always has only one leader. If
a close race must be settled by dice, so be it. But the dice must be trusty and immune to
manipulation!
Alas, this is not what our systems assure. Of course, old democratic traditions help
avoiding outrages endangering younger democracies, such as Ukraine. Yet, we do not want
parties to compete on tricks that may decide the elections: appointing partisan election
officials or judges, easing voter access in sympathetic districts, etc. Better to make the
randomness of the outcome explicit, giving each candidate a chance depending on his/her
share of the vote. It is easy to implement the lottery in an infallible way, the issue is how its
chance should depend on the share of votes.
In contrast to the present one, the system should avoid any big jump from a small change
in the number of votes. Yet, chance should not be proportional to the share of votes. Otherwise
each voter may vote for himself, rendering election of a random person. The present system
encourages voters to consolidate around candidates acceptable to many others. The `jumpless'
system should preserve this feature. This can be done by using a non-linear function: say
the chance in the post-poll lottery be proportional to the squared number of votes. In other
words, a voter has one vote per each person he agrees with.5 Consider for instance an 8-way
race where the percents of votes are 60, 25, 10, 1, 1, 1, 1, 1. The leader's chance will be 5/6,
his main rival's 1/7, the third party candidate's 1/43 and the combined chance of the five
`protest' runners 1/866.
This system would force major parties to determine the most popular candidate via
some sort of primaries, and will almost exclude marginal runners. However it would have
no discontinuity rendering any small change in the vote distribution irrelevant. The system
would preserve an element of chance, but would be resistant to manipulation.
5
The dependence of lottery odds on the share of votes may be sharper.
Yet, it must be smooth to minimize the effects of manipulation. Even (trusty) noise alone,
e.g., discarding a randomly chosen half of the votes, can ``smooth"" the system a little.
Leonid A. Levin Notes for Miscellaneous Lectures 5
4 A Magic Trick
A book ``Mathematics for Computer Science""6 by Eric Lehman, F Thomson Leighton, and
Albert R Meyer has a very nice magic trick with cards. I used in my class some variation of
it described below (with book authors permission).
The trick is performed by a Wizard (W) and his assistant (A) for the viewers (V).
In W's absence, V choose and give A four cards out of 52 deck. A places them in a row
with one of them (H) hidden (turned back up) and exits. W then enters and guesses H.
However, placing H in the middle of the 3 open cards hints that the cards order is
informative, spoiling the surprise. I would instead place the chosen cards so that, 3 contiguous
cards are open and 1 hidden, or all are hidden (sometimes stellar patterns are so favorable to
magic that wizards need no information at all ! :-).
First, some terms: Senior (S), Junior (J), Middle (M) below refer to the order of ranks
or rank-suit pairs. Kings (K) are special7 : If chosen cards include King of spades (K0), all
cards are hidden; K1 always is J, K2 is M, K3 is S. A 4-set is a set of 4 cards with no K0.
A string is an ordered 4-set with the first or last card replaced by a symbol H (hidden).
G is a bipartite graph of 4-sets connected to four strings obtained by hiding one card and
ordering the rest to reflect the rank of H. A hidden K is treated as a duplicate of the respective
(J, M, or S) non-K open card. The Wizard only needs to figure the suit of H.
G breaks into small connected components distinguished by their sets R of non-K ranks
of the 4 chosen cards and ranks' multiplicity (including K as duplicates). With a uniform
degree 4, G has a perfect matching, described below, for A,W to use.
In a 4-set, let \alpha be the \BbbZ 4 sum of all suits in single-suit ranks. Multiple suits in a rank are
viewed in a circle (\BbbZ 7 if | R| =1, else \BbbZ 5 ) including respective Kings (but not K2 for | R| =2).
Let \beta (and \beta \prime if 2 such ranks) be 0 if the suits are consecutive, else 1. Notations like j, j \prime mean
same rank suits, j \prime \equiv j+1+\beta (mod 5). Let \gamma be 2 if | R| =2 with K2 present, else \gamma =0. Below
is a simple matching, blind to \BbbZ 5 , \BbbZ 7 rotations. (I omit cases with just j, m, s permuted):
| R| =1 H is the suit in a row (in \BbbZ 7 ) adjacent to 1-suit-shorter gap (left is preferred).
| R| =2 suits j, j \prime , s, s\prime : H=j if \beta =\beta \prime , else H=s.
| R| =2 suits j, c=K2, s, s\prime or j, s, c=s\prime , s\prime \prime : H=j if \alpha =\beta +\gamma ; H=c if \alpha +\beta =1; else H=s.
| R| =3 suits j, j \prime , m, s: H=s if x=(\alpha +\beta mod 4) is 0; H=m if x=1; else H=j.
| R| =4 The seniority of H reflects \alpha .
6
Problem 15.48 in a preprint: https://courses.csail.mit.edu/6.042/fall17/mcs.pdf
7
In Russia, the special one would be Queen, not King: Queen of Spades is attributed a special malice. :-)
