Mathematical Foundations

Chapter 11
Probability and Stochastic Reasoning

Bachelors Program in Computer Applications
Mathematical Foundations • Bachelor

Probability and Stochastic Reasoning

Introduction

Probability is the mathematical language used to describe uncertainty. Computer applications routinely operate with incomplete information: a network may fail, a transaction may be fraudulent, a sensor may be inaccurate, or a machine-learning model may assign different likelihoods to competing predictions. Probability provides a disciplined framework for representing such uncertainty, updating beliefs when evidence arrives, and making decisions under risk.

A deterministic model produces the same output whenever its inputs and conditions are fixed. A stochastic model, by contrast, includes randomness or uncertainty. Stochastic reasoning does not mean that outcomes are completely unpredictable. It means that uncertainty is represented systematically through events, random variables, distributions, and dependence relationships.

This chapter develops the foundations needed to apply probability to reliability, risk assessment, prediction, simulation, and probabilistic computing.

Learning Objectives

After studying this chapter, you should be able to:

Define sample spaces, events, probability measures, and conditional probability.
Apply the probability axioms, addition rules, multiplication rules, and Bayes’ theorem.
Distinguish mutually exclusive events from independent events.
Describe discrete and continuous random variables using probability distributions.
Calculate and interpret expectation, variance, standard deviation, and covariance.
Use common distributions, including Bernoulli, binomial, Poisson, and normal distributions.
Model reliability and risk using probability trees, conditional probabilities, and expected values.
Recognize assumptions, limitations, ethical concerns, and implementation issues in probabilistic systems.

1. Sample Spaces and Events

A random experiment is a process whose outcome cannot be known with certainty in advance, although the possible outcomes can be specified. Examples include selecting a database record at random, observing whether a server request fails, and measuring the response time of a web service.

The sample space, denoted by Ω, is the set of all possible outcomes. An event is a subset of the sample space. If a die is rolled, Ω = {1,2,3,4,5,6}. The event “an even number occurs” is A = {2,4,6}.

Events may be:

Simple, containing one outcome.
Compound, containing several outcomes.
Certain, equal to the entire sample space Ω.
Impossible, represented by the empty set ∅.
Complementary, where A^c contains all outcomes not in A.
Mutually exclusive, where two events cannot occur together, so A ∩ B = ∅.

For a finite sample space with equally likely outcomes,

P(A) = \frac{|A|}{|Ω|}

where |A| is the number of outcomes in event A and |Ω| is the number of outcomes in the sample space. This formula is valid only when outcomes are equally likely.

Probability Axioms

A probability function P assigns a number to each event and obeys three axioms:

Non-negativity:

P(A) ≥ 0

Normalization:

P(Ω) = 1

Countable additivity: for mutually exclusive events A₁, A₂, ...,

P(A₁ ∪ A₂ ∪ ...) = P(A₁) + P(A₂) + ...

Important consequences include:

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

and, for any two events,

P(A ∪ B) = P(A) + P(B) - P(A ∩ B)

The intersection term is subtracted because outcomes common to both events would otherwise be counted twice.

Worked Example 1: Addition Rule

A university system records 500 login attempts. Of these, 80 involve a password reset, 60 originate outside the country, and 20 satisfy both conditions. If one attempt is selected at random, the probability that it involves a password reset or originates outside the country is

P(R ∪ O) = P(R) + P(O) - P(R ∩ O)

Thus,

P(R ∪ O) = \frac{80}{500} + \frac{60}{500} - \frac{20}{500} = \frac{120}{500} = 0.24

The probability is 0.24, or 24%.

2. Conditional Probability and Dependence

Often, probability must be calculated after some information is known. The conditional probability of A given B, written P(A|B), is

P(A|B) = \frac{P(A ∩ B)}{P(B)}, \quad P(B) > 0

The condition P(B) > 0 is necessary because division by zero is undefined. Conditional probability restricts attention to cases in which B occurred.

Rearranging gives the multiplication rule:

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

Two events are independent if knowledge that one occurred does not change the probability of the other:

P(A|B) = P(A)

Equivalently, for events with defined probabilities,

P(A ∩ B) = P(A)P(B)

Independence is not the same as mutual exclusivity. If two events are mutually exclusive and both have positive probability, they cannot be independent: occurrence of one makes the other impossible.

Law of Total Probability

Suppose B₁, B₂, ..., B_n form a partition of the sample space. This means that they are mutually exclusive and together cover Ω. Then

P(A) = ∑_i=1ⁿ P(A|B_i)P(B_i)

This law is useful when an event can arise through several distinct scenarios.

