Discrete Probability and Probabilistic Reasoning

Introduction

Artificial intelligence and machine learning systems operate under uncertainty. A classifier may be unsure whether an image contains a cat, a medical test may produce a false positive, and a randomized algorithm may take different execution paths on different runs. Discrete probability provides the mathematical language for representing, analyzing, and managing such uncertainty.

This chapter develops the foundations needed to reason about finite or countable outcomes. It introduces sample spaces, events, probability axioms, conditional probability, Bayes’ theorem, independence, discrete random variables, expectation, variance, and randomized algorithms. The final sections connect these ideas to AI decision-making and responsible system design.

Learning Objectives

By the end of this chapter, a student should be able to:

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

2. Apply the addition, multiplication, conditional probability, and complement rules.

3. Use Bayes’ theorem to update beliefs in light of evidence.

4. Distinguish independent events from mutually exclusive events.

5. Construct and interpret discrete random variables and probability mass functions.

6. Calculate expectation, variance, and standard deviation.

7. Explain the logic of randomized algorithms and analyze simple examples.

8. Use probabilistic reasoning in AI classification and decision-making.

9. Identify assumptions, limitations, and ethical risks in probabilistic models.

1. Probability as a Model of Uncertainty

Probability is not uncertainty itself; it is a formal model for representing uncertainty. A probability model has three principal components:

• a sample space, containing all possible outcomes;
• a collection of events, which are sets of outcomes; and
• a probability measure, assigning numerical values between 0 and 1 to events.

For a finite sample space, probabilities may be assigned by counting, empirical estimation, a physical model, or expert judgment. A model is useful only when its assumptions are appropriate to the situation.

1.1 Sample Spaces and Events

The sample space, denoted by \(\Omega\), is the set of all possible elementary outcomes of an experiment. An event \(A\) is a subset of \(\Omega\).

For a fair six-sided die,

\[

\Omega=\{1,2,3,4,5,6\}.

\]

The event \(A=\{2,4,6\}\) represents obtaining an even number. If all outcomes are equally likely, then

\[

P(A)=\frac{|A|}{|\Omega|}=\frac{3}{6}=\frac12.

\]

The notation \(|A|\) denotes the number of elements in a finite set. Equiprobability must not be assumed unless it is justified. A biased die may have unequal probabilities for its faces.

Important set operations include:

• \(A\cup B\): \(A\) or \(B\) occurs;
• \(A\cap B\): both \(A\) and \(B\) occur;
• \(A^c\): \(A\) does not occur;
• \(A\setminus B\): \(A\) occurs but \(B\) does not.

Two events are mutually exclusive if \(A\cap B=\varnothing\). They cannot occur simultaneously.

1.2 Probability Axioms

A probability measure \(P\) satisfies the Kolmogorov axioms:

1. Non-negativity: \(P(A)\geq 0\).

2. Normalization: \(P(\Omega)=1\).

3. Countable additivity: for pairwise disjoint events \(A_1,A_2,\ldots\),

\[

P\left(\bigcup_i A_i\right)=\sum_iP(A_i).

\]

For finite problems, these axioms imply several useful rules:

\[

P(A^c)=1-P(A),

\]

and, for any two events,

\[

P(A\cup B)=P(A)+P(B)-P(A\cap B).

\]

If \(A\) and \(B\) are mutually exclusive, the intersection is empty, so

\[

P(A\cup B)=P(A)+P(B).

\]

Worked Example 1: Union of Events

A data-processing job can fail because of a network error \(N\) or a software error \(S\). Suppose \(P(N)=0.08\), \(P(S)=0.05\), and \(P(N\cap S)=0.02\). The probability of at least one failure is

\[

P(N\cup S)=0.08+0.05-0.02=0.11.

\]

The intersection must be subtracted because failures caused by both errors would otherwise be counted twice.

2. Conditional Probability and Bayes’ Theorem

2.1 Conditional Probability

Conditional probability measures the likelihood of one event given that another event is known to have occurred. For \(P(B)>0\),

