[Boneh-crypto-course] Random variables

[Jason Orendorff]

Feel free to ignore all this.

Random variables have always given me trouble. They figure fairly
prominently in Introduction to Algorithms (2nd ed, anyway), but I
never really got it. I get it now.

--- Random variables are not probability distributions

I used to think of random variables as just probability distributions.
So X <-R-- {0,1} would just mean X = {0: .5, 1: .5}, to use Python
notation. But this view falls apart as soon as it matters that two
expressions are interdependent. For example, consider two possible
definitions for Y:

    Y <-R-- {0,1}
    Y = X

In both cases, the probability distribution of Y is {0: 1/2, 1: 1/2},
but that cannot be the whole story, because in the first case X+Y
should be {0: 1/4, 1: 1/2, 2: 1/4} but in the second case X+Y should
be {0: 1/2, 2: 1/2}.

This is why there is a U in the definition of a random variable.
Independent random variables are orthogonal projections of U, whereas
interdependent random variables consult the same bits of U.

--- Pr is a macro

The notation Pr[X=1] leaves some stuff implicit. Here's my attempt to
explain to myself what's going on here.

Remember that a random variable is just a function mapping the set of
all possible worlds U to some set of values, call it V.

You can think of computing Pr[X=1] as a three-step process:

    1. Given an expression, like [X=1], find the set of values in V
that satisfy the expression:
        S1 = {x ∈ V | x=1}.
    2. Given that set, find all possible worlds in which X maps to one
of those values:
        S2 = {u ∈ U | X(u) = v, v ∈ S1}.
    3. Given that set of possible worlds, compute their total probability:
        Pr = sum(P(u) | u ∈ S2}.

The first step is just S1 = filter(λ v . v = 1, V); a filter of course
involves a predicate.

The reason I say Pr is a macro is that it implicitly creates this
predicate; like most interesting macros, it silently introduces a
lambda. So here is what I think Pr[expr] actually expands to:

  (defmacro Pr [U-probability-distribution X expr]
    `(let [predicate# (fn [~X] ~expr)]
       (apply + (for [[u# P-of-u#] ~U-probability-distribution
                      :when (predicate# (~X u#))]
                  P-of-u#))))

(The language is Clojure; "for" is their badass built-in list
comprehension macro:
<http://clojuredocs.org/clojure_core/clojure.core/for> and the # signs
are some auto-gensym stuff that quasiquoting magically does.)

Note that if you want a hygienic macro you must specify
U-probability-distribution and X at each use. In normal usage they
pretty much go without saying. But still.

Later Boneh introduces a notation
  Pr{K <-R-- 𝒦}[expr]
which apparently means “hey, for the purpose of this expression, the
universe U is just 𝒦, and the probability distribution is uniform”;
you can combine this with other Pr-expressions that contemplate
different universes U and it's sensible because the random variable K
being defined here is by definition independent of everything else.

  (defmacro Pr-uniform [v set expr]
    `(/ (count (filter (fn [~v] ~expr) ~set))
        (count ~set)))

-j