Probability and Information · Study tools

InteractiveApplebaum, Ch. 2: Combinatorics

Counting selections

Before probabilities come counts. Choosing $r$ things from $n$ can be done in four ways, depending on whether order matters and whether repeats are allowed. Each gives a different formula, and the formulas are related by simple overcounting factors that you can see by listing every selection.

The idea

Multiplication principle. If a task is done in

k

stages and stage

i

can be done in

m_i

ways whatever happened before, the whole task can be done in

m_1 m_2\cdots m_k

ways.

Applied to choosing $r$ objects from $n$ distinct ones:

\underbrace{n^r}_{\text{ordered, repeats}} \qquad \underbrace{\frac{n!}{(n-r)!}}_{\text{ordered, no repeats}} \qquad \underbrace{\binom{n}{r}=\frac{n!}{r!\,(n-r)!}}_{\text{unordered, no repeats}} \qquad \underbrace{\binom{n+r-1}{r}}_{\text{unordered, repeats}}

The third comes from the second: every unordered selection of $r$ different objects can be put in order in $r!$ ways, so the ordered count is $r!$ times too big. The fourth is "stars and bars": a selection with repeats is a row of $r$ stars split into $n$ groups by $n-1$ bars, and we choose which $r$ of the $n+r-1$ positions are stars.

Multinomial coefficient. The number of ways to split

N

distinct objects into labelled groups of sizes

n_1,\dots,n_k

(with

n_1+\dots+n_k=N

) is

\displaystyle\binom{N}{n_1,\dots,n_k}=\frac{N!}{n_1!\cdots n_k!}

. The binomial coefficient is the case

k=2

.

Gamma function.

\Gamma(x)=\int_0^\infty t^{x-1}e^{-t}\,dt

for

x>0

. Integration by parts gives

\Gamma(x+1)=x\,\Gamma(x)

, and

\Gamma(1)=1

, so

\Gamma(n+1)=n!

: the gamma function extends the factorial to non-integers. A special value worth knowing is

\Gamma(\tfrac12)=\sqrt\pi

.

Explore

Kind of selection

Objects n 5 Chosen r 3

Every selection, listed. Selections that use the same set of objects share a colour.

Worked example

A committee of 4 is chosen from 6 mathematicians and 5 physicists.

How many committees are possible with no restriction?

Order doesn't matter and nobody is chosen twice: $\binom{11}{4}=\dfrac{11\cdot10\cdot9\cdot8}{4!}=330$ .
How many have exactly two of each subject?

Choose the mathematicians, then the physicists, and multiply: $\binom62\binom52=15\cdot10=150$ .
How many contain at least one physicist?

Count the complement. The committees with no physicist are the $\binom64=15$ all-mathematician ones, so the answer is $330-15=315$ . (Adding up the cases "exactly 1, 2, 3, 4 physicists" gives $100+150+60+5=315$ too.)
Now the committee also needs a chair and a secretary, two different members. How many ways are there to form the committee and fill both posts?

Two ways to count, which must agree. Pick the committee (330 ways), then the chair (4) and the secretary (3): $330\cdot12=3960$ . Or pick the chair (11), the secretary (10), then the other two members from the remaining nine: $11\cdot10\cdot\binom92=110\cdot36=3960$ .

Check your understanding

In how many ways can 3 identical balls be placed in 4 different boxes, if a box may hold any number of balls?

$4^3=64$ That counts the balls as distinguishable: it records which ball went where. Here only how many balls each box gets matters.
$\binom43=4$ That forbids two balls in the same box. Boxes may hold several balls.
$\binom63=20$
$4\cdot3\cdot2=24$ That is an ordered selection without repeats.

A placement is an unordered selection of 3 boxes with repeats allowed. Stars and bars: 3 stars and 3 bars in a row, so

\binom{4+3-1}{3}=\binom63=20

. Check it in the explorer with

n=4,\ r=3

, "unordered, repeats".

In the explorer, set $n=5,\ r=3$ and "ordered, no repeats". The 60 arrangements fall into colour blocks. What are the blocks?

6 blocks of 10The other way round. A block is one set of 3 objects; how many orders does such a set have?
10 blocks of 6
20 blocks of 3Three objects can be ordered in more than 3 ways.

Each of the

\binom53=10

three-element sets appears in all

3!=6

of its orders. So

60=10\cdot6

, which is exactly the identity

\frac{n!}{(n-r)!}=r!\binom nr

.

Given $\Gamma(x+1)=x\,\Gamma(x)$ and $\Gamma(\frac12)=\sqrt\pi$ , what is $\Gamma(\frac52)$ ?

$\frac32\sqrt\pi$ You used the recursion once. $\Gamma(\frac52)=\frac32\Gamma(\frac32)$ , and $\Gamma(\frac32)$ still has to be reduced.
$\frac34\sqrt\pi$
$\frac{15}{8}\sqrt\pi$ That is $\Gamma(\frac72)$ : one step too many.
It is undefined: $(\frac32)!$ makes no sense.The factorial is only defined for integers, but the gamma function is defined for every $x>0$ .

\Gamma(\frac52)=\frac32\cdot\Gamma(\frac32)=\frac32\cdot\frac12\cdot\Gamma(\frac12)=\frac34\sqrt\pi\approx1.329

.

Practice

Rearranging a wordMultinomial coefficients

How many different strings can be made by rearranging all the letters of BANANAS? In how many of them are the three A's next to each other?

Hint

Swapping two equal letters gives the same string. For the second part, glue AAA into a single block.

Solution

There are 7 letters: A three times, N twice, B and S once. The count is $\dfrac{7!}{3!\,2!\,1!\,1!}=\dfrac{5040}{12}=420$ . With AAA as one block there are 5 items, B, S, N, N and the block, so $\dfrac{5!}{2!}=60$ strings.

A sum of squaresCounting one thing two ways

Show that $\displaystyle\sum_{k=0}^{n}\binom nk^2=\binom{2n}{n}$ by counting something in two ways.

Hint

A group has $n$ women and $n$ men. Count the ways to choose $n$ people from it, sorted by how many women are chosen. Use $\binom nk=\binom n{n-k}$ .

Solution

Choosing $n$ of the $2n$ people can be done in $\binom{2n}n$ ways. Alternatively, choose $k$ women and $n-k$ men, in $\binom nk\binom n{n-k}=\binom nk^2$ ways, and add over $k=0,\dots,n$ . Both count the same selections.

More practice: Applebaum, Exercises 2.7, 2.11 and 2.16.

InteractiveApplebaum, Ch. 3: Sets and measures

Sets and measures

A probability is a special kind of measure: a rule that gives each set a size, so that the sizes of non-overlapping pieces add up. Everything else, from the complement rule to inclusion–exclusion, follows from that one property. Below, the measure of a region is its share of the rectangle's area.

The idea

Boolean algebra. A collection

\mathcal B

of subsets of a set

S

that contains

S

and is closed under finite unions, intersections and complements. Its laws include the distributive laws and de Morgan's laws,

\overline{A\cup B}=\bar A\cap\bar B

and

\overline{A\cap B}=\bar A\cup\bar B

.

Measure. A function

m:\mathcal B\to[0,\infty)

that is additive on disjoint sets: if

A\cap B=\varnothing

then

m(A\cup B)=m(A)+m(B)

. Its total mass is

m(S)

; a measure with total mass 1 is a probability measure.

Examples: the counting measure $\#A$ on a finite set, length on unions of intervals, area in the plane. From additivity alone:

$m(\varnothing)=0$ , and $A\subseteq B$ implies $m(A)\le m(B)$ .
$m(A\smallsetminus B)=m(A)-m(A\cap B)$ , since $A$ is the disjoint union of $A\smallsetminus B$ and $A\cap B$ .
If $E_1,\dots,E_n$ partition $S$ , then $m(A)=\sum_i m(A\cap E_i)$ .

Inclusion–exclusion.

m(A\cup B)=m(A)+m(B)-m(A\cap B)

, and for three sets

m(A\cup B\cup C)=m(A)+m(B)+m(C)-m(A\cap B)-m(A\cap C)-m(B\cap C)+m(A\cap B\cap C).

Explore

Drag the discs. The shaded region is the chosen event; its measure is its area as a fraction of the rectangle

S

.

Event

Worked example

Use the counting measure on $S=\{1,2,\dots,30\}$ . Let $A$ , $B$ , $C$ be the multiples of 2, 3 and 5 in $S$ .

Find $\#A$ , $\#B$ , $\#C$ .

$\#A=15$ , $\#B=10$ , $\#C=6$ .
Find the sizes of all the intersections.

