Chapter 0 wrap-up

Readiness: what information theory leans on

Closing thought

Every tool here serves one job: measuring how much you learn from an uncertain outcome. Random variables, joint tables, and Bayes' theorem describe the outcomes and how they relate. Convexity and Jensen's inequality say which way the gap goes when you average first and apply a function second. That gap is behind almost every inequality ahead. Markov chains describe sources whose next symbol depends on the current one, and the stationary distribution is where such a chain settles. The logarithm is the one function that makes information from independent events add.

You can now check the pieces the next chapters lean on. For the concave $\log$ , Jensen gives $E[\log X] \le \log E[X]$ . A two-state weather chain that stays sunny with probability 0.9 and stays rainy with probability 0.5 settles at $\frac{5}{6}$ sunny. Two fair coins give $\log_2 4 = 2$ , which is $\log_2 2 + \log_2 2$ , one share for each coin. Chapter 1 asks what information is measuring in the first place. It builds a number for how surprising a single outcome is.

Recipes in this chapter

Step-by-step procedures for the problem types this chapter teaches.

Solve for a Markov chain's stationary distribution Stationary distributions

Chapter review

One practice set per topic this chapter taught — same fixed, ungraded ladders as the practice panels inside each section.

Practice: Chapter review: random variables, joint distributions, and Bayes' theorem (5 problems · doesn’t affect your progress)

A network engineer counts how many packets are lost in a burst of 50 transmitted packets. Is this random variable discrete or continuous?

Correct! 🎉 Not quite.

Right on try — credit. Right — the answer had already been shown, so no credit this time. Next try is worth Answer shown after three tries — this one no longer earns credit. You chose to see the answer — this one earns no credit.

A count can only land on whole numbers, never in between — that's discrete, not continuous.

It's still genuinely random — which of the 51 possible counts occurs isn't known in advance.

Every protocol's loss count is still a whole-number count — the discrete/continuous distinction doesn't depend on protocol details.

Why

A loss count only takes whole-number values $0,1,\ldots,50$ — the defining trait of a discrete random variable.

Discrete — it only takes whole-number values 0 through 50

A joint pmf has $p(0,0)=0.2$ , $p(0,1)=0.3$ , $p(1,0)=0.15$ , $p(1,1)=0.35$ . Find $p(Y=1 \mid X=0)$ .

Correct! 🎉 Not quite.

Why

$p(X=0) = p(0,0)+p(0,1) = 0.5$ , so $p(Y=1\mid X=0) = p(0,1)/p(X=0) = 0.3/0.5 = 0.6$ .

Correct answer

Also accepted:

Why

Restrict to the row where $X=0$ first, then divide the $Y=1$ cell by the sum of that whole row.

0.6

A disease has 3% prevalence, a test has 90% sensitivity and 92% specificity (8% false-positive rate). Compute the evidence term $P(\text{positive})$ using the law of total probability.

Correct! 🎉 Not quite.

Why

$P(\text{positive}) = 0.90(0.03) + 0.08(0.97) = 0.027+0.0776=0.1046$ .

Correct answer

Also accepted:

Why

Sum the true-positive contribution (sensitivity times prevalence) and the false-positive contribution (false-positive rate times the healthy share) separately, then add.

0.1046

Using the same numbers (3% prevalence, 90% sensitivity, evidence term $P(\text{positive})=0.1046$ ), find $P(\text{disease}\mid\text{positive})$ .

Correct! 🎉 Not quite.

Why

$P(\text{disease}\mid\text{positive}) = \dfrac{0.90\times 0.03}{0.1046} = \dfrac{0.027}{0.1046}\approx 0.258$ .

Correct answer

Also accepted:

Why

The numerator is the sensitivity times the prior alone — you already have the denominator from the previous problem.

0.258

For a joint table where every one of the four cells equals $0.25$ , are the two variables independent?

Correct! 🎉 Not quite.

Equal cells is exactly what makes the table match the product-of-marginals test, not a sign of dependence.

Independence is a property of the numbers in the table, not of what the variables are called.

The independence test itself doesn't care how many values each variable can take — it just compares cells to marginal products.

Why

Every marginal here is $0.5$ , and $0.5\times 0.5=0.25$ matches every cell exactly — the independence condition $p(x,y)=p(x)p(y)$ holds at every cell, so the variables are independent.

Yes — each cell equals the product of its row total (0.5) and column total (0.5)

Practice: Chapter review: convexity and Jensen's inequality (5 problems · doesn’t affect your progress)

Jensen's inequality's direction for $g$ depends on one single property of $g$ . What property is that?

Correct! 🎉 Not quite.

Monotonicity isn't what flips the inequality's direction — a function can be increasing and either convex or concave.

