7. Probability and Information Theory

Introduction and Context

Computer science deals continually with incomplete information. A communication channel may corrupt a transmitted bit, a classifier may be uncertain about an image, a distributed system may fail unpredictably, and a security analyst may need to assess the likelihood of an attack. Probability provides the mathematical language for representing and reasoning about such uncertainty. Information theory, built on probability, measures uncertainty, information content, and the capacity of systems to store or communicate information.

These subjects are not isolated mathematical topics. They support machine learning, artificial intelligence, data compression, cryptography, statistical computing, networking, randomized algorithms, reliability engineering, and decision support. For postgraduate students, the central task is not merely to calculate probabilities, but to construct appropriate models, identify assumptions, interpret results, and understand the limitations of those models.

Probability describes possible outcomes and their likelihoods. Information theory describes how much uncertainty is reduced when an outcome is observed. Together, they provide a rigorous framework for modelling data and making decisions under uncertainty.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Define sample spaces, events, probability measures, random variables, and distributions.

2. Compute and interpret expectation, variance, covariance, and common discrete and continuous distributions.

3. Apply conditional probability, independence, Bayes’ theorem, and the law of total probability.

4. Use concentration inequalities to reason about deviations from expected behaviour.

5. Explain entropy, joint and conditional entropy, mutual information, and relative entropy.

6. Relate information-theoretic measures to compression, learning, communication, and privacy.

7. Evaluate assumptions, modelling errors, ethical issues, and practical limitations in probabilistic systems.

7.1 The Probabilistic Model

A probability model consists of a sample space, a collection of events, and a probability measure. The sample space Ω is the set of all possible outcomes. An event is a subset of Ω. A probability measure P assigns a number between 0 and 1 to each event and satisfies:

• P(Ω) = 1;
• P(A) ≥ 0 for every event A;
• for mutually exclusive events A₁, A₂, …, P(∪ᵢAᵢ) = ΣᵢP(Aᵢ).

The third property is countable additivity. It ensures that probability remains consistent when an event is decomposed into disjoint alternatives.

For example, in a binary communication system, Ω = {0,1} for one transmitted bit. If the probability of receiving a 1 is p, then P({1}) = p and P({0}) = 1 − p. A more realistic model may include the transmitted bit, received bit, noise state, and time, producing a larger sample space.

Events can be combined using set operations. The complement Aᶜ represents the event that A does not occur. The union A ∪ B means that at least one occurs, while A ∩ B means that both occur. The inclusion–exclusion identity is

P(A ∪ B) = P(A) + P(B) − P(A ∩ B).

This identity is important because simply adding probabilities double-counts outcomes in the intersection.

Random Variables and Distributions

A random variable is a function X: Ω → R that assigns a numerical value to each outcome. It is not itself random in the programming sense; uncertainty concerns which value will be observed.

A discrete random variable has a probability mass function (PMF), pX(x) = P(X = x). A continuous random variable is described by a probability density function (PDF) fX(x), where probabilities are obtained by integration:

P(a ≤ X ≤ b) = ∫ₐᵇ fX(x) dx.

For continuous variables, P(X = x) is generally zero, even though intervals have positive probability. The cumulative distribution function (CDF), FX(x) = P(X ≤ x), applies to both discrete and continuous variables and is often the most useful complete description of a distribution.

The Bernoulli distribution models one trial with success probability p. If X ∈ {0,1}, then E[X] = p and Var(X) = p(1 − p). The binomial distribution models the number of successes in n independent Bernoulli trials:

P(X = k) = C(n,k)pᵏ(1 − p)ⁿ⁻ᵏ.

The Poisson distribution, with parameter λ, models counts of events over a fixed interval when events occur independently at an approximately constant rate:

P(X = k) = e⁻λ λᵏ/k!.

Its mean and variance are both λ. The normal distribution is described by mean μ and variance σ². It is important because sums of many independent effects often become approximately normal under the central limit theorem.

Expectation and Variability

The expectation or mean of a discrete random variable is

E[X] = Σₓ xP(X = x),

and for a continuous variable it is E[X] = ∫ xfX(x) dx, provided the quantity exists. Expectation is a long-run average or model-based centre; it need not be an outcome that can actually occur.

For a function g, the law of the unconscious statistician gives E[g(X)] directly from the distribution of X. This is useful when the distribution of g(X) is difficult to derive.

Variance measures dispersion around the mean:

Var(X) = E[(X − E[X])²] = E[X²] − (E[X])².