A number is in $A\cap B$ exactly when it is a multiple of 6, so $\#(A\cap B)=5$ . Similarly $\#(A\cap C)=3$ (multiples of 10), $\#(B\cap C)=2$ (multiples of 15) and $\#(A\cap B\cap C)=1$ (just 30).
How many numbers in $S$ are divisible by at least one of 2, 3, 5?

By inclusion–exclusion, $15+10+6-5-3-2+1=22$ . Check: the numbers coprime to 30 are 1, 7, 11, 13, 17, 19, 23, 29, which is 8 numbers, and $30-8=22$ .
How many are divisible by exactly one of them?

In the sum $\#A+\#B+\#C=31$ , a number in exactly two sets is counted twice and the number in all three is counted three times. In the pairwise sum $5+3+2=10$ , a number in exactly two sets is counted once and the triple point three times. So

$\#(\text{exactly one}) = 31 - 2\cdot10 + 3\cdot1 = 14.$

Check directly: 15 multiples of 2, minus those also divisible by 3 or 5 ( $5+3-1=7$ ) leaves 8; for 3 it is $10-(5+2-1)=4$ ; for 5 it is $6-(3+2-1)=2$ . Total $8+4+2=14$ .

Check your understanding

$P$ is a probability measure with $P(A)=0.5$ and $P(B)=0.4$ . Which values can $P(A\cup B)$ take?

Only $0.9$ That assumes $A$ and $B$ don't overlap. Drag the discs on top of each other and watch $m(A\cup B)$ .
Any value in $[0,0.9]$ $A\subseteq A\cup B$ , so monotonicity forces $P(A\cup B)\ge P(A)$ .
Any value in $[0.5,0.9]$
Any value in $[0.5,1]$ Inclusion–exclusion gives $P(A\cup B)=0.9-P(A\cap B)\le0.9$ .

P(A\cup B)=0.9-P(A\cap B)

, and

P(A\cap B)

can be anything from 0 (disjoint) up to

0.4

(when

B\subseteq A

). So

P(A\cup B)

ranges over

[0.5,0.9]

.

Which condition guarantees $m(A\smallsetminus B)=m(A)-m(B)$ ?

None; it always holds.Drag $B$ so that it sticks out of $A$ , and compare $m(A\smallsetminus B)$ with $m(A)-m(B)$ .
$B\subseteq A$
$A$ and $B$ are disjoint.Then $A\smallsetminus B=A$ , so $m(A\smallsetminus B)=m(A)$ , not $m(A)-m(B)$ (unless $m(B)=0$ ).

In general

m(A\smallsetminus B)=m(A)-m(A\cap B)

. If

B\subseteq A

then

A\cap B=B

, giving

m(A)-m(B)

.

