You are a producer on a game show hosted by Randy “Random” Hall (no relation to Monty Hall). The show has three doors labeled 1 through 3 from left to right, and behind them are various prizes.
Contestants pick one of the three doors at which to start, and then they press an electronic button many, many times in rapid succession. Each time they press the button, they either stay at their current door or move to an adjacent door. If they’re at door 2 and move to an adjacent door, that new door will be 1 or 3 with equal probability.
Randy has decided that when a contestant presses the button while at door 2, there should be a 20 percent chance they remain at door 2.
As the producer, you want the chances of a contestant ultimately winding up at each of the three doors to be nearly equal after many button presses. Otherwise, mathematicians will no doubt write you nasty letters complaining about how your show is rigged.
If a contestant presses the button while at door 1 (or door 3), what should the probability be that they remain at that door?
Firstly, so true ... if there were a meaningful bias in the supposedly uniformly random process of selecting which door, I would take notice. Though rather than calling to complain I would be more likely to try to get on the show to exploit this bias, but I guess potato-potato.
Moving on, per Randy's specifications and your desire for the appearance of uniform randomness, we have a three state Markov chain setup where the transition matrix $$P= \begin{pmatrix} p & 1-p & 0 \\ 0.4 & 0.2 & 0.4 \\ 0 & 1-p & p \end{pmatrix}$$ and we are wondering for which values of $p$ will $P^n \to U,$ as $n\to \infty$, where the limiting matrix $U$ is the $3\times 3$ matrix where each entry is $\frac{1}{3}.$
There are many ways to solve for $p$ here. For instance, though we would obviously start with some specific position, e.g., $\pi_0 = (1,0,0)$, if $P^n \to U,$ as $n\to \infty$, then we would necessarily need to have $u=(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ satisfy $uP=u$. We could obviously just solve here and get three linear equations (that hopefully collapse well since there is only one unknown), but instead let's math out!
Since $P$ is a transition matrix its rows sum to one, so we see that $Pu^T=u^T,$ which if we combine with $uP=u$ implies the $$Pu^T= u^T = (uP)^T = P^Tu^T.$$ So $P$ must be symmetric $(P=P^T)$, which leaves the much easier linear equation $1-p=0.4,$ that is, in order to provide the illusion of a uniform distibution of the door's landing spot through this elaborate Markov scheme you must have the probability of remaining on door 1 when the button is pressed be $p=60\%.$
Of course, armed with the knowledge that we have a symmetric transition matrix, we can then justify that this works by using the Spectral Theorem. We have already seen that $\lambda=1$ and $u^T$ is an eigenpair. We could certainly additionally calculate the other two eigenpairs as well, or simply argue that the eigenvalues must have absolute value less than $1$ and that the eigenvectors can be chosen to be an orthonormal basis of $\mathbb{R}^3$, such that $P=VDV^T,$ where $D = diag(1, \lambda_2, \lambda_3)$ and $$V= \begin{pmatrix} \sqrt{3}/3 & v_{12} & v_{13} \\ \sqrt{3}/3 & v_{22} & v_{23} \\ \sqrt{3}/3 & v_{32} & v_{33} \end{pmatrix}$$ satisfies $V^TV=VV^T=I.$ Since this $V$ represents an orthonormal basis we can change bases and represent any initial $\pi_0$ in $V$-coordinates, where the first coordinate is also $\sqrt{3}/3$ whenever $\pi_0$ sums to $1.$ Let's generically assume that $\pi_0 v_2 = c_2 \in \mathbb{R}$ and $\pi_0 v_3 = c_3 \in \mathbb{R}.$ Then we see that \begin{align*}\pi_n = \pi_{n-1} P &= \pi_{n-1} VDV^T \\ &= \cdots = \pi_0 V D^n V^T \\ &= u + c_2 \lambda_2^n v_2^T + c_3 \lambda_3^n v_3^T\end{align*} Since $|\lambda_2|, |\lambda_2| \lt 1,$ we see that for any value of $\pi_0$ we get $\pi_n \to u,$ as desired.
No comments:
Post a Comment