\[

P(A\mid B)=\frac{P(A\cap B)}{P(B)}.

\]

The condition \(B\) becomes the relevant reference set. In a finite equally likely model, this can be interpreted as

\[

P(A\mid B)=\frac{|A\cap B|}{|B|}.

\]

The multiplication rule follows directly:

\[

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

\]

It can also be written as \(P(B\mid A)P(A)\), provided the relevant conditional probabilities are defined.

2.2 Law of Total Probability

Suppose \(B_1, B_2,\ldots,B_n\) form a partition of \(\Omega\): they are pairwise disjoint and their union is \(\Omega\). Then

\[

P(A)=\sum_{i=1}^{n}P(A\mid B_i)P(B_i).

\]

This law decomposes an event according to different possible sources or groups. It is especially important in diagnostic systems and classification.

2.3 Bayes’ Theorem

Using the multiplication rule in two ways,

\[

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

\]

Therefore,

\[

P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)},

\]

where \(P(B)>0\). Here, \(P(A)\) is the prior probability, \(P(B\mid A)\) is the likelihood, \(P(B)\) is the evidence, and \(P(A\mid B)\) is the posterior probability.

When hypotheses \(A_1,\ldots,A_n\) partition the sample space,

\[

P(A_i\mid B)=\frac{P(B\mid A_i)P(A_i)}{\sum_jP(B\mid A_j)P(A_j)}.

\]

Bayes’ theorem is not merely a formula. It is a disciplined method for updating a prior belief after observing evidence.

Worked Example 2: Medical Screening

Assume a condition affects 1% of a population. A test has sensitivity \(P(T^+\mid D)=0.95\), and its false-positive rate is \(P(T^+\mid D^c)=0.05\). What is the probability that a person actually has the condition after receiving a positive result?

The evidence probability is

\[

P(T^+)=P(T^+\mid D)P(D)+P(T^+\mid D^c)P(D^c).

\]

Thus,

\[

P(T^+)=0.95(0.01)+0.05(0.99)=0.0095+0.0495=0.059.

\]

Bayes’ theorem gives

\[

P(D\mid T^+)=\frac{0.95(0.01)}{0.059}\approx0.161.

\]

The posterior probability is approximately 16.1%, not 95%. The difference arises because the condition is rare and false positives occur among the much larger healthy population. This is the base-rate effect.

3. Independence and Dependence

Events \(A\) and \(B\) are independent if

\[

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

\]

If \(P(B)>0\), an equivalent condition is

\[

P(A\mid B)=P(A).

\]

Thus, learning that \(B\) occurred does not change the probability of \(A\). Independence is a modeling assumption and should not be inferred merely because events appear unrelated.

Events are mutually exclusive when \(P(A\cap B)=0\). If both events have positive probability, mutually exclusive events cannot be independent, because \(P(A)P(B)>0\). This distinction is frequently misunderstood:

• mutually exclusive events cannot occur together;
• independent events do not influence one another.

For random variables, independence means that joint probabilities factorize. Discrete random variables \(X\) and \(Y\) are independent if

\[

P(X=x,Y=y)=P(X=x)P(Y=y)

\]

for every permitted pair \((x,y)\).

Conditional independence is weaker than unconditional independence. Variables \(X\) and \(Y\) may become independent after conditioning on a third variable \(Z\), meaning

\[

P(X,Y\mid Z)=P(X\mid Z)P(Y\mid Z).

\]

This idea is central to Bayesian networks and graphical models.

4. Discrete Random Variables

A random variable is a function that assigns a numerical value to each outcome in a sample space. It is called discrete when its possible values are finite or countably infinite.

For a discrete random variable \(X\), the probability mass function (PMF) is

\[

p_X(x)=P(X=x).

\]

A valid PMF satisfies

\[

p_X(x)\geq0\quad\text{for all }x,

\]

and

\[

\sum_xp_X(x)=1.

\]

The probability that \(X\) belongs to a set \(S\) is

\[

P(X\in S)=\sum_{x\in S}p_X(x).

\]

