— PROJECT 1 —
MATH 368, S2 2023
Dr. A. Alpers
Deadline: 17/04/2023
Task 1. [5+5 points]
Your group has a special pdf πg for generating a discrete random variable X with values in {1, 2, 3}.
This πg = (π(1), π(2), π(3)) with π(i) = Pr(X = i), i = 1, 2, 3, is obtained as follows: Subtract
your group number g from 559 and express the result as 3-digit decimal number a1 ·102+a2 ·10+a3
with a1, a2, a3 ∈ {0, . . . , 9}. Then,
π(i) := ai/(a1 + a2 + a3), i = 1, 2, 3.
(a) Give a Matlab implementation of a function GenerateRandomNumbers(n,g) that takes a
number n and your group number g as input and returns n random numbers from {1, 2, 3}
following your pdf πg. Your function is not allowed to use any built-in number generators
except for rand.
(b) Plot a histogram of nTrials=10^6 random numbers generated by your function
GenerateRandomNumbers (using your πg). The bins should be centered at 1, 2, and 3.
Task 2. [5+5 points]
Consider the following problem (a version of the so-called Monty Hall problem). A car is randomly
placed behind one of the three doors #1, #2, #3 following your special pdf πg from Task 1
(i.e., the probability that the car is placed behind door #i is π(i), i = 1, 2, 3). The contestant
chooses door #1. If the car is behind door #1, the host chooses door #2 with probability q and
door #3 with probability 1 − q. If the car is not behind door #1, then the host opens whichever
of doors #2 or #3 that the car is NOT behind. The contestant makes now a final choice, sticking
to door #1 or switching to the unopened door. The contestant wins if the car is behind the final
chosen door.
Several strategies are available to the contestant. Relevant are here the following three strategies:
ˆ Strategy 1: Stick always to the original choice, door #1.
ˆ Strategy 2: Switch always to the unopened door.
ˆ Strategy 3: Switch always to door #3 if door #2 is opened, otherwise stick to door #1.
(a) Implement a Matlab function that performs simulations to estimate the probability of win-
ning for each of the three strategies.
(b) Provide a single plot that shows these estimated probabilities of winning, for each of the
three strategies, as a function of q.
Task 3. [8+8+6+8 points]
Alice wants to solve six computational tasks (T1, . . . , T6) on her computer, which is equipped with
five Central Processing Units (CPU1, . . . , CPU5). Each task can be split into a certain number
of subtasks that can be processed in parallel (i.e., on different CPUs). However, each CPU can
Page 1 of 2
process only a specific number of subtasks (otherwise it would overheat).
Taking all these constraints into account, Alice came up with the computation plan shown below.
It is given in form of a binary matrix A with entries aij, i = 1, . . . , 5, j = 1, . . . , 6, where aij = 1
if, and only if, a subtask of Tj is processed on CPUi.
A =
T1 T2 T3 T4 T5 T6

a11 a12 a13 a14 a15 a16 CPU1
a21 a22 a23 a24 a25 a26 CPU2
a31 a32 a33 a34 a35 a36 CPU 3
a41 a42 a43 a44 a45 a46 CPU4
a51 a52 a53 a54 a55 a56 CPU5
=
1 2 3 4 5 6

1 0 1 0 1 1
1 1 0 0 0 1
0 1 1 1 1 1
1 0 1 1 1 1
1 1 1 0 1 1
Alice wonders whether there are other, ‘equivalent’, computation plans. A computation plan, i.e.,
a binary matrix B, is called equivalent to A if in each row and each column B has the same number
of 1s as A. A matrix A′ obtained from A by replacing a 2× 2 submatrix of the type(
1 0
0 1
)
or
(
0 1
1 0
)
by the other is said to be obtained from A by an interchange. It is a classical result (and you can
use it without proof) that B is equivalent to A if, and only if, B can be obtained from A by a
sequence of interchanges.
(a) Write a Matlab function EnumerateAllSolutions(A), which takes Alice’s A as input and
returns, by checking systematically all 5×6 binary matrices, the number of different matrices
that are equivalent to A. How many different matrices are equivalent to A?
(b) Write a Matlab function RunMarkovChain(A), which takes Alice’s A as input and generates
a Markov Chain, based on interchanges, that samples the matrices equivalent to A uniformly
at random. Provide a histogram that demonstrates that your RunMarkovChain(A) samples
the matrices equivalent to A uniformly at random.
(c) Prove that your Markov Chain from (b) is aperiodic, irreducible, and has the uniform distri-
bution as stationary distribution.
(d) Take your group number g and compute i0, j0 in Matlab as follows:
i0=ceil(g/5), j0=rem(g,5)+1;
Write a Matlab function RunMarkovChainNonUniform(A), which takes Alice’s A as input
and generates a Markov Chain, based on interchanges, that randomly samples the matrices
equivalent to A. The stationary distribution π of this Markov Chain should satisfy
π(A′) = 2π(A′′) (1)
for any matrix A′ with entry a′i0j0 = 1 and any matrix A
′′ with a′′i0j0 = 0. Provide a histogram
that demonstrates that your RunMarkovChainNonUniform(A) randomly samples the matrices
equivalent to A satisfying (1).
Submit your answers —including all plots, commented (!) matlab code, and calculations—
as one single PDF file via Canvas.
Page 2 of 2