The standard deviation is the square root of variance and has the same units as X. If X and Y are random variables, covariance is

Cov(X,Y) = E[(X − E[X])(Y − E[Y])].

The correlation coefficient normalizes covariance to the interval [−1,1]. Zero covariance indicates linear uncorrelatedness, but it does not generally imply independence.

Expectation is linear: E[aX + bY] = aE[X] + bE[Y], regardless of whether X and Y are independent. Variance, however, satisfies Var(X + Y) = Var(X) + Var(Y) only when covariance is zero.

7.2 Conditional Reasoning and Bayesian Inference

Conditional probability measures the likelihood of A after B is known:

P(A|B) = P(A ∩ B)/P(B), provided P(B) > 0.

The multiplication rule follows immediately:

P(A ∩ B) = P(A|B)P(B).

Events A and B are independent when P(A|B) = P(A), equivalently P(A ∩ B) = P(A)P(B). Independence is a modelling assumption, not a conclusion obtained merely because two events seem unrelated.

If B₁, …, Bₙ partition the sample space, the law of total probability states:

P(A) = Σᵢ P(A|Bᵢ)P(Bᵢ).

Bayes’ theorem reverses conditional direction:

P(B|A) = P(A|B)P(B)/P(A).

Here P(B) is the prior probability, P(A|B) is the likelihood, P(A) is the evidence, and P(B|A) is the posterior probability. Bayesian reasoning is especially important when evidence is imperfect or class frequencies are unequal.

Consider a security detector that identifies an attack with sensitivity 0.99, while the attack base rate is 0.001. Suppose its false-positive rate is 0.01. Then

P(attack|alert) = (0.99 × 0.001)/[(0.99 × 0.001) + (0.01 × 0.999)] ≈ 0.090.

Thus, despite a high sensitivity, only about 9 percent of alerts represent attacks under these assumptions. Ignoring the base rate would produce a seriously misleading interpretation.

Random Variables Given Other Variables

For random variables X and Y, the conditional expectation E[X|Y] is itself a random variable: it assigns the best mean-squared prediction of X for each observed value of Y. The law of total expectation is

E[X] = E[E[X|Y]].

The law of total variance decomposes uncertainty into within-group and between-group components:

Var(X) = E[Var(X|Y)] + Var(E[X|Y]).

These identities underpin hierarchical modelling, regression, risk decomposition, and probabilistic graphical models.

7.3 Concentration and Limit Behaviour

An expectation alone does not describe how likely a large deviation is. Concentration inequalities provide distribution-independent bounds.

Markov’s inequality states that for a non-negative random variable X and a > 0,

P(X ≥ a) ≤ E[X]/a.

It is broadly applicable but often loose. Chebyshev’s inequality states:

P(|X − μ| ≥ t) ≤ σ²/t².

It uses variance and applies without requiring a particular distribution.

For sums or averages of independent bounded variables, Hoeffding’s inequality gives exponentially decreasing bounds. If Xᵢ ∈ [aᵢ,bᵢ] are independent, then

P(Σᵢ(Xᵢ − E[Xᵢ]) ≥ t) ≤ exp(−2t²/Σᵢ(bᵢ−aᵢ)²).

These bounds are central to learning theory because they quantify how many observations are needed for empirical performance to approximate expected performance.

The law of large numbers states that sample averages converge to the expected value under suitable conditions. The central limit theorem states, broadly, that normalized sums of many independent observations approach a normal distribution, even when the individual observations are not normal. Neither theorem says that every finite sample is accurate; convergence rate and assumptions remain important.

7.4 Entropy: Measuring Uncertainty

Probability tells us how likely outcomes are; entropy measures the uncertainty of a distribution. For a discrete random variable X,

H(X) = −Σₓ p(x) log₂ p(x).

Entropy is measured in bits when the logarithm is base 2. A certain event has entropy zero. For a binary variable with equal probabilities, entropy is one bit, the maximum for a binary alphabet. Entropy is maximized by the uniform distribution over a finite set because uncertainty is greatest when no outcome is favoured.

The quantity −log₂ p(x) is the self-information or surprisal of outcome x. Rare events carry more information when they occur. Entropy is the expected surprisal.

For two variables, joint entropy is

H(X,Y) = −Σₓ,ᵧ p(x,y)log₂p(x,y).

Conditional entropy is

H(Y|X) = H(X,Y) − H(X),

representing the remaining uncertainty about Y after observing X. It is never greater than H(Y): information cannot increase uncertainty when conditioning on an observed variable in the ordinary Shannon framework.