The cumulative distribution function (CDF) is

\[

F_X(t)=P(X\leq t)=\sum_{x\leq t}p_X(x).

\]

Unlike a PMF, which gives probability at individual values, the CDF gives accumulated probability up to a threshold.

Common Discrete Distributions

#### Bernoulli Distribution

A Bernoulli random variable represents one trial with success probability \(p\):

\[

P(X=1)=p,\qquad P(X=0)=1-p.

\]

It is appropriate for binary outcomes such as prediction correct/incorrect or transaction accepted/rejected.

#### Binomial Distribution

If \(n\) independent Bernoulli trials have common success probability \(p\), the number \(X\) of successes has distribution

\[

P(X=k)=\binom{n}{k}p^k(1-p)^{n-k},\qquad k=0,1,\ldots,n.

\]

The assumptions are fixed trial count, two outcomes per trial, constant success probability, and independence.

#### Geometric Distribution

If independent Bernoulli trials have success probability \(p\), the number \(X\) of trials until the first success has

\[

P(X=k)=(1-p)^{k-1}p,

\qquad k=1,2,\ldots.

\]

The definition must be stated carefully because some texts define a geometric variable as the number of failures before the first success.

#### Poisson Distribution

A Poisson variable with rate \(\lambda>0\) has

\[

P(X=k)=e^{-\lambda}\frac{\lambda^k}{k!},

\qquad k=0,1,2,\ldots.

\]

It is commonly used for counts of events in a fixed interval when events occur independently at a roughly constant average rate. It is a model, not a guarantee that real events satisfy these assumptions.

5. Expectation, Variance, and Uncertainty Analysis

5.1 Expected Value

For a discrete random variable \(X\), the expected value is

\[

E[X]=\sum_xxp_X(x),

\]

provided the sum is well-defined. The expectation is a probability-weighted average, not necessarily a value that can occur.

For a function \(g(X)\), the law of the unconscious statistician gives

\[

E[g(X)]=\sum_xg(x)p_X(x).

\]

Expectation is linear:

\[

E[aX+bY+c]=aE[X]+bE[Y]+c,

\]

for constants \(a,b,c\), whether or not \(X\) and \(Y\) are independent.

5.2 Variance and Standard Deviation

Variance measures dispersion around the mean:

\[

\operatorname{Var}(X)=E[(X-E[X])^2].

\]

An equivalent computational formula is

\[

\operatorname{Var}(X)=E[X^2]-(E[X])^2.

\]

The standard deviation is

\[

\sigma_X=\sqrt{\operatorname{Var}(X)}.

\]

Variance has squared units, whereas standard deviation has the same units as the random variable. For constants \(a,b\),

\[

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

\]

If \(X\) and \(Y\) are independent,

\[

\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y).

\]

Without independence, covariance must be included:

\[

\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)+2\operatorname{Cov}(X,Y).

\]

Worked Example 3: Expected Cost and Risk

A cloud job costs 2 units with probability 0.7, 5 units with probability 0.2, and 12 units with probability 0.1. Let \(C\) denote cost.

The expected cost is

\[

E[C]=2(0.7)+5(0.2)+12(0.1)=1.4+1+1.2=3.6.

\]

Next,

\[

E[C^2]=2^2(0.7)+5^2(0.2)+12^2(0.1)

=2.8+5+14.4=22.2.

\]

Therefore,

\[

\operatorname{Var}(C)=22.2-(3.6)^2=22.2-12.96=9.24.

\]

The standard deviation is approximately \(\sqrt{9.24}=3.04\) cost units. The expected cost alone hides substantial variability; both mean and dispersion matter in capacity planning.

6. Randomized Algorithms

A randomized algorithm uses random choices during execution. Its behavior, running time, or output may vary across runs even when the input is fixed. Randomization can simplify algorithms, improve average performance, distribute load, and reduce vulnerability to adversarial input arrangements.

Two broad categories are:

