Markov zinciri (Emilim)

Question

Markov zincirini yeni öğrenmeye başladım ve bu sorunu nasıl çözeceğim konusunda bilgim yok

Bir adam 40 metre yüksekliğindeki bir tepeye bir kaya yuvarlıyor. Her dakika, 1/3 olasılıkla kayayı 1 metre yukarı yuvarlamayı başarırken, 2/3 olasılıkla kaya 1 metre aşağı yuvarlanıyor. Adam şu anda zirvenin yarısındaysa, tepelere inmeden zirveye ulaşma olasılığı nedir?

Answer 1

Markov Zinciri teorisini kullanarak bu sorunu çözmek abartılı olur: ancak temeldeki kavramlar , onu basit bir çözümü kabul eden bir şekilde çerçevelemenize yardımcı olacaktır.

Sorunu formüle etmek

En temel kavram bir durumdur: Bu durumu, altından (yükseklik -40) tepesine (yükseklik 0) bir metre yükseklik aralıklarında yerleştirilmiş 41 farklı konum veya "durum" açısından modelleyebiliriz. Tepe. Tepenin ortasındaki mevcut durum -20 yüksekliğindedir.

İkinci temel kavram, geçmiş olaylardan bağımsızlıktır: Bundan sonra ne olacağının şansı, insanın oraya nasıl gittiğine dair herhangi bir ayrıntıya değil, yalnızca devlete bağlıdır. Dolayısıyla zirveye ulaşma şansı sadece devlete bağlıdır. Buna göre yazarsak$s$ bir devlet için zirveye ulaşma şansı basitçe yazılabilir $p(s).$ Bulmamız isteniyor $p(-20).$

From any state $s$ between $-40$ and $0$ there is a $1/3$ chance that $s+1$ will be the next state and a $2/3$ chance that $s-1$ will be the next state. The most basic laws of conditional probability then imply

$$p(s) = (1/3)p(s+1) + (2/3)p(s-1) = \frac{p(s+1)+2p(s-1)}{3}.\tag{*}$$

The final step of formulating the problem treats the endpoints, or "absorbing states" $s=0$ and $s=-40.$ It should be clear that

$$p(0)=1;\ p(-40)=0.\tag{**}$$

Analysis

At this point the work may look formidable: who wants to solve a sequence of 40 equations? A nice solution method combines all the equations into a single mathematical object. But before we proceed, allow me to remark that you don't need to follow this analysis: it will suffice to check that the final formula (highlighted below) satisfies all the conditions established by the problem -- and this is just a matter of simple algebra.

At this juncture it is helpful to solve the general problem. Let's suppose there is a sequence of states $s=0,1,2,\ldots, n$ and that each state $s$ between $1$ and $n-1$ transitions to $s-1$ with probability $p$ and to $s+1$ with probability $1-p.$ For all $s$ let $a_s$ be the chance of arriving at state $0$ before hitting state $n.$ (I have dropped the previous "$p(-s)$" notation because it leads to too many p's and I have switched from indexing states with negative numbers to indexing them with positive numbers.)

As we have seen, $a_0=1,$ $a_n=0,$ and otherwise $a_{s} = pa_{s-1} + (1-p)a_{s+1}$ (the "recurrence relation"). This set of equations is neatly encoded by a polynomial

$$P(t) = a_0 + a_1 t + a_2 t^2 + \cdots + a_n t^n = a_0 + \sum_{s=1}^{n} a_s t^s.$$

Plugging in the recurrence relation and then collecting common powers of $t$ (writing $a_{n+1}=0$ for convenience) gives

$$\begin{aligned} P(t) &= a_0 + \sum_{s=1}^n \left[pa_{s-1} + (1-p)a_{s+1}\right]t^s \\ &= a_0 + p\sum_{s=1}^n a_{s-1} t^s + (1-p)\sum_{s=1}^n a_{s+1}t^s\\ &= a_0 + pt\sum_{s=1}^n a_{s-1} t^{s-1} + \frac{1-p}{t}\sum_{s=1}^n a_{s+1}t^{s+1}\\ &= a_0 + pt\sum_{s=0}^{n-1} a_{s} t^{s} + \frac{1-p}{t}\sum_{s=2}^{n+1} a_{s}t^{s}\\ &= a_0 + pt(P(t) - a_nt^n) + \frac{1-p}{t}(P(t) - a_0 - a_1t) \end{aligned}$$

