Random walk on a weighted graph

Let $G$ be an undirected graph with vertex set $V$ and edge set $E$, and let $w : E \to \mathbb{R}_{\ge 0}$ a weighting of the edges. Define $X$ to be the continuous-time Markov chain on $V$ that, when at vertex $v$, jumps to vertex $u$ with rate equal to the weight on the edge between $u$ and $v$, i.e., with rate $w(\{u,v\})$. Show that the stationary distribution of $X$ is uniform on $V$.

It's raining candy

We are called in to inspect a malfunctioning candy factory: about every 5 seconds, the machine ejects a random, Geometrically distributed number of M&Ms (with an average of 5 M&Ms per event). These land on the floor, where they are eaten by children (on a school tour, now uncontrollable) at an average rate of $\alpha$ per second.

Let $M(t)$ be the number of loose, uneaten M&Ms.

  1. Write down the generator for the continuous-time Markov chain that models $M(t)$.
  2. Calculate and plot the stationary distribution of the amount of candy on the floor with $\alpha = 1.1$ candies/second.
  3. Later, the situation becomes worse: $n$ machines begin to break and $n$ tour groups show up, scaling the rates of both appearance and dissapearance of candy. Let $X(t) = M(t) / n$, and show that the generator for $X$ satisfies for $x > 0$ $$ Gf(x) = (1 - \alpha) \frac{d}{dx} f(x) + O\left(\frac{1}{n}\right) .$$
  4. By using the approximate generator in (3), show that the amount of candy is nearly deterministic by solving for $\mathbb{E}[X(t)]$ and $\text{var}[X(t)]$.

Note: For part (2) you may want to use np.linalg.solve and the fact that if $\pi^T G = 0$ and $\pi^T \mathbf{1} = 1$ then $\pi^T (\mathbf{1}\mathbf{1}^T + G) = \mathbf{1}^T$.

Block stacking

My two-year-old stacks blocks, adding a new block to the existing stack at an average rate of 6 per minute. The chance that a tower of $n$ blocks does not fall over during the course of $t$ minutes is $\exp(-nt)$. Once the tower falls over, it becomes a tower of 0 blocks, and construction continues. Modeling the height of the tower as a continuous time Markov chain, find the following quantities, and check your results with a simulation:

  1. The probability that a given tower reaches height $N$ before collapsing.
  2. The stationary distribution of the height of the tower.
  3. Compute numerically the probability that there will be a tower with 6 blocks present 1 minute after starting to stack.