On the subsets of a finite set, define $m(A)=(\#A)^2$ . Is $m$ a measure?

Yes: it is never negative.Non-negativity is only half of the definition. Check additivity on two disjoint one-point sets.
Yes: it is built from the counting measure, which is a measure.A function of a measure need not be a measure. Test it on disjoint sets.
No: additivity fails.

For disjoint one-point sets

\{a\}

,

\{b\}

:

m(\{a,b\})=4

but

m(\{a\})+m(\{b\})=2

. Any

c\cdot\#A

with

c\ge0

is a measure; squaring breaks additivity.

Practice

Proving inclusion–exclusionFrom additivity alone

Using only additivity on disjoint sets, prove $m(A\cup B)+m(A\cap B)=m(A)+m(B)$ for any $A,B\in\mathcal B$ .

Hint

Split $A\cup B$ into three disjoint pieces: $A\smallsetminus B$ , $A\cap B$ , $B\smallsetminus A$ .

Solution

Write $a=m(A\smallsetminus B)$ , $c=m(A\cap B)$ , $b=m(B\smallsetminus A)$ . Additivity gives $m(A\cup B)=a+b+c$ , $m(A)=a+c$ and $m(B)=b+c$ . So both sides equal $a+b+2c$ .

A lower bound for an intersectionBonferroni's inequality

Show that $P(A\cap B)\ge P(A)+P(B)-1$ for any probability measure. A part goes through two checks, which it passes with probabilities $0.97$ and $0.95$ . Nothing is known about how the checks are related. What can you say about the probability that it passes both?

Solution

From inclusion–exclusion, $P(A\cap B)=P(A)+P(B)-P(A\cup B)\ge P(A)+P(B)-1$ , since $P(A\cup B)\le1$ . For the checks, $P(\text{both})\ge0.97+0.95-1=0.92$ . The bound holds whatever the dependence between the checks, and it is attained when the two sets of failures are disjoint. If the checks were independent, the answer would be exactly $0.97\cdot0.95=0.9215$ .

More practice: Applebaum, Exercises 3.6, 3.10 and 3.16.

InteractiveApplebaum, Ch. 4: Probability

Conditional probability and Bayes' theorem

A test that is right 99% of the time can still be wrong most of the time it says "positive". The resolution is the difference between $P(\text{positive}\mid\text{ill})$ and $P(\text{ill}\mid\text{positive})$ , and Bayes' theorem is the rule for turning one into the other.

The idea

Conditional probability. If

P(A)>0

, the probability of

B

given

A

is

P(B\mid A)=\dfrac{P(A\cap B)}{P(A)}

. (The book writes

P_A(B)

.) For fixed

A

,

B\mapsto P(B\mid A)

is itself a probability measure.

Total probability and Bayes. If

E_1,\dots,E_n

partition

S

and each

P(E_i)>0

, then

P(A)=\sum_{i}P(A\mid E_i)\,P(E_i), \qquad P(E_k\mid A)=\frac{P(A\mid E_k)\,P(E_k)}{\sum_i P(A\mid E_i)\,P(E_i)}.

Independence.

A

and

B

are independent if

P(A\cap B)=P(A)P(B)

, that is, learning

A

does not change the probability of

B

. Three events are independent if each pair is and also

P(A\cap B\cap C)=P(A)P(B)P(C)

; pairwise independence alone is not enough.

For a diagnostic test, $E_1=D$ (ill) and $E_2=\bar D$ . The sensitivity is $P(+\mid D)$ , the specificity is $P(-\mid\bar D)$ , and the prevalence $P(D)$ is the prior. Bayes gives the posterior $P(D\mid +)$ .

Explore

Prevalence P(D) Sensitivity P(+ | D) Specificity P(− | not D)

ill, tests positive ill, tests negative healthy, tests positive healthy, tests negative · expected numbers in 1000 people, rounded

Worked example

30% of the email reaching an inbox is spam. A filter flags 95% of spam, and also flags 2% of genuine email.

What fraction of all email gets flagged?

By total probability, $P(F)=0.95\cdot0.3+0.02\cdot0.7=0.285+0.014=0.299$ .
A message is flagged. What is the probability it is spam?

$P(\text{spam}\mid F)=\frac{0.285}{0.299}\approx0.953.$

About 1 flagged message in 21 is genuine.
A message is not flagged. What is the probability it is spam?

$P(\text{spam}\mid\bar F)=\frac{0.05\cdot0.3}{1-0.299}=\frac{0.015}{0.701}\approx0.021.$
Are "spam" and "flagged" independent? What would independence mean for the filter?

No: $P(\text{spam}\mid F)\approx0.953\ne0.3=P(\text{spam})$ . Independence would mean that a flag carries no information about whether the message is spam, which happens exactly when the filter flags spam and genuine mail at the same rate. Try that in the explorer: set sensitivity $=1-$ specificity and the posterior equals the prior.

Check your understanding

A test has sensitivity and specificity both 0.99, and 1 person in 1000 has the disease. Roughly what is $P(D\mid +)$ ?

0.99That is $P(+\mid D)$ . The question asks for the reverse conditional probability.
0.5Count the positives in 1000 people: about 1 true positive and about 10 false ones.
About 0.09
0.001That is the prior. A positive result should raise it.

P(D\mid+)=\dfrac{0.99\cdot0.001}{0.99\cdot0.001+0.01\cdot0.999}=\dfrac{0.00099}{0.01098}\approx0.090

. The false positives come from the 999 healthy people, so they outnumber the true positives about ten to one.

$A$ and $B$ are disjoint events, each with positive probability. Can they be independent?

Yes: they have nothing to do with each other.Disjoint does not mean unrelated: if $A$ happens, you know for certain that $B$ did not.
No
Only if $P(A)+P(B)=1$ .Check the definition: $P(A\cap B)$ would have to equal $P(A)P(B)$ .

P(A\cap B)=P(\varnothing)=0

, but

P(A)P(B)>0

. Disjoint events with positive probability are strongly dependent.

A patient tests positive, then takes a second test of the same kind, whose result given the disease status is independent of the first, and is positive again. How should the probability be updated?

Use the posterior after the first test as the prior and apply Bayes again.
Multiply the first posterior by the sensitivity.That gives $P(D\cap+_2\mid+_1)$ , not $P(D\mid+_1,+_2)$ . You still have to divide by the probability of the second positive.
The second test adds nothing new.It is independent given the disease status, so it is fresh evidence. Use the retest button in the explorer.

Because the tests are conditionally independent given

D

,

P(D\mid+_1,+_2)

is Bayes' formula with prior

P(D\mid+_1)

. In the 1-in-1000 example the posterior goes from about 0.09 to about 0.91.

Practice

Three cardsConditioning on what you see

One card is red on both sides, one is white on both sides, and one is red on one side and white on the other. A card is drawn at random and placed on the table with a random side up. The visible side is red. What is the probability that the other side is red too?

Hint

Condition on the face you see, not on the card. There are six equally likely faces.

Solution

Of the six equally likely faces, three are red. Two of those belong to the red–red card. So $P(\text{other side red}\mid\text{red seen})=2/3$ , not $1/2$ . With Bayes: $P(RR\mid\text{red})=\dfrac{1\cdot\frac13}{1\cdot\frac13+\frac12\cdot\frac13+0}=\frac23$ .

Pairwise is not enoughIndependence of three events

Toss two fair coins. Let $A$ = "first coin heads", $B$ = "second coin heads", $C$ = "the coins show the same face". Show that each pair of these events is independent, but the three are not.

Solution

Each event has probability $\frac12$ . $A\cap B=\{HH\}$ , $A\cap C=\{HH\}$ , $B\cap C=\{HH\}$ , each of probability $\frac14=\frac12\cdot\frac12$ . But $A\cap B\cap C=\{HH\}$ has probability $\frac14\ne\frac18$ . Knowing $A$ and $B$ together determines $C$ , even though each alone tells you nothing about it.

More practice: Applebaum, Exercises 4.14, 4.20 and 4.29.

SimulationApplebaum, Ch. 5: Discrete random variables

Discrete random variables

A random variable's law says how likely each value is; its mean and variance summarise where the values sit and how far they spread. Draw samples below and watch the histogram settle onto the law and the running average settle onto the mean.

The idea

Random variable. A function

X

from the sample space to

\R

. For discrete

X

, its law is

p(x)=P(X=x)

and its cumulative distribution is

F(x)=P(X\le x)

.

Mean and variance.

E(X)=\sum_x x\,p(x)

and

\mathrm{Var}(X)=E\big((X-\mu)^2\big)=E(X^2)-E(X)^2

. Expectation is linear,

\mathrm{Var}(aX+b)=a^2\mathrm{Var}(X)

, and for independent

X,Y

,

\mathrm{Var}(X+Y)=\mathrm{Var}(X)+\mathrm{Var}(Y)

.

Three laws that come up again and again:

Binomial $b(n,p)$ : the number of successes in $n$ independent trials, $p(k)=\binom nk p^k(1-p)^{n-k}$ ; mean $np$ , variance $np(1-p)$ .
Poisson $\pi(\lambda)$ : $p(k)=e^{-\lambda}\lambda^k/k!$ for $k=0,1,2,\dots$ ; mean and variance both $\lambda$ . It is the limit of $b(n,\lambda/n)$ as $n\to\infty$ : many trials, each rarely a success.
Geometric: the number of the trial on which the first success happens, $p(r)=p(1-p)^{r-1}$ for $r=1,2,\dots$ ; mean $1/p$ , variance $(1-p)/p^2$ .

Averages settle down. If

X_1,X_2,\dots

are i.i.d. with mean

\mu

and variance

\sigma^2

, the sample mean

\bar X_n

has mean

\mu

and variance

\sigma^2/n

. So its typical distance from

\mu

shrinks like

1/\sqrt n

. (The law of large numbers itself is proved in Chapter 8.)

Explore

Law

Trials n Success probability p

the law

p(k)

relative frequency in your samples Poisson overlay

running mean

\bar X_n

E(X)

and the band

E(X)\pm\sigma/\sqrt n

Worked example

A batch contains 200 chips, each defective with probability 0.01 independently of the others. Let $X$ be the number of defective chips.

What is the law of $X$ ? Find $P(X=0)$ .

$X\sim b(200,0.01)$ , so $P(X=0)=0.99^{200}\approx0.1340$ .
Approximate the same probability with a Poisson law. Which $\lambda$ ?

Match the means: $\lambda=np=2$ . Then $P(X=0)\approx e^{-2}\approx0.1353$ , within about 1% of the exact value.
Estimate $P(X\ge3)$ both ways.

Use the complement. Exactly: $1-(0.1340+0.2707+0.2720)\approx0.3233$ . Poisson: $1-e^{-2}(1+2+2)=1-5e^{-2}\approx0.3233$ . They agree to four decimal places.
Compare the variances. Why is the Poisson variance a little larger?

The binomial variance is $np(1-p)=1.98$ ; the Poisson variance is $\lambda=2$ . The factor $1-p$ is the only difference, and it tends to 1 as $p\to0$ with $np$ fixed. That is the regime in which the Poisson approximation is good.

Check your understanding

$X\sim b(10,0.3)$ and $Y\sim b(10,0.3)$ are independent. What is the law of $X+Y$ ?

$b(20,0.3)$
$b(10,0.6)$ Adding the two counts adds the numbers of trials, not the success probabilities. $X+Y$ can be as large as 20.
It is not binomial.Think of $X$ and $Y$ as counting successes in two separate runs of independent trials.

X+Y

counts successes in 20 independent trials, each with success probability 0.3. Check: the mean is

3+3=6=20\cdot0.3

and the variance is

2.1+2.1=4.2=20\cdot0.3\cdot0.7

.

In the simulator, the running mean wanders around $E(X)$ . If you quadruple the number of draws, by what factor does its typical distance from $E(X)$ shrink?

4That would be true of the variance of $\bar X_n$ , not its standard deviation.
2
It doesn't shrink; each draw is as random as the last.Each draw is, but the average of many draws is much less variable.

\mathrm{Var}(\bar X_n)=\sigma^2/n

, so the standard deviation is

\sigma/\sqrt n

. Four times as many draws halves it. That is the band drawn around

E(X)

in the right-hand plot.

$X$ is uniform on $\{-1,0,1\}$ and $Y=X^2$ . Which is true?

They are independent, because they are uncorrelated.Uncorrelated only says $E(XY)=E(X)E(Y)$ . Compare $P(Y=0\mid X=0)$ with $P(Y=0)$ .
They are uncorrelated but not independent.
They are correlated, since $Y$ is a function of $X$ .Compute $\mathrm{Cov}(X,Y)=E(X^3)-E(X)E(X^2)$ .

E(XY)=E(X^3)=0=E(X)E(Y)

, so the covariance is 0. But

P(Y=0\mid X=0)=1\ne\frac13=P(Y=0)

. Correlation only detects linear dependence.

Practice

Mean of the geometric lawDifferentiating a series

Show that if $p(r)=p(1-p)^{r-1}$ for $r\ge1$ , then $E(X)=1/p$ .

Hint

Differentiate $\sum_{r\ge0}x^r=\frac1{1-x}$ for $|x|<1$ .

Solution

Differentiating gives $\sum_{r\ge1}r x^{r-1}=\frac1{(1-x)^2}$ . With $x=1-p$ , $E(X)=p\sum_{r\ge1}r(1-p)^{r-1}=p\cdot\frac1{p^2}=\frac1p$ . On average a fair die takes 6 rolls to show its first six.

Thinning a Poisson countTotal probability with random variables

The number of emails arriving in an hour is $N\sim\pi(\lambda)$ . Each email, independently, is spam with probability $s$ . Show that the number of spam emails $K$ is Poisson with mean $\lambda s$ .

Hint

Given $N=n$ , $K\sim b(n,s)$ . Sum over $n\ge k$ .

Solution

P(K=k)=\sum_{n\ge k}e^{-\lambda}\frac{\lambda^n}{n!}\binom nk s^k(1-s)^{n-k}=e^{-\lambda}\frac{(\lambda s)^k}{k!}\sum_{m\ge0}\frac{(\lambda(1-s))^m}{m!}=e^{-\lambda s}\frac{(\lambda s)^k}{k!},

where $m=n-k$ . So $K\sim\pi(\lambda s)$ .

More practice: Applebaum, Exercises 5.22, 5.23 and 5.36.

InteractiveApplebaum, Ch. 6: Information and entropy

Information and entropy

A rare event is more informative than a common one. Entropy is the average information in the outcome of a random variable: how many yes/no questions, on average, it takes to pin down the outcome. Drag the bars below and find the shapes with the most and the least entropy.

The idea

Information. The information in an event of probability

p

is

I=-\log p

bits. Two independent events carry the sum of their informations, because probabilities multiply and logarithms turn products into sums.

Entropy. For

X

with law

p_1,\dots,p_n

,

H(X)=E\big(I(X)\big)=-\sum_{j=1}^n p_j\log p_j, \qquad\text{with } 0\log 0=0.

It depends only on the probabilities, not on the values $X$ takes. For a Bernoulli variable, $H_b(p)=-p\log p-(1-p)\log(1-p)$ , which is 1 bit at $p=\frac12$ .

Bounds.

0\le H(X)\le\log n

. The lower bound holds exactly when one outcome is certain, the upper exactly when

X

is uniform.

Maximum entropy principle. Among all laws on values

x_1,\dots,x_n

with a given mean, the one of largest entropy is the Gibbs law

p_j=\frac{e^{-\beta x_j}}{Z(\beta)}, \qquad Z(\beta)=\sum_j e^{-\beta x_j},

with $\beta$ chosen to give the right mean. It is the "least committal" law consistent with what you know. In statistical mechanics the $x_j$ are energies and this is the Boltzmann distribution.

Explore

Drag the bars (outcomes

j=1,\dots,6

) up and down; the heights are rescaled to sum to 1. Above each bar is the information

-\log p_j

of that outcome, in bits. The dashed outline is the maximum-entropy law with the same mean as yours.

Worked example

Three fair coins are tossed. Let $X$ be the number of heads.

Write down the law of $X$ .

$P(X=0)=P(X=3)=\frac18$ and $P(X=1)=P(X=2)=\frac38$ .
How much information is there in learning $X=0$ ? In learning $X=1$ ?

$-\log\frac18=3$ bits, and $-\log\frac38=\log\frac83\approx1.415$ bits.
Compute $H(X)$ .

$H(X)=2\cdot\tfrac18\cdot3+2\cdot\tfrac38\cdot1.415\approx0.75+1.061=1.811\ \text{bits}.$
The full outcome (e.g. HTH) has 3 bits of entropy. Where did the other 1.19 bits go?

The full outcome is uniform on 8 sequences, so it has $\log8=3$ bits. $X$ is a function of it and forgets the order of the heads, which is why $H(X)<3$ . In general $H(f(Y))\le H(Y)$ : processing can only lose information. The missing $3-1.811=1.189$ bits is the average information in "which order", given the count.

Check your understanding

Which law on four outcomes has more entropy: $(0.5,0.5,0,0)$ or $(0.4,0.2,0.2,0.2)$ ?

The first, because it is uniform.It is uniform only on two of the four outcomes, which gives $\log2=1$ bit.
The second
They are equal.Compute both: one is exactly 1 bit.

H(0.5,0.5,0,0)=1

bit, while

H(0.4,0.2,0.2,0.2)=0.4\log2.5+0.6\log5\approx1.922

bits. Spreading probability over more outcomes matters more than being exactly uniform.

$X$ takes values $1,\dots,6$ . Let $Y=10X+7$ . How does $H(Y)$ compare with $H(X)$ ?

$H(Y)=H(X)$
$H(Y)=10\,H(X)$ That is how the variance would scale (by $10^2$ , in fact). Entropy only sees the probabilities.
$H(Y)>H(X)$ , since $Y$ is more spread out.Entropy does not measure spread of values; relabelling the outcomes changes nothing.

x\mapsto10x+7

is one-to-one, so

Y

has the same list of probabilities as

X

and the same entropy. Entropy measures uncertainty about which outcome occurs, not how far apart the outcomes are.

Among all laws on $\{1,\dots,6\}$ with mean 3.5, which has the largest entropy?

The uniform law
$p_3=p_4=\frac12$ It has mean 3.5 but only 1 bit of entropy. Try it in the explorer.
A Gibbs law with $\beta>0$ With $\beta>0$ the weights $e^{-\beta j}$ favour small values, so the mean is below 3.5.

The uniform law has the largest entropy of all,

\log6\approx2.585

bits, and its mean is 3.5. It is the Gibbs law with

\beta=0

. Press "Uniform", then "Replace with the max-entropy law": nothing changes.

Practice

The Bernoulli entropyA calculus check

Show that $H_b(p)$ has its maximum at $p=\frac12$ and is symmetric about it. Compute $H_b(0.1)$ .

Solution

$H_b(p)=H_b(1-p)$ by its formula. In natural logs, $\frac{d}{dp}\big(-p\ln p-(1-p)\ln(1-p)\big)=\ln\frac{1-p}{p}$ , which is positive for $p<\frac12$ , zero at $\frac12$ and negative after. So the maximum is $H_b(\frac12)=1$ bit. $H_b(0.1)=0.1\log10+0.9\log\frac{10}9\approx0.332+0.137=0.469$ bits.

Why uniform is the maximumThe Gibbs inequality

Using $\ln x\le x-1$ (equality only at $x=1$ ), show that $H(X)\le\log n$ , with equality only for the uniform law.

Hint

Look at $H(X)-\log n=\sum_j p_j\log\frac{1}{np_j}$ , summing over the $j$ with $p_j>0$ .

Solution

In natural logs, $\sum_j p_j\ln\frac1{np_j}\le\sum_j p_j\big(\frac1{np_j}-1\big)=\sum_{p_j>0}\frac1n-1\le0$ . Equality needs $np_j=1$ for every $j$ with $p_j>0$ , and needs every $j$ to have $p_j>0$ ; that is the uniform law. Dividing by $\ln2$ converts to bits.

More practice: Applebaum, Exercises 6.5, 6.6, 6.13 and 6.16.

InteractiveApplebaum, Ch. 6: Information and entropy (§6.3)

Joint entropy and mutual information

How much does knowing $X$ tell you about $Y$ ? Mutual information answers in bits: it is the drop in uncertainty about $Y$ once $X$ is known. Reshape a joint law by dragging the dividers of the mosaic below and watch the entropies add up.

The idea

Joint and conditional entropy. For a pair

(X,Y)

with joint law

p_{jk}=P(X=x_j,Y=y_k)

,

H(X,Y)=-\sum_{j,k}p_{jk}\log p_{jk}, \qquad H(Y\mid X)=\sum_j P(X=x_j)\,H(Y\mid X=x_j).

$H(Y\mid X=x_j)$ is the entropy of the conditional law of $Y$ given $X=x_j$ , and $H(Y\mid X)$ is its average over $x_j$ . (The book writes $H_X(Y)$ .)

Chain rule.

H(X,Y)=H(X)+H(Y\mid X)

: learning the pair is learning

X

, then learning

Y

given

X

.

Mutual information.

I(X;Y)=H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y)=\sum_{j,k}p_{jk}\log\frac{p_{jk}}{P(X=x_j)P(Y=y_k)}.