Bayes’ Theorem

Bayes’ theorem reverses a conditional probability:

P(B_j|A) = \frac{P(A|B_j)P(B_j)}{∑_i=1ⁿP(A|B_i)P(B_i)}

Here, P(B_j) is the prior probability, P(A|B_j) is the likelihood of observing evidence A under condition B_j, and P(B_j|A) is the posterior probability after observing A.

Worked Example 2: Diagnostic Classification

Suppose 2% of network transactions are fraudulent. A screening model flags 95% of fraudulent transactions and incorrectly flags 5% of legitimate transactions. Let F mean fraud and + mean a positive flag.

Given:

P(F)=0.02
P(+|F)=0.95
P(+|F^c)=0.05
P(F^c)=0.98

First calculate the total probability of a positive flag:

P(+) = P(+|F)P(F) + P(+|F^c)P(F^c)

P(+) = (0.95)(0.02) + (0.05)(0.98) = 0.019 + 0.049 = 0.068

Bayes’ theorem gives:

P(F|+) = \frac{(0.95)(0.02)}{0.068} ≈ 0.2794

Therefore, a flagged transaction has approximately a 27.94% probability of being fraudulent. The result illustrates the base-rate effect: even a relatively accurate detector can produce many false positives when the underlying event is uncommon.

3. Counting, Trees, and Simulation

Counting methods are useful when all outcomes are equally likely. The number of ordered arrangements of n distinct objects is

n! = n(n-1)(n-2)⋯1

The number of ways to choose r objects from n without regard to order is

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

The binomial coefficient is central to binomial probability calculations.

A probability tree displays sequential events and their conditional probabilities. Probabilities along a path are multiplied; probabilities of alternative paths are added. Trees are especially useful for reliability diagnosis, authentication workflows, and multi-stage decisions.

When exact calculation is difficult, Monte Carlo simulation estimates a probability by repeating a random experiment many times. If an event occurs k times in N independent simulation runs, its estimated probability is

\hat{p} = \frac{k}{N}

The estimate becomes more stable as N increases, but simulation error never disappears completely. Simulation must also use a valid probability model and an appropriate random-number generator.

4. Random Variables and Probability Distributions

A random variable is a function that assigns a numerical value to each outcome. It is commonly denoted by X. A random variable may be:

Discrete, taking a finite or countably infinite set of values, such as the number of failed requests.
Continuous, taking values over intervals, such as response time.

A discrete random variable is described by a probability mass function (PMF):

p_X(x) = P(X=x)

The PMF must satisfy

p_X(x) ≥ 0, \qquad ∑_x p_X(x)=1

A continuous random variable is described by a probability density function (PDF) f_X(x). Probabilities are obtained by integration:

P(a ≤ X ≤ b) = ∫_a^b f_X(x)dx

A density itself is not a probability at a point. For a continuous variable, P(X=x)=0; probabilities correspond to areas over intervals.

The cumulative distribution function (CDF) is

F_X(x) = P(X ≤ x)

For a continuous variable, if the density is differentiable, f_X(x)=F'_X(x).

Expectation and Variance

The expected value, or mean, of a discrete random variable is

E[X] = ∑_x x p_X(x)

For a continuous variable,

E[X] = ∫_-∞^∞ x f_X(x)dx

Expectation is a long-run average, not necessarily an outcome that will actually occur. For a function g(X),

E[g(X)] = ∑_x g(x)p_X(x)

for a discrete variable, with the corresponding integral for a continuous variable.

Variance measures dispersion around the mean:

Var(X) = E[(X-μ)²] = E[X²] - μ²

where μ=E[X]. The standard deviation is

σ = √Var(X)

Variance has squared units, whereas standard deviation has the same units as X. For constants a and b,

E[aX+b] = aE[X]+b

and

Var(aX+b)=a²Var(X)

The constant b shifts the mean but does not affect variance; scaling by a changes variance by a².

Covariance and Correlation

For random variables X and Y, covariance is

Cov(X,Y)=E[(X-E[X])(Y-E[Y])]

Equivalently,

Cov(X,Y)=E[XY]-E[X]E[Y]

Correlation standardizes covariance:

ρ_X,Y=\frac{Cov(X,Y)}{σ_Xσ_Y}

provided both standard deviations are nonzero. Correlation lies between −1 and 1. Zero correlation does not generally imply independence, although independence does imply zero covariance when the relevant expectations exist.

5. Standard Probability Distributions

Bernoulli Distribution

A Bernoulli random variable represents one trial with success probability p and failure probability 1-p. If X∈{0,1}, then

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

