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 repre- sents the homework number, e.g., 01.
*** You should write up your own solution, and you are not permitted to share or copy some- one 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.
000100
100000
1 0 0 0 0 0 G=[gij]6×6=0 1 1 0 1 0.
0 0 1 0 0 1
000100
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 prob- ability 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 dou- bled. 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.
3