Practice Problems in Probabilistic
Modeling and Analysis
Kazi Ashrafuzzaman
STA 351, Department of CSE, CU
Each problem is designed to test your ability to carry out
analysis upon fomulating appropriate models for systems or
processes using probabilistic tools.
Show reasoning clearly. Analytical justification is valued
over numeric answers.
1. A load balancer distributes incoming requests to n = 4
servers. Each incoming request is assigned independently
and uniformly at random to one of the servers.
(a) Model the number of requests received by a particular
server after 100 requests as a random variable, and
specify its PMF.
(b) Approximate (using the normal approximation to the
binomial if convenient) the probability that this server
receives between 20 and 35 requests inclusive.
(c) Interpret this result in the context of system fairness.
1
2. A cloud provider’s datacenter records the latency (in mil-
liseconds) for a certain API request. Suppose the latency
X follows an exponential distribution with mean 50 ms.
(a) Write down the PDF and CDF of X.
(b) Compute the probability that latency exceeds 100 ms.
(c) Suppose an optimization is applied that reduces the
mean latency by 30%. By what factor does the prob-
ability of latency exceeding 100 ms decrease?
3. Let X1 , X2 , . . . , X10 be i.i.d. random variables representing
the number of cache hits (out of 5 possible accesses) for 10
different user sessions. Assume each access is a hit with
probability p = 0.8.
(a) Find the moment generating function (MGF) of the
P10
total number of hits S = i=1 Xi .
(b) Using the MGF, derive the mean and variance of S.
(c) Explain briefly how MGFs could be useful in analyzing
algorithmic runtime distributions.
4. A web server handles an average of µ = 2000 requests per
second with standard deviation σ = 200. Let X denote the
number of requests handled in one second.
(a) Use Chebyshev’s inequality to bound Pr(|X − 2000| ≥
400).
(b) Interpret the bound in operational terms (e.g., perfor-
mance guarantee).
(c) Compare the Chebyshev bound to what a normal ap-
proximation might predict.
2
5. A web crawler navigates among three types of websites:
S1 = tech blogs, S2 = news sites, S3 = forums.
From empirical data, the transition probabilities are as fol-
lows:
0.4 0.4 0.2
P = 0.2 0.6 0.2 .
0.3 0.3 0.4
(a) Verify that P is a valid stochastic matrix.
(b) Determine the stationary distribution π.
(c) Interpret π as the long-run fraction of time the crawler
spends on each type of site.
(d) Suppose visiting a news site consumes 3x the band-
width of visiting a tech blog, while a forum visit uses
2x. Compute the expected relative bandwidth usage
in steady state.
6. When a network packet is transmitted, it may need to be
resent several times before being acknowledged.
Let the number of transmissions N be a discrete random
variable with
P (N = k) = (1 − p)k−1 p, k = 1, 2, 3, . . .
i.e. a geometric distribution with success probability p =
0.3.
Each transmission takes an independent random time Ti (in
milliseconds), where
Ti ∼ Uniform(5, 10),
3
independent of N . The total delay for the packet to be
successfully sent is
XN
D= Ti .
i=1
(a) Explain briefly why D is a mixture of discrete and
continuous random variables.
(b) Compute E[Ti ] and E[D].
(c) What is the probability that the packet succeeds on
the first attempt and the delay is less than 8 ms?
(d) If a student simulated 1000 packets, explain how the
histogram of D might look qualitatively (e.g., would it
be smooth, discrete, skewed?).
7. A small cloud service processes incoming requests that can
be of two types:
Type A: simple queries (probability 0.7), Type B: complex a
Let the random variable Y denote the processing time (in
seconds) of a single request.
Y | Type A ∼ Uniform(0.2, 0.6),
Y | Type B ∼ Exponential(λ = 2).
(a) Write an expression for the overall (marginal) PDF
fY (y) in terms of the conditional PDFs.
(b) Compute P (Y > 0.5).
(c) Compute the expected processing time E[Y ].
(d) Discuss briefly (one or two sentences) how the heavier
tail of the exponential part affects the overall variabil-
ity in request times.
4
8. A small web proxy cache can hold one webpage at a time.
When a user requests a page:
• If the requested page is already in cache, it is a cache
hit.
• If not, it is a cache miss, and the requested page
replaces the one in cache.
Suppose that users request only two popular pages: A and
B. At each request, the probability that the next requested
page is A is 0.6, and that it is B is 0.4, independent of the
past.
Define the system state as the page currently in the cache.
The transition probabilities between states A (cache stores
page A) and B (cache stores page B) are:
0.6 0.4
P = .
0.6 0.4
(a) Interpret each row of the transition matrix and explain
what they represent.
(b) Find the stationary distribution π = (πA , πB ).
(c) In the long run, what fraction of requests will be cache
hits?
(d) Suppose that caching page A uses twice as much mem-
ory as caching page B. Using the steady-state distri-
bution, find the expected proportion of memory used
(in units relative to the size of B).
9. A smartphone CPU operates in three power states:
S1 = Idle, S2 = Active, S3 = Sleep.
5
The system is observed at discrete time intervals of 1 sec-
ond. From empirical measurement, the transition probabil-
ity matrix is:
0.6 0.3 0.1
P = 0.2 0.7 0.1 .
0.4 0.4 0.2
(a) Verify that P is a valid stochastic matrix.
(b) Compute the stationary distribution π = (π1 , π2 , π3 ).
(c) Interpret π in the context of energy consumption (e.g.,
expected long-run fraction of time spent in each power
state).
(d) Suppose the power consumption rates (in watts) for
the states are 0.1, 1.0, and 0.02, respectively. Compute
the expected steady-state power consumption.
(e) If the system starts in the Active state, find the prob-
ability that it is in the Sleep state after two seconds.