The sign of $g$ 's output doesn't determine which way the inequality points.

Symmetry properties like even/odd aren't what Jensen's inequality depends on.

Why

Convex gives $E[g(X)]\geq g(E[X])$ and concave gives $E[g(X)]\leq g(E[X])$ — the single property that decides the direction is exactly which of the two shapes $g$ has.

Whether $g$ is convex or concave

For $g(x) = x^3 + x$ , compute $g''(2)$ .

Correct! 🎉 Not quite.

Why

$g'(x)=3x^2+1$ , $g''(x)=6x$ , so $g''(2)=12$ .

Correct answer

Also accepted:

Why

Differentiate $g(x)=x^3+x$ twice first, then substitute $x=2$ into the resulting expression.

Using $g''(x)=6x$ from the previous problem, on which interval is $g(x)=x^3+x$ convex?

Correct! 🎉 Not quite.

Check the sign of $6x$ on that interval — it isn't nonnegative there.

$6x$ changes sign at $x=0$ , so convexity can't hold on the whole real line.

$6x$ is positive for $x>0$ , which does give convexity there.

Why

$g''(x)=6x \geq 0$ exactly when $x\geq 0$ , so $g$ is convex on $[0,\infty)$ and concave on $(-\infty,0]$ .

$g''(x)=6x$ is a straight line through the origin — find where it's nonnegative.

x > 0

Using the convex function $g(x)=x^2$ and $X$ taking values $-2$ , $0$ , and $3$ with probabilities $0.3$ , $0.4$ , and $0.3$ , find $E[g(X)]$ alone (not $g(E[X])$ ).

Correct! 🎉 Not quite.

Why

$E[g(X)] = E[X^2] = 0.3(4)+0.4(0)+0.3(9) = 1.2+2.7=3.9$ . Separately, $E[X]=0.3$ so $g(E[X])=(0.3)^2=0.09$ — confirming $E[g(X)]=3.9 \geq 0.09=g(E[X])$ , exactly the direction Jensen's inequality guarantees for a convex $g$ .

Correct answer

Also accepted:

Why

Average $g(x)=x^2$ evaluated at each of the three outcomes, weighted by its own probability — don't average $X$ first.

3.9

Chapter 2 will define entropy using $-x\log_2 x$ , shown in this chapter to be concave on $(0,1]$ . Given that Jensen's inequality for a CONCAVE function gives $E[g(X)]\leq g(E[X])$ , what does this predict about averaging two probability values and THEN applying $-x\log_2 x$ , versus applying it first and averaging?

Correct! 🎉 Not quite.

That's the direction for a CONVEX function — this function is concave, so the inequality points the other way.

Equality only holds in the special case where there's nothing to average over — in general the two orders differ.

Concavity alone, without any specific numbers, already fixes which direction the inequality points.

Why

For concave $g$ , $E[g(X)]\leq g(E[X])$ — applying $g$ first and then averaging is never bigger than averaging first and applying $g$ once. This is the exact mechanism behind entropy's key non-negativity and concavity properties in the chapters ahead.

Averaging first, then applying the concave function, gives a result at least as large

Practice: Chapter review: Markov chains and stationary distributions (5 problems · doesn’t affect your progress)

A vending machine's tomorrow inventory level depends only on today's inventory level and today's sales (not on any earlier day's inventory). Is this process Markov (unit memory) in the inventory level?

Correct! 🎉 Not quite.

The unit-memory property doesn't forbid fresh, day-of randomness — it only forbids the next state depending on states further back than the current one.

Restocking frequency doesn't affect whether the process has unit memory — that's about how far back the dependence reaches.

Unit memory allows the next state to be random, not just deterministic — what it restricts is which PAST states matter.

Why