Properties.

I(X;Y)=I(Y;X)\ge0

, with equality exactly when

X

and

Y

are independent. Equivalently

H(Y\mid X)\le H(Y)

: on average, conditioning cannot increase uncertainty.

Explore

Start from:

Each rectangle's area is

p_{jk}

. Drag the vertical divider to set

P(X=0)

, and each horizontal divider to set

P(Y=0\mid X=x)

.

H(X\mid Y)

I(X;Y)

H(Y\mid X)

, in bits

Worked example

$X$ and $Y$ take values 0 and 1 with joint law $p_{00}=\frac12$ , $p_{01}=\frac14$ , $p_{10}=0$ , $p_{11}=\frac14$ .

Find the marginal laws and their entropies.

$P(X=0)=\frac34$ , $P(X=1)=\frac14$ , so $H(X)=H_b(\frac14)\approx0.811$ . $P(Y=0)=P(Y=1)=\frac12$ , so $H(Y)=1$ .
Find $H(X,Y)$ .

$H(X,Y)=\frac12\log2+\frac14\log4+\frac14\log4=0.5+0.5+0.5=1.5$ bits.
Compute $H(Y\mid X)$ from its definition, and check the chain rule.

Given $X=0$ , $Y$ is 0 or 1 with probabilities $\frac23,\frac13$ , so $H(Y\mid X=0)=H_b(\frac13)\approx0.918$ . Given $X=1$ , $Y=1$ for certain, so $H(Y\mid X=1)=0$ . Then $H(Y\mid X)=\frac34\cdot0.918\approx0.689$ , and indeed $H(X)+H(Y\mid X)\approx0.811+0.689=1.5$ .
Find $I(X;Y)$ two ways.

$H(Y)-H(Y\mid X)\approx1-0.689=0.311$ , and $H(X)+H(Y)-H(X,Y)\approx0.811+1-1.5=0.311$ bits. Set the mosaic to these numbers ( $P(X=0)=0.75$ , $P(Y=0\mid X=0)=\frac23$ , $P(Y=0\mid X=1)=0$ ) to check.

