## Description

CECS 451

Assignment 6

Total: 54 Points

General Instruction

• Submit your work in the Dropbox folder via BeachBoard (Not email or in class).

• Submit the separate files as they are. (no zip file)

1. (10 points) Implement a program to compute π value using Monte Carlo simulation

method. Use Python 3 and the name pi.py

(a) The program should generate n points to compute π for n ∈ {103

, 104

, 105

, 106}.

(b) You can use math.pi to compute error rates.

(c) Please follow the output format. (Fix precisions using “0:.nf”.format)

n = 10 ^ 3 pi = 3.096000 error = 1.4513 %

n = 10 ^ 4 pi = 3.136800 error = 0.1526 %

n = 10 ^ 5 pi = 3.145280 error = 0.1174 %

n = 10 ^ 6 pi = 3.140568 error = 0.0326 %

2. Consider Figure 1, and implement a program to answer the query P~ (C|¬s, w) by using

Gibbs (MCMC) sampling. The program should generate 1, 000, 000 samples to estimate

the probability. Use Python 3 and the name gibbs.py

(a) (8 points) Show P~ (C|¬s, r), P~ (C|¬s, ¬r), P~ (R|c, ¬s, w), P~ (R|¬c, ¬s, w).

(b) (16 points) Show the transition probability matrix Q ∈ R

4×4 where

qij = transition probability from Si to Sj

in Figure 2.

(c) (20 points) Show the probability of the query P~ (C|¬s, w)

(d) Please follow the output format. (Fix precisions using “0:.nf”.format)

Part A. The sampling probabilities

P(C|-s,r) = <…, …

P(C|-s,-r) = <…, …

P(R|c,-s,w) = <…, …

P(R|-c,-s,w) = <…, …

Part B. The transition probability matrix

S1 S2 S3 S4

S1 . . . .

S2 . . . .

S3 . . . .

S4 . . . .

Part C. The probability for the query

P(C|-s,w) = <…, …

CECS 451 Assignment 6 – Page 2 of 2

Figure 1: A multiply connected network with conditional probability tables

Figure 2: Possible states diagram