The mutual information between X and Y is

I(X;Y) = H(X) − H(X|Y) = H(Y) − H(Y|X).

It measures the reduction in uncertainty about one variable obtained from the other. Mutual information is zero precisely when X and Y are independent. It is widely used for feature selection, representation learning, clustering, and analysing communication channels.

Relative Entropy and Divergence

The Kullback–Leibler (KL) divergence from Q to P is

Dₖₗ(P||Q) = Σₓ p(x)log₂[p(x)/q(x)].

It measures the inefficiency or discrepancy incurred when Q is used to represent data generated by P. KL divergence is non-negative and equals zero only when P = Q, but it is not symmetric and therefore is not a distance metric. It becomes infinite if P assigns positive probability to an outcome that Q assigns probability zero.

Cross-entropy is

H(P,Q) = −Σₓ p(x)log₂q(x) = H(P) + Dₖₗ(P||Q).

Minimizing cross-entropy is therefore equivalent to minimizing KL divergence from the true distribution, apart from the constant H(P). This explains the central role of cross-entropy loss in classification and language modelling.

7.5 Information in Communication and Computation

A communication channel maps an input X to an output Y probabilistically. The channel’s uncertainty is described by P(Y|X). A noisy binary symmetric channel flips a bit with probability ε. Its capacity, the maximum reliable information rate per use, is

C = 1 − H₂(ε),

where H₂ is binary entropy, for ε between 0 and 1/2. Capacity is not the guaranteed rate of every coding scheme; it is an asymptotic theoretical limit under suitable coding and block-length assumptions.

Source coding seeks compact representations. Shannon’s source coding theorem states that lossless compression cannot, in the long run, use fewer than H(X) bits per symbol on average, although practical codes approach this limit under appropriate conditions. Huffman coding exploits symbol probabilities to assign shorter codes to common symbols. Arithmetic coding can approach entropy more closely for large or structured sources.

Lossy compression accepts controlled distortion to achieve lower rates. Rate–distortion theory studies the minimum rate required to represent a source while keeping expected distortion below a specified level. This framework informs image, audio, and video compression.

In computing, entropy also supports randomized algorithms, anomaly detection, uncertainty estimation, and privacy analysis. However, high entropy does not automatically imply usefulness, security, or fairness. The meaning of a measure depends on the model, data quality, and decision context.

7.6 Applications in Computing and Professional Practice

In machine learning, probabilistic models express predictive uncertainty and support Bayesian updating. Naïve Bayes classifiers use conditional independence assumptions to estimate class posteriors. Decision trees may select splits using information gain, which is a mutual-information reduction in label uncertainty. Neural classifiers are commonly trained with cross-entropy, although a low loss does not guarantee calibrated probabilities.

In distributed systems, probability helps estimate availability, queueing delays, replication failures, and expected resource demand. Reliability models combine component failure probabilities, while Monte Carlo simulation estimates quantities that are difficult to derive analytically.

In cybersecurity, Bayesian inference updates threat assessments as logs and alerts arrive. Entropy can assess password spaces or cryptographic key uncertainty, but measured entropy may be overstated when users choose correlated or predictable values. Differential privacy uses calibrated randomness to limit the information that a released dataset reveals about an individual. Its guarantees are formal and should not be confused with simply removing names from records.

In software testing and quality engineering, statistical sampling and confidence bounds help estimate defect rates. In operations, expected loss combines possible impacts with their probabilities, but rare catastrophic events require tail analysis rather than reliance on average loss alone.

7.7 Illustrative Case Study: Bayesian Fault Diagnosis in a Data Centre

Background

A cloud service provider operates a cluster in which an automated monitoring system reports whether a server is overheating. The engineering team wants to decide whether an alert should trigger immediate shutdown.

Situation

Assume that, on a randomly selected observation interval, the probability of genuine overheating is 0.002. The sensor detects overheating with probability 0.98 and reports overheating incorrectly with probability 0.015 when the server is normal.

Analysis

Let O denote overheating and A denote an alert. The probability of an alert is

P(A) = P(A|O)P(O) + P(A|Oᶜ)P(Oᶜ)

= (0.98)(0.002) + (0.015)(0.998)

= 0.01693 approximately.

The posterior probability of overheating after an alert is

P(O|A) = (0.98 × 0.002)/0.01693 ≈ 0.116.

Only about 11.6 percent of alerts correspond to actual overheating. A shutdown policy based on every alert would therefore cause many unnecessary interruptions.