Its mean and variance are

E[X]=p, \qquad Var(X)=p(1-p)

Examples include whether a login fails or whether a packet is lost.

Binomial Distribution

If n independent Bernoulli trials have the same success probability p, the number of successes X follows a binomial distribution:

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

Its mean and variance are

E[X]=np, \qquad Var(X)=np(1-p)

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

Poisson Distribution

The Poisson distribution models the number of events in a fixed interval when events occur independently at an approximately constant average rate λ.

P(X=k)=\frac{e^-λλ^k}{k!}, \quad k=0,1,2,...

For a Poisson variable,

E[X]=Var(X)=λ

The model is appropriate for some request-arrival, defect, or failure counts, but not when events strongly influence one another or the rate changes substantially over the interval.

Uniform Distribution

If every value in the interval [a,b] is equally likely, the continuous uniform density is

f_X(x)=\frac{1}{b-a}, \quad a≤x≤b

Its mean and variance are

E[X]=\frac{a+b}{2}, \qquad Var(X)=\frac{(b-a)²}{12}

Normal Distribution

A normal random variable with mean μ and variance σ² has density

f_X(x)=\frac{1}{σ√{2π}}e^{-\frac{(x-μ)²}{2σ²}}, \quad σ>0

The standardized variable is

Z=\frac{X-μ}{σ}

which has the standard normal distribution. The normal model is useful for measurement errors and aggregated effects, but it should not be applied automatically to bounded, highly skewed, or count data.

Exponential Distribution and Reliability

The exponential distribution models a nonnegative waiting time with rate λ>0:

f_X(x)=λe^-λx, \quad x≥0

Its survival probability is

P(X>t)=e^-λt

and its mean is 1/λ. A notable property is memorylessness:

P(X>s+t|X>s)=P(X>t)

This assumption means that the future waiting time does not depend on how long the system has already operated. Real components may exhibit wear-out, so the exponential model must be validated rather than assumed.

6. Reliability and Risk Analysis

Reliability is the probability that a system performs its required function for a specified time under stated conditions. If a component operates successfully through time t with probability R(t), then R(t) is its reliability function.

For independent components in a series system, every component must work:

R_series=∏_i=1ⁿR_i

For independent components in a parallel system, at least one must work:

R_parallel=1-∏_i=1ⁿ(1-R_i)

For two independent components with reliabilities 0.98 and 0.95, the series reliability is

R_series=(0.98)(0.95)=0.931

The parallel reliability is

R_parallel=1-(0.02)(0.05)=0.999

These calculations assume independence and correctly identified system structure. Common-cause failures, shared power supplies, software defects, and environmental conditions can invalidate the simple formulas.

Risk combines uncertain outcomes with their consequences. A simple expected-loss model is

E[L]=∑_i=1ⁿP(S_i)L_i

where S_i is scenario i, P(S_i) is its probability, and L_i is its loss. Expected loss supports comparison, but it does not capture risk appetite, catastrophic tail events, or distributional fairness by itself.

7. A Detailed Applied Case: Reliability of an Online Payment Service

Background

The following is an illustrative case. An online payment service uses two independent application servers in parallel so that either server can process a request. Each server has reliability 0.97 during a defined operating period. A shared database has reliability 0.99, and the payment service cannot function if the database fails.

Problem

Determine the reliability of the complete service and estimate the expected loss if a service outage costs ₹200,000 and no outage costs nothing.

Analysis

The application layer works if at least one server works:

R_app=1-(1-0.97)²=1-(0.03)²=0.9991

The complete service requires both the application layer and database. Assuming independence between these subsystems,

R_service=R_appR_db=(0.9991)(0.99)=0.989109

Thus, the outage probability is

P(outage)=1-0.989109=0.010891

The expected loss per operating period is

E[L]=(0.010891)(₹200,000)=₹2,178.20

Approach and Possible Solution

The organization might compare the cost of improving database reliability with the expected reduction in loss. For example, replacing the database design with a highly available configuration could reduce database failure probability, but the investment should be evaluated against expected loss, service-level commitments, customer impact, and the possibility of correlated failures.

Outcome and Learning Points

The parallel servers greatly improve application-layer reliability, but the shared database remains a bottleneck. Redundancy is effective only when failures are sufficiently independent. The case also shows why system-level analysis is necessary: improving one component may have little effect if another component dominates total risk.

8. Probabilistic Computing, Prediction, and AI

Probabilistic computing represents uncertain inputs, hidden states, or outputs with probability distributions. Examples include:

Bayesian spam filtering.
Probabilistic data structures and randomized algorithms.
Fault detection in distributed systems.
Weather and demand forecasting.
Speech recognition and natural-language processing.
Bayesian networks, which represent conditional dependencies among variables.
Markov models, in which the next state depends probabilistically on the current state.

A prediction should ideally provide both a point estimate and uncertainty information. A model that predicts a 70% probability of failure should be assessed for calibration: among cases assigned probabilities near 0.70, failure should occur approximately 70% of the time over a sufficiently large and comparable population.

Randomness in algorithms must be controlled carefully. Reproducible experiments require recorded seeds, versioned data, documented preprocessing, and explicit treatment of train-test leakage. In security applications, cryptographic randomness must come from a secure source rather than an ordinary pseudorandom generator.

9. Assumptions, Limitations, and Ethical Governance

Probability calculations are only as reliable as the model and data supporting them. Important limitations include:

Model uncertainty: the selected distribution or dependence structure may be wrong.
Parameter uncertainty: estimated probabilities may be imprecise.
Selection bias: historical data may not represent future users or conditions.
Dependence: failures, transactions, or observations may be correlated.
Nonstationarity: rates and relationships may change over time.
Small samples: rare-event estimates can be unstable.
Simulation error: finite simulation runs produce approximation error.

In professional systems, probability should not be presented as certainty. A risk score can affect credit, employment, insurance, healthcare, or access to services. Governance should therefore include transparency, validation, monitoring for drift, privacy protection, human review for high-impact decisions, and documentation of assumptions.

Fairness analysis must examine whether error rates differ systematically across relevant groups. Removing a sensitive attribute does not necessarily remove discriminatory effects because other variables may act as proxies. Ethical deployment requires both technical evaluation and institutional accountability.

10. Best Practices for Probabilistic Analysis

Define the random experiment, population, time period, and outcome precisely.
State whether probabilities are theoretical, empirical, subjective, or simulated.
Separate prior information from new evidence when applying Bayes’ theorem.
Test independence assumptions rather than treating them as automatic.
Check that probabilities lie between 0 and 1 and that a distribution sums or integrates to 1.
Preserve units: variance has squared units, while standard deviation has original units.
Report uncertainty, sensitivity, and relevant alternative models.
Validate predictions using data not used for fitting.
Monitor real-world performance because probability models can degrade.
Communicate both expected outcomes and low-probability, high-impact outcomes.

Chapter Summary

Probability formalizes uncertainty through sample spaces, events, and probability measures. The axioms lead to complement, addition, and multiplication rules. Conditional probability describes uncertainty after information is known, while Bayes’ theorem updates prior beliefs using evidence. Independence is a special structural assumption and must not be confused with mutual exclusivity.

Random variables translate outcomes into numerical quantities. Their distributions may be discrete or continuous and are summarized using expectation, variance, standard deviation, covariance, and correlation. Bernoulli, binomial, Poisson, uniform, normal, and exponential distributions support common computing and reliability applications, provided their assumptions are appropriate.

Reliability models combine component probabilities according to system structure, while expected loss connects probability with consequences. Monte Carlo simulation provides approximate solutions when analytical methods are difficult. In probabilistic computing and AI, calibrated uncertainty, reproducibility, model validation, fairness, privacy, and accountability are as important as numerical accuracy.

Key Terms

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

Event: A subset of the sample space.

Probability: A number from 0 to 1 representing the likelihood of an event.

Complement: The event that an event does not occur.

Mutually exclusive events: Events that cannot occur together.

Conditional probability: Probability of one event given that another event has occurred.

Independence: A relationship in which occurrence of one event does not alter the probability of another.

Bayes’ theorem: A rule for updating a probability using observed evidence.

Prior probability: Probability assigned before new evidence is considered.

Posterior probability: Updated probability after evidence is considered.

Random variable: A numerical function defined on outcomes of a random experiment.

PMF: Probability mass function for a discrete random variable.

PDF: Probability density function for a continuous random variable.

CDF: Cumulative distribution function giving P(X≤x).

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

Variance: Expected squared deviation from the mean.

Covariance: Measure of joint variation between two random variables.

Reliability: Probability that a system performs its required function for a specified period.

Monte Carlo simulation: Repeated random sampling used to estimate probabilities or quantities.

Calibration: Agreement between predicted probabilities and observed frequencies.

Review Questions

Short Answer Questions

What is the difference between a sample space and an event?
State the three probability axioms.
Define conditional probability and specify its condition of applicability.
Why are mutually exclusive events with positive probabilities not independent?
Distinguish a probability mass function from a probability density function.

Long Answer Questions

