In this exercise, we will try a clustering algorithm which is an another application of Markov chain in machine learning. Before we get started, we simulate a dataset based on the following sampling process: (Xi, Yi) = (risin(0;), r; cos(0i)) for i = 1, 2, ..., 500 where r; ~ U[1, 2] and (; ~ U[0, 27]; and (Xi, Yi) = (risin(0;), r; cos(0:)) for i = 501, 502, ..., 1000 where ri ~ U[4, 5] and A; ~ U[0, 2x].| 2 -2 -4 Figure 1: Two clusters in this simulated dataset 1. Now we want to design a Markov chain such that the state space = these 1000 data points, and the transition probability matrix is designed as follows: Pij = Pr((X,, Y,)I(Xi, Yi)) xx C(i, j) = exp(-(Xi - X; )? - (Yi - Y; )?). Here, C(i, j) is a metric indicating connectivity between any pair of data points (i, j). Following this idea and due to the constraint _, Pij = 1, we should have Puj = C(i, j)/ E, C(i, j). What is the stationary distribution of this Markov chain? Can you directly identify two clusters from this distribution? 2. Compare with the clustering results using a k-means algorithm. What is the advantage of this Markov chain based clustering algorithm