Approach

The provider introduces a two-stage policy. A first alert creates a high-priority diagnostic event. Shutdown occurs only if a second independent sensor confirms the condition or if temperature continues rising. The team also verifies whether the assumed independence of sensors is realistic; shared calibration errors could make the combined evidence less informative than expected.

Outcome

The policy distinguishes detection from decision. The first sensor remains valuable for sensitivity, while a confirmation stage reduces false shutdowns. Thresholds are selected by comparing the cost of service interruption with the cost of delayed intervention.

Learning Points

1. Base rates strongly affect posterior probabilities.

2. A technically accurate detector may still generate mostly false alarms for rare events.

3. Conditional independence assumptions must be examined rather than silently accepted.

4. Probabilities should support decisions whose costs and consequences are explicit.

7.8 Limitations, Risks, and Ethical Considerations

Probability models are conditional on assumptions. Incorrect sample spaces, dependence ignored as independence, biased data, selection effects, and measurement error can invalidate apparently precise conclusions. A model may also be statistically accurate on average while performing poorly for a minority group.

Confusing P(A|B) with P(B|A) is a common error. Another is interpreting correlation as causation. Small samples can produce unstable estimates, and repeated testing can inflate false discoveries. In machine learning, a model may be overconfident even when its classification accuracy is high; calibration and proper scoring rules are therefore important.

Ethically, probabilistic decisions affecting employment, credit, healthcare, education, or policing require attention to fairness, explainability, contestability, and privacy. Historical data may encode discrimination. A probability estimate should not be treated as an immutable label about an individual. Governance should specify data provenance, validation, monitoring, human oversight, and procedures for correcting errors.

Entropy and anonymization can also be misused. Aggregation or removal of direct identifiers does not necessarily prevent re-identification when auxiliary data are available. Security systems must report uncertainty honestly rather than presenting risk scores as certainty.

7.9 Best Practices and Emerging Directions

Sound probabilistic practice begins with clearly defining the random experiment, population, variables, and decision objective. Analysts should state assumptions, use appropriate distributions, distinguish aleatory randomness from epistemic uncertainty, and report intervals or distributions rather than unjustified point certainty. Sensitivity analysis should examine how conclusions change when priors, error rates, or dependence assumptions change.

For deployed systems, probabilities should be calibrated and monitored for dataset shift. Reproducible estimation, proper scoring rules, uncertainty-aware visualizations, and independent validation improve reliability. Simulation is useful when analytical solutions are unavailable, but simulation results inherit the validity of the input model.

Current developments include probabilistic programming, Bayesian deep learning, conformal prediction, causal inference, information-theoretic representation learning, privacy-preserving analytics, and foundation models that estimate distributions over language or multimodal data. These methods expand capability but also increase the need for computational efficiency, interpretability, robustness, and responsible governance.

Chapter Summary

Probability provides a formal language for uncertain outcomes through sample spaces, events, random variables, and distributions. Expectation describes average behaviour, while variance and covariance describe variability and dependence. Conditional probability, total probability, and Bayes’ theorem support evidence-based updating, although their usefulness depends on valid priors, likelihoods, and assumptions.

Markov, Chebyshev, and Hoeffding inequalities bound deviations, while the laws of large numbers and the central limit theorem explain the behaviour of averages and sums. Information theory measures uncertainty using entropy, remaining uncertainty using conditional entropy, and shared information using mutual information. KL divergence and cross-entropy quantify distributional mismatch and underpin modern learning objectives. These concepts support compression, communication, machine learning, cybersecurity, reliability, privacy, and decision-making. Responsible use requires attention to dependence, base rates, calibration, bias, privacy, and the consequences of probabilistic errors.

Key Terms

Sample space: Set of all possible outcomes of a random experiment.

Event: A subset of the sample space to which a probability is assigned.

Probability measure: Function assigning consistent probabilities to events.

Random variable: Function that maps outcomes to numerical values.

PMF: Function giving probabilities of values of a discrete random variable.

PDF: Density function whose integration over an interval gives probability.

CDF: Function F(x) = P(X ≤ x).

Expectation: Probability-weighted average value of a random variable.

Variance: Expected squared deviation from the mean.

Covariance: Measure of joint linear variation between two variables.

Independence: Condition in which knowledge of one event does not change the probability of another.

Conditional probability: Probability of an event given that another event is known.

Bayes’ theorem: Rule for reversing conditional probabilities using priors and evidence.

Entropy: Expected uncertainty or surprisal of a random variable.