Explain Bayes’ theorem, including prior probability, likelihood, evidence, and posterior probability. Illustrate the explanation with a computing-related example.
Compare Bernoulli, binomial, Poisson, normal, and exponential distributions, including their assumptions and typical applications.
Derive the reliability expressions for independent series and parallel systems and discuss circumstances in which the formulas may fail.
Explain expectation, variance, standard deviation, covariance, and correlation, including the interpretation and units of each.
Discuss the limitations and ethical governance requirements of probabilistic prediction systems used in high-impact decisions.

Analytical / Application Questions

A fraud detector flags 4% of legitimate transactions and detects 90% of fraudulent transactions. If 1% of transactions are fraudulent, calculate the probability that a flagged transaction is actually fraudulent.
A service requires a database and at least one of two independent application servers. The database reliability is 0.995 and each server reliability is 0.96. Calculate the service reliability and explain the dominant risk source.
A simulation of 50,000 independent trials observes 425 failures. Estimate the failure probability and explain at least two reasons why the estimate may differ from the true probability.

Multiple Choice Questions with Answers

Question 1

If P(A)=0.30, P(B)=0.40, and P(A ∩ B)=0.10, what is P(A ∪ B)?

A. 0.10

B. 0.60

C. 0.70

D. 0.80

Correct Answer: B. 0.60

Question 2

Which condition defines independence of events A and B?

A. P(A ∩ B)=0

B. P(A|B)=1

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

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

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

Question 3

A disease has prevalence 0.02. A test has sensitivity 0.95 and a false-positive rate of 0.05. What is approximately P(disease | positive)?

A. 0.019

B. 0.050

C. 0.279

D. 0.950

Correct Answer: C. 0.279

Question 4

A Bernoulli random variable has success probability p=0.2. What is its variance?

A. 0.04

B. 0.16

C. 0.20

D. 0.80

Correct Answer: B. 0.16

Question 5

If X has a Poisson distribution with rate λ=4, what is Var(X)?

A. 1

B. 2

C. 4

D. 16

Correct Answer: C. 4

Question 6

Two independent components have reliabilities 0.90 and 0.80 and are connected in series. What is the system reliability?

A. 0.08

B. 0.18

C. 0.72

D. 0.98

Correct Answer: C. 0.72

Question 7

For a continuous random variable, which statement is correct?

A. P(X=x)=1 for every x

B. P(X=x)=0 for an individual point x

C. Its PDF must be at most 0.01

D. Its CDF is always constant

Correct Answer: B. P(X=x)=0 for an individual point x

Question 8

If E[X]=5 and Var(X)=4, what are E[2X+3] and Var(2X+3)?

A. 10 and 7

B. 13 and 8

C. 13 and 16

D. 16 and 16

Correct Answer: C. 13 and 16

Question 9

A Monte Carlo estimate based on k successes in N trials is calculated as:

A. N/k

B. k+N

C. k−N

D. k/N

Correct Answer: D. k/N

Question 10

Which statement about correlation is correct?

A. Zero correlation always implies independence

B. Independence implies zero covariance when moments exist

C. Correlation can exceed 1 for strongly related variables

D. Correlation has squared units

Correct Answer: B. Independence implies zero covariance when moments exist

Mathematical Foundations
Chapter 11 of 15

Chapter 11 Probability and Stochastic Reasoning

Probability and Stochastic Reasoning

Introduction

Learning Objectives

1. Sample Spaces and Events

Probability Axioms

Worked Example 1: Addition Rule

2. Conditional Probability and Dependence

Law of Total Probability

Bayes’ Theorem

Worked Example 2: Diagnostic Classification

3. Counting, Trees, and Simulation

4. Random Variables and Probability Distributions

Expectation and Variance

Covariance and Correlation

5. Standard Probability Distributions

Bernoulli Distribution

Binomial Distribution

Poisson Distribution

Uniform Distribution

Normal Distribution

Exponential Distribution and Reliability

6. Reliability and Risk Analysis

7. A Detailed Applied Case: Reliability of an Online Payment Service

Background

Problem

Analysis

Approach and Possible Solution

Outcome and Learning Points

8. Probabilistic Computing, Prediction, and AI

9. Assumptions, Limitations, and Ethical Governance

10. Best Practices for Probabilistic Analysis

Chapter Summary

Key Terms

Review Questions

Short Answer Questions

Long Answer Questions

Analytical / Application Questions

Multiple Choice Questions with Answers

Question 1

Question 2

Question 3

Question 4

Question 5

Question 6

Question 7

Question 8

Question 9

Question 10

Chapter 11
Probability and Stochastic Reasoning