Question 1 : Snakes and Ladders
代做web – 该题目是一个常规的统计的练习题目代写, 是比较典型的统计等代写方向
Consider the game of snakes and ladders given by the following figure:
Part A
- Write a function that computes the transition matrix of the associ- ated Markov chain.
- Write a function that takes in an absorbing Markov chain and re- turns,QandR, i.e., the main components of the canonical form. The function should do the necessary work to make sure the tran- sient states are re-labeled appropriately.
Part B
- Re-using the functions above create a function that takes in an absorbing Markov chain and returns the fundamental matrixN.
- What are the most and least visited squares before the game fin- ishes? Are there parts of the board that are more visited than others before the game ends?
Part C
- Write a function to compute absorption times, and use it to com- pute the expected number of times a die is rolled before the game is finished.
- LetTbe the random variable that determines the number of steps required to win the game. Based on the transition matrix, simu- late the Markov chain and plot a histogram of the distribution of T. Is the expected value close to the theoretical value computed above? How many times do you need to sample to approach the theoretical value?
Part D
- Suppose that you modify the game so that you can rollndice at every turn. Using MC theory, compute and plot the expected time to win as a function the number of dice.
- What conclusions can you draw?
Part E – Optional
Write a computer program to study the stochastic properties ofany snakes and ladders game.
Question 2 : Random web surfer
A very successful model to study the structure of the web is the so- calledrandomwebsurfer. The model works as follows: The web consist of a fixed set of webpages (nodes), and links between them (edges). A random web surfer moves through the graph by randomly following links in the webpages. For a given structure, the idea is to figure out on average, where does the random web surfer spend most of the time. The ranking of the pages, given by the stationary distribution of the associated Markov chain, is known aspage-rank. The rank of each page is proportional to the total rank of the other pages which are pointing to it.
Consider a simplified web given by the directed graph above.
Part A
- Write down (by hand or using a function) the transition matrix of the associated Markov Chain
- Compute the stationary distribution using two methods(i) in- specting the eigenvector with the largest eigenvalue;(ii) using the power method, which involves taking a large power of the matrix.
- Provide the ranking induced by the stationary distribution
Part B
- Create a function that samples a trajectory of the chain, given a length. The program should return a sequence of states. Because the chain is ergodic,inthelongrun it doesnt matter where you start.
- How many steps are required so that the histogram induced by the simulation approaches the stationary distribution computed theoretically?
Part C.
Repeat the analysis now assuming that the random web surfer fol- lows a link with probability 0.9, or directly goes to a random page with probability 0.1. How does this assumption affect the page-rank?
Part D Optional.
Repeat the analysis with the larger graph given in the file web_graph.json, as an adjacency list.