Conditional entropy: Uncertainty remaining in one variable after observing another.

Mutual information: Reduction in uncertainty produced by observing another variable.

KL divergence: Non-symmetric measure of discrepancy between probability distributions.

Cross-entropy: Expected coding loss when one distribution represents another.

Concentration inequality: Bound on the probability of deviation from expected behaviour.

Channel capacity: Maximum asymptotically reliable information rate of a communication channel.

Review Questions

Short Answer Questions

1. What are the three defining properties of a probability measure?

2. Distinguish a probability mass function from a probability density function.

3. State Bayes’ theorem and identify its prior, likelihood, evidence, and posterior terms.

4. What does mutual information measure?

5. Why does zero covariance not generally imply independence?

Long Answer Questions

1. Explain random variables, CDFs, expectation, variance, and covariance with suitable computing examples.

2. Derive the law of total probability and explain its role in Bayesian inference.

3. Compare Markov, Chebyshev, and Hoeffding inequalities in terms of assumptions and usefulness.

4. Explain entropy, conditional entropy, mutual information, KL divergence, and cross-entropy, including their relationships.

5. Discuss the role of probability and information theory in machine learning, compression, cybersecurity, and privacy.

Analytical / Application Questions

1. A fraud detector has a true-positive rate of 0.95, a false-positive rate of 0.04, and a fraud base rate of 0.005. Derive the probability that a transaction is fraudulent after an alert and interpret the result.

2. A data scientist assumes that two sensor readings are independent because they are produced by different devices. Design an analysis to test whether shared environmental factors invalidate this assumption.

3. A classifier has high accuracy but poorly calibrated probabilities. Explain why this may be dangerous in medical or security decisions and propose suitable evaluation measures.

22. Multiple Choice Questions with Answers

Question 1

A security alert has sensitivity 0.99, false-positive rate 0.01, and attack base rate 0.001. What is approximately the probability that an alert represents a genuine attack?

A. 0.001

B. 0.009

C. 0.090

D. 0.990

Correct Answer: C. 0.090

Question 2

Which statement about expectation is correct?

A. It must be an outcome that can actually occur.

B. It is always equal to the median.

C. It is linear even when variables are dependent.

D. It is defined only for continuous variables.

Correct Answer: C. It is linear even when variables are dependent.

Question 3

If X and Y are independent, which identity must hold?

A. Cov(X,Y)=1

B. P(X,Y)=P(X)+P(Y)

C. H(X|Y)=H(X)

D. E[X|Y]=Y

Correct Answer: C. H(X|Y)=H(X)

Question 4

For a non-negative random variable X, Markov’s inequality bounds which quantity?

A. P(X≤a)

B. P(X≥a)

C. Var(X)

D. Cov(X,Y)

Correct Answer: B. P(X≥a)

Question 5

The entropy of a binary variable is maximized when its two outcomes have probabilities:

A. 0.99 and 0.01

B. 0.75 and 0.25

C. 0.5 and 0.5

D. 1 and 0

Correct Answer: C. 0.5 and 0.5

Question 6

What does mutual information I(X;Y)=0 imply for discrete variables?

A. X and Y have equal means.

B. X and Y are independent.

C. X and Y are identical.

D. Both variables have zero entropy.

Correct Answer: B. X and Y are independent.

Question 7

Why can a rare-event detector with high sensitivity still produce mostly false alarms?

A. Entropy is always zero for rare events.

B. The central limit theorem prevents accurate detection.

C. The low base rate allows false positives to outnumber true positives.

D. Conditional probability cannot be used for detectors.

Correct Answer: C. The low base rate allows false positives to outnumber true positives.

Question 8

Which statement about KL divergence is correct?

A. It is always symmetric.

B. It can be negative for valid distributions.

C. It is zero exactly when the two distributions agree.

D. It is a probability between zero and one.

Correct Answer: C. It is zero exactly when the two distributions agree.

Question 9

In lossless source coding, Shannon entropy primarily represents:

A. The minimum asymptotic average description length per symbol.

B. The maximum possible file size.

C. The probability of a hardware failure.

D. The number of training examples required in every model.

Correct Answer: A. The minimum asymptotic average description length per symbol.

Question 10

A model trained with cross-entropy is encouraged primarily to:

A. Make all class probabilities equal.

B. Assign high probability to outcomes supported by the target distribution.

C. Maximize variance in its predictions.

D. Ignore class frequencies.

Correct Answer: B. Assign high probability to outcomes supported by the target distribution.