— PROJECT 1 —
MATH 368, S2 2023 Dr. A. Alpers Deadline: 17/04/2023
[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
程序代写 CS代考 加QQ: 749389476
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.
T1 T2 T3 T4 T5 T6
1 0 1 0 1 1
1 1 0 0 0 1 =0 1 1 1 1 1.
1 0 1 1 1 1 111011
a11 a12 a13
a21 a22 a23 A=a31 a32 a33
a41 a42 a43 a51 a52 a53
a14 a15 a24 a25 a34 a35 a44 a45 a54 a55
a16 CPU1 a26 CPU2 a36CPU3 a46 CPU4 a56 CPU5
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 01 or 10
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′ = 1 and any matrix A′′ with a′′ = 0. Provide a histogram
i0 j0 i0 j0
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
Programming Help, Add QQ: 749389476