• A Las Vegas algorithm always returns a correct answer, but its running time is random.
• A Monte Carlo algorithm has a bounded or controlled running time, but may return an incorrect answer with small probability.

For a randomized algorithm, let \(T\) be its running time. The expected running time is

\[

E[T]=\sum_ttP(T=t),

\]

when the possible running times are discrete. An expected bound does not mean every run meets that bound. A strong analysis also considers tail probabilities, worst-case behavior, and implementation overhead.

Example: Randomized Selection of a Sample

Suppose a data stream contains \(n\) records and an algorithm must retain a uniformly random sample of one record without storing the entire stream. Reservoir sampling maintains one selected record initially. When the \(i\)-th record arrives, it replaces the current record with probability \(1/i\).

At the end, every record has probability \(1/n\) of being retained. For record \(i\), the probability of being selected when it arrives is \(1/i\), and the probability it is not replaced by each later record is

\[

\prod_{j=i+1}^{n}\left(1-\frac1j\right)

=\prod_{j=i+1}^{n}\frac{j-1}{j}=\frac{i}{n}.

\]

Thus its final selection probability is

\[

\frac1i\cdot\frac{i}{n}=\frac1n.

\]

This illustrates a probabilistic invariant: equal selection probability is preserved as the stream grows.

Randomized algorithms require reliable pseudorandom-number generators, carefully chosen seeds where reproducibility is needed, and avoidance of biased range-reduction techniques. Security-sensitive systems must use cryptographically secure randomness rather than ordinary simulation-oriented generators.

7. Probabilistic Reasoning in AI Decision-Making

AI systems often estimate probabilities rather than produce certain conclusions. A classifier may output \(P(Y=1\mid X=x)=0.8\), where \(Y\) is a class label and \(X\) represents observed features. This probability is useful only if it is interpreted correctly and reasonably calibrated.

7.1 Classification and Decision Rules

The most probable class, or maximum a posteriori (MAP) decision, is

\[

\hat y=\arg\max_yP(Y=y\mid X=x).

\]

MAP classification is not always the best decision. If the costs of errors differ, a decision should minimize expected loss. If action \(a\) has loss \(L(a,y)\) when the true state is \(y\), its conditional expected loss is

\[

R(a\mid x)=\sum_yL(a,y)P(Y=y\mid X=x).

\]

The rational action is one minimizing this quantity. For example, a fraud detector may reject a transaction only when the expected cost of accepting fraud exceeds the cost of inconveniencing a legitimate customer.

7.2 Calibration and Evaluation

A model is calibrated when, among cases assigned probability near 0.7, the event occurs approximately 70% of the time. Calibration differs from discrimination: a model can rank positive cases well but produce poorly calibrated probabilities.

Evaluation should match the decision context. Accuracy may be misleading under class imbalance. Alternatives include precision, recall, Brier score, log loss, calibration curves, and cost-sensitive measures. A probability estimate should be evaluated on data that reflect deployment conditions and should be monitored for drift.

7.3 Graphical and Causal Reasoning

Bayesian networks represent variables as nodes in a directed acyclic graph and encode conditional-independence assumptions. They can make complex joint distributions tractable, but a graph is not automatically a causal model. Causal interpretation requires additional assumptions, such as a defensible data-generating structure and appropriate treatment of confounding.

8. Illustrative Case: Risk-Based Fraud Screening

Background

Consider a fictional online payment platform that screens transactions for possible fraud. Fraud is rare, but fraudulent transactions can cause financial loss and regulatory exposure. Legitimate customers may be inconvenienced if transactions are incorrectly blocked.

Problem

A model flags a transaction when its estimated fraud probability exceeds a threshold. The organization must choose a threshold that balances fraud losses against customer disruption.

Analysis

Suppose a transaction has posterior fraud probability 0.04. Blocking a legitimate transaction costs 2 units in service and lost goodwill. Allowing a fraudulent transaction costs 30 units. If the action is block, expected loss is

\[

0.96(2)=1.92,

\]

assuming blocking a fraudulent transaction has negligible additional loss. If the action is allow, expected loss is