Check your understanding

$I(X;Y)=0$ . What can you conclude?

$X$ and $Y$ are independent.
$Y$ is a function of $X$ .Then $H(Y\mid X)=0$ and $I(X;Y)=H(Y)$ , the largest it can be.
One of them is constant.That is enough for $I=0$ but not necessary. In the mosaic, line the two horizontal dividers up.

I(X;Y)=\sum p_{jk}\log\frac{p_{jk}}{p_jq_k}

is zero exactly when

p_{jk}=p_jq_k

for every

j,k

. In the mosaic, that means the two horizontal dividers are at the same height: the conditional law of

Y

doesn't depend on

X

.

$X$ is a fair bit and $Y=X$ . What is $I(X;Y)$ ?

0 $Y$ tells you $X$ exactly. That is the opposite of independence.
1 bit
2 bitsThat is $H(X)+H(Y)$ . But $H(X,Y)=1$ , not 0, so subtract it.

H(Y\mid X)=0

, so

I=H(Y)=1

bit. A variable shares all of its information with itself:

I(X;X)=H(X)

.

Which of these always holds?

$H(Y\mid X)\le H(Y)$
$H(Y\mid X=x)\le H(Y)$ for every value $x$ Try "Y depends on X only sometimes": a rare value of $X$ after which $Y$ is a fair coin.
$H(X,Y)\ge H(X)+H(Y)$ The inequality goes the other way: $H(X,Y)=H(X)+H(Y)-I(X;Y)$ .

Only the average over

x

is guaranteed to drop. If

X=0

with probability 0.9 and then

Y=0

, but

X=1

makes

Y

a fair coin, then

H(Y)=H_b(0.05)\approx0.286

while

H(Y\mid X=1)=1

. Learning a particular, surprising value can make you less sure.

Practice

Two formulas for IExpanding the logarithm

Show that $\displaystyle\sum_{j,k}p_{jk}\log\frac{p_{jk}}{p_jq_k}=H(X)+H(Y)-H(X,Y)$ , where $p_j$ , $q_k$ are the marginals.

Solution

Split the logarithm: $\sum p_{jk}\log p_{jk}-\sum p_{jk}\log p_j-\sum p_{jk}\log q_k$ . The first sum is $-H(X,Y)$ . In the second, summing over $k$ first gives $\sum_j p_j\log p_j=-H(X)$ ; similarly the third is $-H(Y)$ . So the total is $-H(X,Y)+H(X)+H(Y)$ .

The last bitA function of a random variable

$X$ is uniform on $\{0,1,2,3\}$ and $Y=X\bmod2$ . Find $H(X)$ , $H(Y)$ , $H(Y\mid X)$ , $H(X\mid Y)$ and $I(X;Y)$ .

Solution

$H(X)=2$ , $H(Y)=1$ . $Y$ is determined by $X$ , so $H(Y\mid X)=0$ . Given $Y$ , $X$ is uniform on two values, so $H(X\mid Y)=1$ . Then $I(X;Y)=H(Y)-H(Y\mid X)=1$ bit, and the chain rule checks: $H(X,Y)=H(X)=2=H(Y)+H(X\mid Y)$ .

More practice: Applebaum, Exercises 6.8 and 6.10.

InteractiveApplebaum, Ch. 7: Communication (§§7.1–7.2, 7.5)

Channels and capacity

A noisy channel garbles some of what is sent. The mutual information between input and output measures how much gets through, and the sender can tune it by choosing how often to send each symbol. The best achievable value is the channel's capacity, and Shannon's theorem says it is a hard speed limit for reliable communication.

The idea

Channel. A source sends a symbol

X

; the receiver gets

Y

. The channel is described by the conditional probabilities

P(Y=y\mid X=x)

, which are fixed. The sender chooses the input law

P(X=x)

.

Capacity.

C=\max I(X;Y)

, the maximum over all input laws.

In the binary symmetric channel each bit is flipped with probability $\varepsilon$ , independently. If $P(X=1)=p$ , then $P(Y=1)=p(1-\varepsilon)+(1-p)\varepsilon$ , and $H(Y\mid X)=H_b(\varepsilon)$ whatever was sent, so

I(X;Y)=H_b\big(p(1-\varepsilon)+(1-p)\varepsilon\big)-H_b(\varepsilon), \qquad C=1-H_b(\varepsilon),

with the maximum at $p=\frac12$ , which makes $Y$ uniform.

Shannon's coding theorem. Send blocks of

n

bits through the channel, using

2^{nR}

of the possible blocks as codewords (a rate of

R

message bits per channel use). If

R<C

, then for large

n

there are codes whose probability of a decoding error is as small as you like. Above capacity this is impossible.

Explore

Flip probability ε Input law p = P(X = 1)

Right-hand plot

The channel. Line widths show the joint probabilities

P(X=x,Y=y)

.

Worked example

In a "Z-channel", a 0 is always received correctly, but a 1 arrives as 0 with probability $\frac12$ . Find its capacity and the input law that achieves it.

With $P(X=1)=p$ , find the law of $Y$ .

$Y=1$ only if a 1 was sent and survived: $P(Y=1)=\frac p2$ .
Find $H(Y\mid X)$ .

Given $X=0$ , $Y$ is certain: entropy 0. Given $X=1$ , $Y$ is a fair coin: entropy 1. So $H(Y\mid X)=(1-p)\cdot0+p\cdot1=p$ .
Write $I(X;Y)$ as a function of $p$ and maximise it.

$I(p)=H_b(\frac p2)-p$ . Using $\frac{d}{dq}H_b(q)=\log\frac{1-q}{q}$ ,

$I'(p)=\tfrac12\log\frac{1-p/2}{p/2}-1=0 \iff \frac{2-p}{p}=4 \iff p=\tfrac25.$
What is the capacity? What is surprising about the optimal input?

$C=H_b(0.2)-0.4\approx0.722-0.4=0.322$ bits, which equals $\log\frac54$ . The best input sends 1 only 40% of the time: since 1s are the unreliable symbol, it pays to use them less. For the symmetric channel the optimum is always $\frac12$ , but in general the capacity-achieving input need not be uniform.

Check your understanding

A binary symmetric channel has $\varepsilon=\frac12$ . What is its capacity?

0
$\frac12$ bit, since half the bits arrive correctlyThey do, but the receiver can't tell which half. Set ε to 0.5 and look at the output law.
1 bitThat is the capacity of a perfect channel.

With

\varepsilon=\frac12

,

Y

is a fair coin whatever was sent, so

Y

is independent of

X

and

I(X;Y)=0

for every input law. Indeed

1-H_b(\frac12)=0

.

A binary symmetric channel flips each bit with probability 0.9. How does its capacity compare with a channel that flips with probability 0.1?

It is the same.
It is nearly zero.The receiver can flip every bit back. That turns it into a channel with ε = 0.1.
It is lower than at ε = 0.5.The capacity is smallest at 0.5. Look at the capacity curve.

H_b(0.9)=H_b(0.1)

, so both have capacity

1-0.469=0.531

bits. A channel that is almost always wrong is almost as useful as one that is almost always right; only one that is unpredictable is useless.

Why is the capacity defined as a maximum over input laws?

The channel's noise is fixed, but the sender can choose how often to use each input symbol.
Because $I(X;Y)$ is the same for every input law, so the maximum is just that value.Move the p slider: $I(X;Y)$ changes with the input law.
To make the capacity independent of the noise.The capacity depends on the noise; for the symmetric channel it is $1-H_b(\varepsilon)$ .

I(X;Y)

depends on the channel and on the input law. Maximising over the part the sender controls leaves a number that describes the channel alone.

Practice

A ternary channelCapacity by symmetry

Inputs and outputs are $\{0,1,2\}$ . Each input $j$ arrives as $j$ or as $j+1\pmod3$ , with probability $\frac12$ each. Find the capacity.

Hint

$H(Y\mid X)$ does not depend on the input law. Which input law makes $H(Y)$ as large as possible?

Solution

$H(Y\mid X=j)=1$ for each $j$ , so $H(Y\mid X)=1$ . $H(Y)\le\log3$ , with equality when $Y$ is uniform, which happens when $X$ is uniform. So $C=\log3-1\approx0.585$ bits.

The repetition codeReliable, but slow

Over a binary symmetric channel with $\varepsilon=0.1$ , each message bit is sent three times and decoded by majority vote. Find the probability of a decoding error and the rate. How does this compare with what Shannon's theorem allows?

Solution