As long as tomorrow's inventory depends only on today's inventory (plus today's own randomness), no earlier day's inventory matters — that's exactly the unit-memory property.

Yes — the next state depends only on the current state (plus fresh randomness, not old history)

A transition matrix's column has entries $0.55$ , $0.25$ , and an unknown third entry. What must the third entry be?

Correct! 🎉 Not quite.

Why

Every column must sum to 1: $0.55+0.25+x=1 \Rightarrow x=0.2$ .

Correct answer

Also accepted:

Why

0.2

A three-state chain's stationary distribution has $\pi_1=0.5$ and $\pi_2=0.3$ . What must $\pi_3$ equal?

Correct! 🎉 Not quite.

Why

Every stationary distribution's entries sum to 1, like any probability distribution: $\pi_3 = 1-0.5-0.3=0.2$ .

Correct answer

Also accepted:

Why

A stationary distribution is still a probability distribution — all its entries have to sum to 1.

0.2

A random-walk Markov chain on a social network has two separate clusters of users that never interact (no connections crossing between clusters). What does this imply about the chain's stationary distribution?

Correct! 🎉 Not quite.

Uniqueness specifically requires irreducibility — every state reachable from every other — which two disconnected clusters violate.

A stationary distribution still exists on each separate cluster — it's the UNIQUENESS across the whole chain that fails.

Whether the network is connected has nothing to do with the Markov (unit-memory) property — that's a separate structural question.

Why

Without irreducibility, each cluster has its own stationary distribution, and any weighted combination of the two is also stationary for the whole network — uniqueness specifically requires irreducibility.

Not unique — infinitely many exist, one weighted combination per cluster

Chapter 8 will define a Markov source's entropy rate as a weighted average over states, weighted by the stationary distribution $\boldsymbol\pi$ . Why does the entropy rate need $\boldsymbol\pi$ specifically, rather than weighting every state equally?

Correct! 🎉 Not quite.

Equal weighting is perfectly possible arithmetically — it's just the wrong weighting, since it would ignore how often each state actually occurs long-run.

The stationary-distribution weighting applies no matter how many states the chain has, including just two.

The entropy rate is defined specifically AS a frequency-weighted average — state frequency is the whole point of using $\boldsymbol\pi$ .

Why

A Markov source spends different long-run fractions of time in different states, and $\boldsymbol\pi$ is exactly that fraction for each state — weighting the per-state uncertainty by $\boldsymbol\pi$ is what makes 'entropy per symbol' a meaningful long-run average rather than an arbitrary equal-weighted one.

Because in the long run the chain visits different states with different frequencies, and $\boldsymbol\pi$ captures exactly those frequencies

Practice: Chapter review: why logarithms measure information (4 problems · doesn’t affect your progress)

Suppose an information measure $f$ satisfies $f(p) = 5\log_2 p$ instead of $-\log_2 p$ . Does it still satisfy the additivity requirement $f(pq)=f(p)+f(q)$ ?

Correct! 🎉 Not quite.

Additivity doesn't pin down the constant or its sign at all — that comes from the separate decreasing requirement.

A constant multiple carries straight through the functional equation on both sides — it doesn't break anything.

The functional equation is required to hold for every $p,q\in(0,1]$ , not just when they happen to be equal.

Why

$5\log_2(pq) = 5\log_2 p + 5\log_2 q$ — additivity survives any constant multiple. It's the separate DECREASING requirement, not additivity, that rules out a positive constant like 5 and forces a negative one instead.

Yes — additivity holds for any constant multiple of a logarithm, not just $-\log_2$

Confirm additivity for $p=q=0.8$ : compute $-\log_2(pq) - \big[-\log_2(p) - \log_2(q)\big]$ .

Correct! 🎉 Not quite.

Why

$-\log_2(0.64) \approx 0.6439$ and $-\log_2(0.8)-\log_2(0.8) \approx 0.3219\times 2 = 0.6439$ — they match exactly, confirming additivity even when the two events are identical, not just when they're different.

Correct answer

Also accepted:

Why

Compute $-\log_2(0.64)$ as one number, then separately compute $-\log_2(0.8)$ and double it, then compare.

Which of these fails the DECREASING requirement for an information measure, even though it satisfies additivity?

Correct! 🎉 Not quite.

This one is decreasing in $p$ — it's the standard choice, and it satisfies both requirements.

A negative constant multiple of $\log_2$ is still decreasing in $p$ .

A negative constant multiple of $\log_2$ is still decreasing in $p$ , just more gently than $-\log_2 p$ itself.

Why

$\log_2 p$ INCREASES as $p$ grows, the opposite of what an information measure needs — a rarer (smaller) $p$ should give MORE information, not less, so a positive multiple of $\log_2$ fails the decreasing requirement even though it satisfies additivity.

f(p) = \log_2 p

Choosing base $e$ instead of base $2$ in $f(p)=-\log_b p$ changes the numeric value of the measure. Does it change whether additivity holds?

Correct! 🎉 Not quite.

Every base gives a valid, additive measure — base 2 isn't special for additivity, only conventional for units (bits).

Natural log satisfies exactly the same functional equation as base-2 log — changing base is just a constant rescaling.

This holds for every probability in $(0,1]$ , not just one special value.

Why

Any base gives a valid, additive information measure — the base only rescales the answer by a constant factor, which is exactly why 'bits' (base 2) and 'nats' (base $e$ ) are unit conversions of the same underlying quantity.

No — additivity holds for any base, since changing base only rescales by a constant factor

Take the chapter quiz On to Chapter 1 →

← Why logarithms measure information The concept of information →