\[

0.04(30)=1.20.

\]

Under these stated costs, allowing the transaction has lower expected loss. The threshold is not automatically 0.5; it depends on error costs. With false-negative cost \(C_{FN}\) and false-positive cost \(C_{FP}\), blocking becomes preferable when

\[

(1-p)C_{FP}<pC_{FN},

\]

or equivalently,

\[

p>\frac{C_{FP}}{C_{FP}+C_{FN}},

\]

under the simplified assumption that correct decisions have zero loss.

Approach and Outcome

The platform uses calibrated probabilities, separate review for borderline cases, and periodic monitoring. It evaluates performance by customer segment and transaction type rather than relying only on overall accuracy. Human investigators review a sample of decisions, and users receive an appeal mechanism.

Learning Points

1. A posterior probability is not itself a decision; actions require a loss model.

2. Rare events make base rates essential.

3. Calibration and drift monitoring are operational requirements.

4. Thresholds can create unequal burdens across groups if data or error costs differ.

5. Human review and appeal processes improve governance in high-impact applications.

9. Limitations, Ethics, and Best Practices

Probability models depend on assumptions, data quality, and the relevance of past observations to future cases. A model may be mathematically correct but operationally misleading if the sample is biased, labels are unreliable, or the environment changes.

Important risks include:

• base-rate neglect, when prior prevalence is ignored;
• data leakage, when information unavailable at decision time enters training;
• overconfidence, when estimated probabilities are poorly calibrated;
• selection bias, when observed data do not represent the affected population;
• feedback loops, when predictions influence the data later used to retrain the model;
• fairness harms, when errors or thresholds differ systematically across groups;
• privacy risks, when probabilistic inference reveals sensitive attributes.

Professional best practices include clearly stating assumptions, separating training and evaluation data, reporting uncertainty and confidence appropriately, testing subgroup performance, calibrating probabilities, documenting data provenance, monitoring distribution shift, and retaining human accountability for consequential decisions. Random seeds and model versions should be recorded for reproducibility, while sensitive data and randomness sources should be protected.

Contemporary AI systems increasingly combine probabilistic models with deep learning, Bayesian optimization, uncertainty estimation, and conformal prediction. These methods can provide useful prediction sets or uncertainty scores, but their guarantees depend on assumptions such as exchangeability and can weaken under distribution shift. Probabilistic outputs should therefore support—not replace—domain expertise and governance.

Chapter Summary

Discrete probability models uncertainty using sample spaces, events, and probability measures. The complement, union, and multiplication rules allow probabilities to be combined systematically. Conditional probability changes the reference information, while Bayes’ theorem updates prior beliefs using evidence and is especially important when base rates are unequal.

Independence means that the occurrence of one event does not change the probability of another; it is distinct from mutual exclusivity. Discrete random variables assign numerical values to outcomes and are described by probability mass functions. Their expected values quantify average outcomes, while variance and standard deviation describe dispersion.

Randomized algorithms use probability to improve efficiency, simplicity, or robustness. Their analyses must distinguish guaranteed correctness from probabilistic correctness and expected performance from worst-case performance. In AI, posterior probabilities support classification and decision-making, but rational actions require an explicit loss model. Calibration, data quality, fairness, privacy, monitoring, and accountability are essential when probabilistic outputs affect people.

Key Terms

Sample space: Set of all possible outcomes of an experiment.

Elementary outcome: A single outcome in a sample space.

Event: A subset of the sample space.

Probability measure: Function assigning probabilities to events.

Conditional probability: Probability of an event given another event.

Bayes’ theorem: Rule for updating a prior probability using evidence.

Prior probability: Belief assigned before observing new evidence.

Likelihood: Probability of observed evidence under a hypothesis.

Posterior probability: Updated probability after observing evidence.

Independence: Condition in which one event does not affect another.

Mutually exclusive events: Events that cannot occur together.

Random variable: Function assigning numerical values to outcomes.

Probability mass function: Function giving probabilities of discrete values.

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