This is a single equation for the polynomial $P$ (at least up to $t^n;$ I will ignore any coefficients of $t^n$ or higher powers that might be needed to make the equation work out exactly.) Simplify this equation a little using the initial condition $a_0=1$ and solve for $P$ to get

$$P(t) = \frac{(1-p) + (-1 + (1-p)a_1)t}{pt^2 - t + (1-p)}.$$

Now every coefficient of $P$ can be expressed in terms of the (still unknown) number $a_1.$ The value of $a_1$ is determined by the final condition $a_n=0.$

A closed formula is possible by expanding the right hand side as a partial fraction. It comes down to observing

$$\frac{1}{pt^2 - t + (1-p)} = \frac{1}{1-2p}\left(\frac{1}{1-t} - \frac{\lambda}{1 - \lambda t}\right)$$

and expanding the fractions as sums of geometric series, both of which are in the form

$$\frac{\rho}{1 - \rho t} = \rho + \rho^2 t + \rho^3 t^2 + \cdots$$

and multiplying that by the numerator $(1-p) + (-1 + (1-p)a_1)t$ to obtain $P(t).$ This gives a closed formula for every term in $P(t)$ as a function of $a_1.$

For $p\ne 1/2$ and writing $\lambda = p/(1-p)$ this approach gives the general result

$$a_s = \frac{\lambda^s - \lambda^n}{1 - \lambda^n}$$

for $s=1, 2, \ldots, n$ (and this happens to work for $s=0,$ too). (When $p=1/2,$ $\lambda=1$ makes this formula undefined. You can easily figure it out a simple formula, though, by taking the limit of $a_s$ as $\lambda\to 1$ using a single application of L'Hopital's Rule.)

As a check, it is clear this formula gives $a_0=1$ and $a_n=0.$ It remains to verify it satisfies the recurrence relation, but that's a matter of showing

$$\frac{\lambda^s - \lambda^n}{1 - \lambda^n} = a_s = pa_{s-1} + (1-p)a_{s+1} = p\frac{\lambda^{s-1} - \lambda^n}{1 - \lambda^n} + (1-p)\frac{\lambda^{s+1} - \lambda^n}{1 - \lambda^n},$$

which is straightforward.

Application

In the given problem $n=40,$ $p=1/3,$ and we are asked to find $a_{20}.$ Consequently $\lambda = (1/3)\,/\,(1-1/3) = 1/2$ and

$$a_{20} = \frac{2^{-20} - 2^{-40}}{1 - 2^{-40}} = 2^{-20} - 2^{-40} + 2^{-60} - 2^{-80} + \cdots.$$

The expansion on the right hand side can be terminated after the first two terms when computing in double precision floating point (which has a precision of $52$ binary places), giving

$$a_{20} \approx 2^{-20} - 2^{-40} \approx 9.53673406911546\times 10^{-7};$$

a little less than one in a million.

Answer 2

Imagine that the hill-climbing journey consists of 41 states, one for each meter possible, so states 0, 1, 3, ...., 40. The transition probability matrix then becomes a 41x41 matrix, representing the different probabilities of going from one state to another. It looks like the following:

   0    1    2    --    40
0  0    1    0    --     0
1 2/3   0   1/3   --     0
2  0   2/3   0    --     0
|  |    |    |    --     |
|  |    |    |    --     |
40 0    0    0    --     0

Let's call this matrix P. If we start at 20 meters, with other words at state 20, we can represent this as a vector (41 elements long) with the probabilities of starting in each state, called u, u=[0,0, ... , 0, 1, 0 ... 0, 0], where the 1 represent a 100% probability of starting at 20 meters.

The matrix multiplication, u*P, then becomes the probabilities of ending up in all other states at timestep t+1. If we continue to do this matrix multiplication over and over again, u*P^t, where t goes towards infinity, we will reach a steady state matrix P*. This steady state matrix represents the probabilities of ending up in all other states.

So in your case, you would do this matrix multiplication in a programming language of your choice many times (eg. 100+), and you would simply look up P[20,40], which would give you the probability of starting at 20 meters and making it all the way atop the hill!