Decoding fails if at least two of the three copies are flipped: $3\varepsilon^2(1-\varepsilon)+\varepsilon^3=0.027+0.001=0.028$ . The rate is $\frac13$ bit per use. The capacity is $1-H_b(0.1)\approx0.531$ , so Shannon's theorem promises codes with rate up to about 0.53 and error probability as small as we like. Repetition buys reliability by giving up rate, and longer repetition makes the rate tend to 0; good codes avoid this.

More practice: Applebaum, Exercises 7.1, 7.2 and 7.5.

Animated lessonApplebaum, Ch. 7: Communication (§§7.3–7.4)

Prefix codes and Huffman coding

To compress a source, give common symbols short codewords and rare ones long codewords. Entropy is the floor: no code can beat $H$ bits per symbol on average. Huffman's algorithm builds the best possible prefix code by repeatedly merging the two least likely symbols. Watch it work.

The idea

Prefix-free code. A binary code in which no codeword is the beginning of another. Such a code can be decoded as the bits arrive, with no separators. Codewords correspond to leaves of a binary tree: 0 for left, 1 for right.

Kraft–McMillan inequality. A binary prefix-free code with codeword lengths

l_1,\dots,l_n

exists if and only if

\sum_j 2^{-l_j}\le1

. (McMillan: the inequality also holds for every uniquely decodable code.)

Noiseless coding theorem. For a source with law

p_1,\dots,p_n

, every uniquely decodable code has average length

E(L)=\sum_j p_jl_j\ge H

. There is a prefix-free code with

E(L)<H+1

: take

l_j=\lceil-\log p_j\rceil

(Shannon–Fano lengths).

Huffman's algorithm. Start with each symbol as a one-node tree with its probability. Repeatedly join the two trees of smallest probability under a new root, whose probability is their sum, until one tree remains. The resulting code has the smallest

E(L)

of all prefix-free codes.

$E(L)=H$ exactly when every $p_j$ is a power of $\frac12$ . Otherwise the gap can be shrunk by coding blocks of $m$ symbols at a time, which gives $H\le E(L)/m<H+\frac1m$ bits per symbol.

Watch

Source (six symbols)

the two trees being merged trees still waiting codeword lengths at the end

Six symbols, sorted by probability. Each one starts as a tree on its own.
Merge the two least likely trees. The new node's probability is their sum.
Repeat with the trees that remain: again take the two smallest.
And again. A merged node is treated exactly like a symbol.
After this merge only two trees are left.
The last merge makes the root.
Label left branches 0 and right branches 1. Each codeword is the path from the root to its symbol. Compare the average length with the entropy.

Worked example

A source emits five symbols with probabilities $0.4,\ 0.2,\ 0.15,\ 0.15,\ 0.1$ . Build a Huffman code and compare it with the entropy and with the Shannon–Fano lengths.

Carry out the merges.

$0.1+0.15=0.25$ . Now the smallest are $0.15$ and $0.2$ : $0.35$ . Then $0.25+0.35=0.6$ . Finally $0.4+0.6=1$ .
Read off the codeword lengths and the average length.

The symbol of probability 0.4 joins only at the last merge: length 1. The other four sit two merges below the 0.6 node: length 3 each. So $E(L)=0.4\cdot1+0.6\cdot3=2.2$ bits. One valid code is $0,\ 100,\ 101,\ 110,\ 111$ . Kraft: $\frac12+4\cdot\frac18=1$ .
Compute the entropy.

$H=0.4\log2.5+0.2\log5+2\cdot0.15\log\frac1{0.15}+0.1\log10\approx0.529+0.464+0.821+0.332=2.146$ bits. So $H\le E(L)<H+1$ , with a gap of only about 0.05 bits.
What do the Shannon–Fano lengths $\lceil-\log p_j\rceil$ give?

Lengths $2,3,3,3,4$ , so $E(L)=0.8+0.6+0.45+0.45+0.4=2.7$ bits. It also lies within 1 bit of $H$ , as the theorem promises, but Huffman does half a bit better.

Check your understanding

Is there a binary prefix-free code for four symbols with codeword lengths 1, 2, 2, 3?

Yes, for example 0, 10, 11, 110110 begins with 11, which is another codeword.
No
Yes, as long as the shortest word goes to the most likely symbolWhether the lengths are possible doesn't depend on the probabilities at all.

\frac12+\frac14+\frac14+\frac18=\frac98>1

, so Kraft–McMillan rules it out. Lengths 1, 2, 3, 3 would work: 0, 10, 110, 111.

A source has two symbols with probabilities 0.9 and 0.1, so $H\approx0.469$ bits. What is the average length of its Huffman code?

0.469 bitsCodeword lengths are whole numbers, and each symbol needs at least one bit.
1 bit
Somewhere between 0.469 and 1, depending on the codeWith two symbols the only sensible code is 0 and 1.

The code is

\{0,1\}

, with

E(L)=1

, more than twice the entropy. Coding pairs of symbols brings it down to 0.645 bits per symbol (see the first practice problem); longer blocks get closer still.

For which sources does the Huffman code achieve $E(L)=H$ exactly?

When every probability is a power of $\frac12$
When the source is uniformTry three equally likely symbols: $H=\log3\approx1.585$ , but the best code has lengths 1, 2, 2 and $E(L)=\frac53$ .
Always, since Huffman codes are optimalOptimal among codes, but codes have whole-number lengths, and $H$ usually isn't of that form.

E(L)-H=\sum p_j(l_j+\log p_j)

vanishes only if

l_j=-\log p_j

for each

j

, which needs

p_j=2^{-l_j}

. Try the "dyadic" source in the animation.

Practice

Coding pairsThe extension of a source

For the source with probabilities 0.9 and 0.1, code pairs of independent symbols. Build the Huffman code for the four pairs and find the average length per original symbol.

Solution

The pairs have probabilities 0.81, 0.09, 0.09, 0.01. Merge $0.01+0.09=0.10$ , then $0.09+0.10=0.19$ , then $0.19+0.81$ . Lengths: 1, 2, 3, 3, so $E(L)=0.81+0.18+0.27+0.03=1.29$ bits per pair, or 0.645 bits per symbol, against $H\approx0.469$ . The bound says blocks of length $m$ are within $\frac1m$ of $H$ per symbol.

Likely symbols get short wordsAn exchange argument

Show that in a code of minimal average length, if $p_i>p_j$ then $l_i\le l_j$ .

Solution

Suppose $p_i>p_j$ but $l_i>l_j$ . Swap the two codewords. The code is still prefix-free, and the average length changes by $p_il_j+p_jl_i-p_il_i-p_jl_j=-(p_i-p_j)(l_i-l_j)<0$ . So the original code was not minimal.

More practice: Applebaum, Exercises 7.9, 7.12 and 7.15.

SimulationApplebaum, Ch. 8: Random variables with probability density functions

Densities and the central limit theorem

Add up many independent random quantities and, whatever their own shape, the sum looks normal. That is the central limit theorem, and it is why the bell curve is everywhere. Pick a lopsided distribution below, add $n$ copies, and watch the histogram of the standardised sum turn into the normal curve.

The idea

Density.

X

has probability density function

f

if

P(a\le X\le b)=\int_a^b f(x)\,dx

for all

a\le b

. Then

E(X)=\int xf(x)\,dx

and

\mathrm{Var}(X)=\int(x-\mu)^2f(x)\,dx

. Examples: the uniform density on

(a,b)

, and the exponential density

\lambda e^{-\lambda x}

on

[0,\infty)

.

Chebyshev and the weak law.

P(|X-\mu|\ge c)\le\sigma^2/c^2

. Applied to the mean

\bar X_n

of

n

i.i.d. copies, whose variance is

\sigma^2/n

:

P(|\bar X_n-\mu|\ge c)\to0

as

n\to\infty

, for every

c>0

.

Normal law.

N(\mu,\sigma^2)

has density

\dfrac{1}{\sigma\sqrt{2\pi}}e^{-(x-\mu)^2/2\sigma^2}

. If

X\sim N(\mu,\sigma^2)

then

Z=(X-\mu)/\sigma\sim N(0,1)

, with distribution function

\Phi

.

Central limit theorem. If

X_1,X_2,\dots

are i.i.d. with mean

\mu

and finite variance

\sigma^2>0

, and

S_n=X_1+\dots+X_n

, then for every

z

P\!\left(\frac{S_n-n\mu}{\sigma\sqrt n}\le z\right)\longrightarrow\Phi(z)\qquad(n\to\infty).

Entropy of a density.

H(X)=-\int f\log f\,dx

. For

U(a,b)

it is

\log(b-a)

, which is negative when

b-a<1

; for

N(\mu,\sigma^2)

it is

\frac12\log(2\pi e\sigma^2)

, the largest possible for a density with variance

\sigma^2

.

Explore

Distribution of each term

Terms in the sum n 1

The law of one term