Variance: Expected squared deviation from the mean.

Standard deviation: Square root of variance.

Las Vegas algorithm: Randomized algorithm that always returns a correct result.

Monte Carlo algorithm: Randomized algorithm with a probability of error.

Calibration: Agreement between predicted probabilities and observed frequencies.

Expected loss: Probability-weighted cost of an action’s possible outcomes.

Review Questions

Short Answer Questions

1. What is the difference between a sample space and an event?

2. State Bayes’ theorem and identify its prior, likelihood, evidence, and posterior components.

3. Why are mutually exclusive events with positive probabilities not independent?

4. What is the difference between a probability mass function and a cumulative distribution function?

5. Why can expected value alone be insufficient for uncertainty analysis?

Long Answer Questions

1. Explain the probability axioms and derive the complement and union rules.

2. Compare conditional probability, independence, and conditional independence, using examples.

3. Describe Bernoulli, binomial, geometric, and Poisson distributions, including their assumptions.

4. Explain the distinction between Las Vegas and Monte Carlo randomized algorithms.

5. Discuss why calibrated probabilities and cost-sensitive decisions are important in AI systems.

Analytical / Application Questions

1. A disease affects 2% of a population. A test has sensitivity 90% and false-positive rate 4%. Calculate the probability of disease given a positive test and interpret the result.

2. A model assigns fraud probability 0.08. Blocking a legitimate transaction costs 3 units, while allowing fraud costs 25 units. Under the simplified zero-cost correct-decision model, should the transaction be blocked? Show the expected-loss comparison.

3. A discrete random variable takes values 0, 1, and 3 with probabilities 0.5, 0.3, and 0.2. Calculate its expectation, variance, and standard deviation, and explain what the results mean.

Multiple Choice Questions with Answers

Question 1

A fair six-sided die is rolled. What is the probability of obtaining an even number?

A. 1/6

B. 1/3

C. 1/2

D. 2/3

Correct Answer: C. 1/2

Question 2

If P(A)=0.4, P(B)=0.3, and P(A∩B)=0.1, what is P(A∪B)?

A. 0.6

B. 0.7

C. 0.8

D. 0.12

Correct Answer: A. 0.6

Question 3

Which expression defines conditional probability P(A|B), assuming P(B)>0?

A. P(A)/P(B)

B. P(A∩B)/P(B)

C. P(A∩B)/P(A)

D. P(A)+P(B)

Correct Answer: B. P(A∩B)/P(B)

Question 4

A condition has prevalence 1%, sensitivity 95%, and false-positive rate 5%. What is approximately P(condition | positive test)?

A. 5.0%

B. 16.1%

C. 50.0%

D. 95.0%

Correct Answer: B. 16.1%

Question 5

Which statement correctly characterizes independent events A and B?

A. They cannot occur together.

B. P(A∩B)=0.

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

D. P(A)=P(B).

Correct Answer: C. P(A∩B)=P(A)P(B).

Question 6

A Bernoulli random variable with success probability p takes which values?

A. Only p and 1-p

B. 0 and 1

C. Any integer from 0 to n

D. All nonnegative real numbers

Correct Answer: B. 0 and 1

Question 7

For a discrete random variable X, which formula gives its expected value?

A. Σ pX(x)

B. Σ x pX(x)

C. Σ x²

D. max(X)-min(X)

Correct Answer: B. Σ x pX(x)

Question 8

If E[X]=4 and E[X²]=20, what is Var(X)?

A. 4

B. 12

C. 16

D. 36

Correct Answer: A. 4

Question 9

Which randomized algorithm always returns a correct answer but may have random running time?

A. Monte Carlo

B. Las Vegas

C. Greedy

D. Deterministic

Correct Answer: B. Las Vegas

Question 10

If false-positive cost is 2 and false-negative cost is 8, under the simplified decision model, blocking is preferred when fraud probability p is greater than which threshold?

A. 0.20

B. 0.25

C. 0.50

D. 0.80

Correct Answer: B. 0.25