# Coding a Poisson random variable Suppose R (Python) can only generate uniform random variables. How can you take advantage of this and generate Poisson random variables? # Inverse transform method Use the inverse transform method to generate an exponential random variable # The value of Pi Inscribe a circle in a square. Estimate the value of $\pi$ by computing the ratio of the number of times a uniformly chosen point on the square ends up in the circle. # Acceptance/Rejection Using an exponential random variable, generate a normal random variable that is conditioned to be be positive; from here, adjust this result to get a normal random variable. # Total variatonal distance Let $X$ and $Y$ be Poisson random variables with means $\lambda > \mu$. Show that $$d_{TV}(X, Y) \leq 2 (1-\exp(\mu-\lambda))$$ # Reversibility Let $P$ be transition matrix on a state space $S$, and $\pi$ be a probability measure on $S$. We say that $\pi$ is **reversible** for $P$ if $\pi_i p_{ij} = \pi_j p_{ji}$. * Check that the stationary distribution from a random walk on a finite graph is reversible. * Let $P$ be a transition matrix on a state space $S$. Check that if $\pi$ is reversible, then it is stationary. * Let $\pi$ be a reversible distribution for the transition matrix $P$ on a state space $S$. Let $X$ be Markov chain with transition matrix $P$, that is started at $\pi$. Let $a, b,c,d \in S$. Show that $$\mathbb{P}(X_0=a,X_1=b, X_2=c, X_3=d) = \mathbb{P}(X_0=d,X_1=c,X_2=b, X_3=a).$$ # Simple card shuffling Suppose that I have $n=52$ cards, arranged in some initial order. Consider the following procedure: I choose two cards with probability $1/ {n \choose 2}$, and then change their position; repeat. * Describe this procedure as a Markov chain. Can you code it? * With this procedure, can you get from an initial ordering to *any* other ordering? Why? * Do you think it has a stationary distribution? If, so, what is it? # The arrow of time Consider a Markov chain on $15$ states $1,2,3,4, \ldots, 15$. Suppose that the probability of going from state $i$ to $i+1$ is $0.9$, for all $1 \leq i \leq 15$ and the probability of going from state $i$ to $i-1$ is $0.1$ for all $2 \leq i \leq 15$; in the case that $i =1$, we allow the possibility of going to state $15$ with probability $0.1$, and if $i=15$, the probability of going to state $1$ is $0.9$. Do you think this Markov chain has a stationary distribution; if so, what is it? Is this Markov chain reversible? Explain. # Endnotes * Coding to be done in Python and R * Version: r format(Sys.time(), '%d %B %Y') * [Rmd Source](https://tsoo-math.github.io/ucl2/2021-HW-week7.Rmd)