X_i

.

histogram of

(S_n-n\mu)/\sigma\sqrt n

standard normal density

Worked example

A fair die is rolled 100 times. Estimate the probability that the total is at least 380.

Find the mean and variance of a single roll.

$\mu=3.5$ , and $E(X^2)=\frac{91}6$ , so $\sigma^2=\frac{91}6-\frac{49}4=\frac{35}{12}\approx2.917$ .
Find the mean and standard deviation of the total $S$ .

$E(S)=350$ and $\mathrm{Var}(S)=100\cdot\frac{35}{12}\approx291.7$ , so the standard deviation is about $17.08$ .
Standardise and use the normal approximation.

$S$ takes whole-number values, so " $S\ge380$ " is the same as " $S\ge379.5$ " (a continuity correction). Then

$P(S\ge379.5)\approx1-\Phi\!\left(\frac{29.5}{17.08}\right)=1-\Phi(1.727)\approx0.042.$

The exact value, from convolving the die's law 100 times, is 0.0420.
What does Chebyshev's inequality give? Why is it so much weaker?

$P(|S-350|\ge30)\le291.7/900\approx0.32$ , and that bounds both tails together. Chebyshev uses only the variance, so it must hold for every distribution with that variance, including very spread-out ones. The CLT uses the fact that $S$ is a sum of many independent pieces.

Check your understanding

$X_1,\dots,X_n$ are i.i.d. Uniform(0, 1). For large $n$ , what does the CLT say about $S_n=X_1+\dots+X_n$ ?

It is approximately $N(n/2,\ n/12)$ .
It is approximately $N(1/2,\ 1/12)$ .Those are the mean and variance of one term. For a sum of independent terms, means add and variances add.
It is approximately uniform on $(0,n)$ .Run the simulator with the uniform law and $n=2$ : the sum is already a triangle, not flat.

E(S_n)=n\cdot\frac12

and

\mathrm{Var}(S_n)=n\cdot\frac1{12}

, and the CLT says the shape is approximately normal. For

n=12

,

S_{12}-6

is a classical quick approximation to

N(0,1)

.

Can a probability density function take values bigger than 1?

Yes
No, because $f(x)$ is a probability. $f(x)$ is a probability per unit length. Only its integrals are probabilities.
Only at finitely many points.The uniform density on $(0,\frac12)$ is 2 on the whole interval.

The uniform density on

(0,\frac12)

equals 2 there, and still

\int f=1

. A density must be non-negative and integrate to 1; it can be as tall as it likes on a short interval.

What is the entropy $-\int f\log f$ of the uniform density on $(0,\frac12)$ ?

$-1$ bit
It can't be negative, so 0.That is true for discrete entropy, where each $p_j\le1$ . A density can exceed 1, which makes $-\log f$ negative.
1 bitCheck the sign: $f=2$ and $-\log2=-1$ .

-\int_0^{1/2}2\log2\,dx=-1

. Continuous entropy is not a count of bits and can be negative. Differences of such entropies, such as mutual information, are still meaningful and non-negative.

Practice

Four hundred tossesNormal approximation to the binomial

A fair coin is tossed 400 times. Estimate the probability that the number of heads is between 190 and 210 inclusive.

Solution

The count is $b(400,\frac12)$ , with mean 200 and standard deviation $\sqrt{100}=10$ . With a continuity correction, $P(189.5\le S\le210.5)\approx\Phi(1.05)-\Phi(-1.05)\approx0.706$ . (The exact binomial value is also 0.706 to three places.)

From uniform to exponentialThe distribution-function method

Let $U$ be uniform on $(0,1)$ and $Y=-\ln U$ . Find the density of $Y$ .

Hint

Compute $P(Y>y)$ for $y\ge0$ first.

Solution

For $y\ge0$ , $P(Y>y)=P(U<e^{-y})=e^{-y}$ . So $F_Y(y)=1-e^{-y}$ and $f_Y(y)=e^{-y}$ : $Y$ is exponential with $\lambda=1$ . This is how the simulator above generates exponential samples.

More practice: Applebaum, Exercises 8.19, 8.34 and 8.37.

InteractiveApplebaum, Ch. 9: Random vectors

Random vectors and conditional densities

Two random quantities measured together have a joint density. Slicing it at $X=x$ gives the conditional density of $Y$ , and how much narrower that slice is than $Y$ 's own density measures how much $X$ tells you about $Y$ . For the bivariate normal everything is explicit.

The idea

Joint density.

P\big((X,Y)\in A\big)=\iint_A f(x,y)\,dx\,dy

. The marginal densities are

f_X(x)=\int f(x,y)\,dy

and

f_Y(y)=\int f(x,y)\,dx

.

Independence.

X

and

Y

are independent exactly when

f(x,y)=f_X(x)f_Y(y)

.

Conditional density. Where

f_X(x)>0

,

f_{Y\mid x}(y)=\dfrac{f(x,y)}{f_X(x)}

: the slice of the joint density along

X=x

, rescaled to have area 1.

Bivariate normal. With standard normal marginals and correlation

\rho\in(-1,1)

,

f(x,y)=\frac{1}{2\pi\sqrt{1-\rho^2}}\exp\!\left(-\frac{x^2-2\rho xy+y^2}{2(1-\rho^2)}\right), \qquad Y\mid X=x\ \sim\ N(\rho x,\ 1-\rho^2).

Information. Conditional entropy and mutual information carry over:

H(Y\mid X)=-\iint f\log f_{Y\mid x}(y)\,dx\,dy

and

I(X;Y)=H(Y)-H(Y\mid X)\ge0

. For the bivariate normal,

I(X;Y)=-\frac12\log(1-\rho^2)

. For a channel that adds independent noise

Z\sim N(0,N)

to an input of variance

P

, the capacity is

\frac12\log(1+P/N)

, attained by a normal input.

Explore

Correlation ρ

Contours of

f(x,y)

and 500 sample points. Drag the vertical line to choose

x

.

f_Y

f_{Y\mid x}

, the rescaled slice

Worked example

A point $(X,Y)$ is chosen uniformly in the unit disc $x^2+y^2<1$ . Find the marginal and conditional densities, and decide whether $X$ and $Y$ are correlated, and whether they are independent.

What is the joint density? Find $f_X$ .

The disc has area $\pi$ , so $f=\frac1\pi$ inside it. For $|x|<1$ , the vertical line at $x$ meets the disc in an interval of length $2\sqrt{1-x^2}$ , so $f_X(x)=\frac2\pi\sqrt{1-x^2}$ .
Find the conditional density of $Y$ given $X=x$ .

$f_{Y\mid x}(y)=\dfrac{1/\pi}{(2/\pi)\sqrt{1-x^2}}=\dfrac{1}{2\sqrt{1-x^2}}$ for $|y|<\sqrt{1-x^2}$ : uniform on the chord. Its spread depends on $x$ .
Compute $\mathrm{Cov}(X,Y)$ .

The disc is symmetric under $y\mapsto-y$ , so $E(Y)=0$ and $E(XY)=0$ . Hence $\mathrm{Cov}(X,Y)=0$ : uncorrelated.
Are $X$ and $Y$ independent?

No. At $(0.9,0.9)$ , outside the disc, $f=0$ , but $f_X(0.9)f_Y(0.9)>0$ . Equivalently, the conditional law of $Y$ changes with $x$ . (For the bivariate normal, by contrast, $\rho=0$ does give independence: set $\rho=0$ above and the slice matches $f_Y$ for every $x$ .)

Check your understanding

$(X,Y)$ is standard bivariate normal with $\rho=0.8$ . Given $X=1$ , what is the law of $Y$ ?

$N(1,\ 0.36)$ The conditional mean is $\rho x$ , not $x$ . Move the slice to $x=1$ and read off the peak.
$N(0.8,\ 0.36)$
$N(0.8,\ 1)$ Knowing $X$ also narrows the spread of $Y$ : the conditional variance is $1-\rho^2$ .

Y\mid X=x\sim N(\rho x,1-\rho^2)=N(0.8,0.36)

. The mean is pulled toward 0 compared with

x

(regression to the mean), and the variance doesn't depend on

x

.

$f(x,y)=x+y$ on the unit square $0<x,y<1$ . Are $X$ and $Y$ independent?

Yes, because the density lives on a rectangle.A rectangular range is needed for independence, but not enough. The density itself must factor.
No
Yes, by symmetry in $x$ and $y$ .Symmetry says $X$ and $Y$ have the same law, not that they are independent.

f_X(x)=x+\frac12

and

f_Y(y)=y+\frac12

, and

(x+\frac12)(y+\frac12)\ne x+y

in general (at

x=y=0

the left side is

\frac14

, the right 0).

