CS314 Numerical Methods

Fall 2018

Homework 02

Due 11:59PM, Tuesday, Sept 25, 2018

*** Homework must be submitted via Blackboard in PDF file format. The PDF file (i.e. the main

file) should include Matlab code (if necessary) and also the Matlab code should be uploaded in

separate files (i.e., .m files).

*** Your PDF file should be named as follows: FistnameLastnameHWxx.pdf, where xx represents

the homework number, e.g., 01.

*** You should write up your own solution, and you are not permitted to share or copy someone

else’s written solution or code. All projects are individual projects.

1. (10 points) For this problem we are going to implement our own Monte Carlo simulation of a

web surfer using a network of six nodes represented by the following adjacency graph.

G = [gij ]6×6 =

?

0 0 0 1 0 0

1 0 0 0 0 0

1 0 0 0 0 0

0 1 1 0 1 0

0 0 1 0 0 1

0 0 0 1 0 0

.

That is, gij = 1 if there is a outgoing link from node i to node j, and 0 otherwise. You may assume

that just like in the original formulation of PageRank that 85% of the time a surfer follows a link

on the web page being visited and that the other 15% they visit a random page. Compute the

probability of landing on each page from up to 5000 simulations of our surfer’s movements on the

network above. Also, write down the transition matrix M = [mij ]6×6. The transition matrix M is

referred as Google matrix (see, Page 332 of the textbook). Note that the sum of elements in each

row is equal to 1.

Note: The sample code in the textbook should be a good starting point for this problem.

2. (10 points) Using the same network and probabilities as above, compute the probabilities

of landing on each page using multiple surfers. You can do this as follows.

? Initialize a counter for every node.

? Initialize a surfer for every node.

1

? Have the surfers move to a different node with the probabilities following the transition matrix

M calculated in Problem 1.

? When the surfers move to a different node increment the counter that corresponds to that

node by the amount of surfers that land on that node.

? Repeat this process 500 times. Compute the probabilities by dividing the count of each node

by the number of simulations carried out.

Do your results agree with the previous problem?

3. (10 points) A famous probability puzzle is the Monty Hall problem. A contestant on a game

show is given the choice of choosing between three doors. If they choose the correct door they win

a car, otherwise nothing. Behind one door is the car, and behind the other two doors are goats.

However, when you pick a door, the host, who knows what’s behind each of the doors, opens a door

that you did not pick that contains a goat. The host then gives you the option to stay or switch.

Write MATLAB code that simulates the Monty Hall problem. It should output the probability of

success if you switch doors as well as the probability of success if you decide to stay. Run the code

1000 times. Do the results converge to what your intuition expected them to?

Note: This is also problem 3 in the book

4. (10 points) Another famous probability puzzle is the birthday problem. The problem states

that in a randomly selected group of n people, at least two have the same birthday with some probability

P. Assume a year has 365 days. Write MATLAB code to compute and plot the probability

of a match from n = 2 to n = 100. For roughly what n can we almost guarantee that a pair of

people has the same birthday?

Note: This is similar to problem 7 in the book

5. (10 points) Say someone offers you a game where a fair coin is tossed at each stage of the

game. Starting at 2 dollars, for every heads that appears the amount of money in the pot is doubled.

If the flip results in a tails you keep all the money that is accrued in the pot. For instance,

if our coin flip is HHHT, the pot has accrued 8 dollars, and you win that 8 dollars due to the final

flip being a tails. How much money would you pay to have a chance at playing this game? Write

MATLAB code to simulate playing this game 10000 times and plot the results of your earnings.

Compute the expected value of playing this game. How much would you pay to play it now? Does

your simulation agree with your computation?

6. (5 points) Let X and Y be random variables with finite expected values. Show that the

following are true.

(a) E(X + Y ) = E(X) + E(Y )

(b) E(cX) = cE(x), where c is a constant.

7. (5 points) Let X be the result of rolling a fair die. Compute the following.

(a) Expected value of X.

(b) The variance of X.

(c) The standard deviation of X.

2

8. (5 points) Is E[X2

] equivalent to E[X]

2

? Why or why not? Justify your reasoning.

版权所有：留学生编程辅导网 2018 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。