What happens to $I(X;Y)$ for the bivariate normal as $\rho\to1$ ?

It tends to infinity.
It tends to 1 bit.1 bit is the most two binary variables can share. Continuous variables can share far more.
It tends to 0.The variables become more strongly dependent, not less. Slide ρ toward 0.95.

-\frac12\log(1-\rho^2)\to\infty

. As

\rho\to1

,

X

pins

Y

down to ever more decimal places, and each extra decimal place is more information.

Practice

A waiting-time pairMarginals and conditionals

$(X,Y)$ has joint density $f(x,y)=e^{-y}$ for $0<x<y$ . Find $f_X$ , $f_Y$ and both conditional densities.

Solution

$f_X(x)=\int_x^\infty e^{-y}dy=e^{-x}$ for $x>0$ , and $f_Y(y)=\int_0^y e^{-y}dx=ye^{-y}$ for $y>0$ . Then $f_{Y\mid x}(y)=e^{-(y-x)}$ for $y>x$ , so given $X=x$ , $Y-x$ is exponential with $\lambda=1$ . And $f_{X\mid y}(x)=\frac1y$ for $0<x<y$ : given $Y=y$ , $X$ is uniform on $(0,y)$ .

Is more power worth it?The Gaussian channel

Using $C=\frac12\log(1+P/N)$ , find how much the capacity increases when the signal power $P$ is doubled, first at $P/N=100$ , then at $P/N=0.01$ .

Solution

At $P/N=100$ : $\frac12\log\frac{201}{101}\approx0.496$ , so about half a bit more, on top of $\frac12\log101\approx3.33$ . At $P/N=0.01$ : $C$ goes from $\frac12\log1.01\approx0.00718$ to $\frac12\log1.02\approx0.01429$ , almost exactly double. At low signal-to-noise ratio capacity is roughly proportional to power; at high ratio, each doubling adds only half a bit.

More practice: Applebaum, Exercises 9.17, 9.22 and 9.27.

SimulationApplebaum, Ch. 10: Markov chains and their entropy

Markov chains and entropy rate

A Markov chain forgets everything except where it is now. That one rule makes it settle into an equilibrium from any start, and it makes the information it produces per step easy to compute. Set the two switching probabilities and watch the chain converge.

The idea

Markov chain. A sequence

X_0,X_1,\dots

on a finite state space with

P(X_{n+1}=j\mid X_n=i,\ X_{n-1},\dots,X_0)=P_{ij}

, depending only on

i

and

j

. The transition matrix

P

has non-negative entries and rows summing to 1.

Chapman–Kolmogorov. The

n

-step transition probabilities satisfy

P^{(m+n)}_{ij}=\sum_kP^{(m)}_{ik}P^{(n)}_{kj}

, so

P^{(n)}=P^n

. If

\pi^{(n)}

is the law of

X_n

, written as a row vector, then

\pi^{(n)}=\pi^{(0)}P^n

.

Invariant distribution. A law

\rho

with

\rho P=\rho

. If the chain starts with law

\rho

, every

X_n

has law

\rho

and the process is stationary. If some power

P^m

has all entries positive,

\rho

is unique and

\pi^{(n)}\to\rho

from every starting law.

Entropy rate.

h=\lim_{n\to\infty}\frac1nH(X_0,\dots,X_{n-1})

. For a stationary Markov chain,

h=H(X_1\mid X_0)=-\sum_i\rho_i\sum_jP_{ij}\log P_{ij},

the average, under $\rho$ , of the entropies of the rows of $P$ . It satisfies $h\le H(\rho)$ , with equality exactly when all the rows are equal, that is, when the $X_n$ are i.i.d.

Explore

a = P(0 → 1) b = P(1 → 0)

The chain, and a simulated path: state 0 state 1

P(X_n=0\mid X_0=0)

P(X_n=0\mid X_0=1)

\rho_0

Worked example

A particle moves on the states $0,1,2$ with transition matrix

P=\begin{pmatrix}\frac12&\frac12&0\\ \frac14&\frac12&\frac14\\ 0&\frac12&\frac12\end{pmatrix}.

Starting from 0, what is the law of $X_2$ ?

It is the first row of $P^2$ : $\big(\frac12\cdot\frac12+\frac12\cdot\frac14,\ \frac12\cdot\frac12+\frac12\cdot\frac12,\ \frac12\cdot\frac14\big)=\big(\frac38,\frac12,\frac18\big)$ .
Find the invariant distribution.

Solve $\rho P=\rho$ . The first column gives $\rho_0=\frac12\rho_0+\frac14\rho_1$ , so $\rho_1=2\rho_0$ ; by symmetry $\rho_1=2\rho_2$ . With $\rho_0+\rho_1+\rho_2=1$ : $\rho=(\frac14,\frac12,\frac14)$ . $P^2$ has all entries positive, so this is the limit from any start.
Compute the entropy rate.

The rows have entropies 1, 1.5 and 1 bits. So $h=\frac14\cdot1+\frac12\cdot1.5+\frac14\cdot1=1.25$ bits per step.
Compare with $H(\rho)$ and interpret.

$H(\rho)=\frac14\cdot2+\frac12\cdot1+\frac14\cdot2=1.5$ bits. An i.i.d. sequence with the same one-step law would produce 1.5 bits per step; the chain produces only 1.25, because each step is partly predictable from the last. A source like this can be compressed to about 1.25 bits per symbol, but only by a code that uses the previous symbol.

Check your understanding

The two-state chain above has $P(0\to1)=a$ and $P(1\to0)=b$ , with $a+b>0$ . What is $\rho_0$ , the long-run fraction of time in state 0?

$\dfrac{b}{a+b}$
$\dfrac{a}{a+b}$ A large $a$ means the chain leaves 0 quickly, so it should spend less time there, not more.
$\frac12$ , by symmetryThe two states are only symmetric when $a=b$ .

In equilibrium the flow out of 0 balances the flow in:

\rho_0a=\rho_1b

. With

\rho_0+\rho_1=1

this gives

\rho_0=b/(a+b)

.

Take $a=b=1$ : the chain switches state at every step. Starting from 0, does $P(X_n=0)$ converge?

Yes, to $\frac12$ Starting from 0, the chain is at 0 at every even time and at 1 at every odd time. Set both sliders to 1.
No, it alternates between 1 and 0, although $(\frac12,\frac12)$ is invariant.
No, and there is no invariant distribution.Check $(\frac12,\frac12)P$ .

P^n

alternates between the identity and the swap matrix, so no power has all entries positive and the convergence theorem doesn't apply. The chain is periodic. Its invariant law

(\frac12,\frac12)

still gives the long-run fraction of time in each state.

For a stationary Markov chain with invariant law $\rho$ , which is always true?

$h\le H(\rho)$
$h\ge H(\rho)$ $h=H(X_1\mid X_0)$ , and conditioning cannot increase entropy on average.
$h=H(\rho)$ Only when $X_1$ is independent of $X_0$ . Try $a=0.1,\ b=0.3$ .

h=H(X_1\mid X_0)\le H(X_1)=H(\rho)

, with equality exactly when

X_1

and

X_0

are independent, which for a Markov chain means every row of

P

equals

\rho

. For two states that is the line

a+b=1

.

Practice

A walk around a cycleDoubly stochastic matrices

A particle on the cycle $0,1,\dots,N-1$ ( $N\ge3$ ) steps one place clockwise or anticlockwise with probability $\frac12$ each. Show that the uniform law is invariant and find the entropy rate. For which $N$ does $P(X_n=0\mid X_0=0)$ converge?

Solution

Every column of $P$ also sums to 1, so $\frac1N(1,\dots,1)P=\frac1N(1,\dots,1)$ . Each row has two entries $\frac12$ , so $h=1$ bit per step, while $H(\rho)=\log N$ . For even $N$ the chain alternates between even and odd states, so $P(X_n=0\mid X_0=0)=0$ for odd $n$ and there is no convergence. For odd $N$ some power of $P$ is positive and the probability tends to $\frac1N$ .

A sticky chainEntropy rate of two states

Compute $\rho$ , $h$ and $H(\rho)$ for the two-state chain with $a=0.1$ , $b=0.3$ . Check your answers in the explorer.

Solution

$\rho=(\frac{0.3}{0.4},\frac{0.1}{0.4})=(0.75,0.25)$ . $h=0.75\,H_b(0.1)+0.25\,H_b(0.3)\approx0.75\cdot0.469+0.25\cdot0.881=0.572$ bits, while $H(\rho)=H_b(0.25)\approx0.811$ bits. The chain stays put most of the time, which makes it more predictable than an i.i.d. sequence spending the same fraction of time in each state.

More practice: Applebaum, Exercises 10.14, 10.23 and 10.24.