مثال‌های زنجیره مارکوف

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

این صفحه شامل مثال هایی از زنجیره مارکوف است.

بازی های تخته ای با تاس[ویرایش]

بازی مار و پله و یا هر بازی دیگری که حرکات بوسیله ی تاس تعیین می شود یک زنجیره ی مارکوف هستند. این نوع بازی ها در نقطه مقابل بازی های کارتی مانند blackjack هستند که کارت ها مانند حافظه ی حرکت قبلی عمل می کنند. برای درک این تفاوتهااحتمال یک حرکت مشخص را در بازی در نظر بگیرید. در بالا به بازی هایی که با تاس بازی می شوند اشاره کردیم، تنها چیزی که اهمیت دارد حالت کنونی روی تخته است. حالت بعدی روی تخته به حالت کنونی و چرخش بعدی تاس بستگی دارد و وابسته به اینکه که مهره ها چگونه در حالت کنونی قرار گرفته اند، نیست. در بازی مانند blackjack ، بازیکن می تواند با به خاطر سپردن اینکه کدام کارتها تا کنون نشان داده شده اند، برتری کسب کنند. بنابراین حالت بعدی بازی مستقل از حالت کنونی نیست.

گام های تصادفی متمایل به مرکز[ویرایش]

یک حرکت تصادفی روی تعدادی خط را در نظر بگیرید، موقعیت کنونی (که x نامیده می نامیم) با احتمالات زیر می تواند به +۱ (به راست) یا -۱(به چپ) تغییر کند:

P_{move~left} = \tfrac{1}{2} + \tfrac{1}{2} \left( \tfrac{x}{c+|x|} \right)

P_{move~right} = 1 - P_{move~left}

(c یک عدد ثابت بزرگتر از ۰ است)

به عنوان مثال اگر عدد ثابت c برابر ۱ باشد، احتمال حرکت به چپ از موقعیت x=-۲,-۱٬۰٬۱٬۲ به ترتیب برابرست با: \tfrac{1}{6},\tfrac{1}{4},\tfrac{1}{2},\tfrac{3}{4},\tfrac{5}{6}.

یک گام تصادفی یک اثر مرکزی دارد بطوریکه با افزایش تضعیف c می شود. از آنجایی که احتمالات تنها به وضعیت کنونی بستگی دارد(مقدار x) و وابسته به هیچ یک از موقعیت های قبلی نیست، این گام تصادفی متمایل به مرکز در تعریف زنجیره ی مارکوف صدق میکند.

یک مدل آب و هوایی بسیار ساده[ویرایش]

احتمال وضعیت آب و هوایی که آب و هوا در طول روز را نشان می دهد و هم بصورت بارانی و هم آفتابی مدل می شود،توسط یک ماتریس انتقال ارائه داده میشود.


    P = \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}

ماتریس P یک مدل آب و هوایی را نشان می دهد بطوریکه روز بعد یک روز آفتابی، با احتمال %۹۰ آفتابی است و روز بعد یک روز بارانی، با احتمال %۵۰ آفتابی است. ستونها و سطرها با آفتابی و بارانی برچسب گذاری می شوند.

(P)i j احتمال این است که هوای امروز از نوع i باشد و فردا از نوع j باشد.

در نظر داشته باشید که حاصل جمع احتمالات سطر P برابر ۱ است.

پیش بینی آب و هوا[ویرایش]

هوا در روز ۰ آفتابی تشخیص داده شده. که این توسط یک بردار که ورودی آفتابی %۱۰۰ است و بارانی %۰ است نمایش داده می شود.


    \mathbf{x}^{(0)} = \begin{bmatrix}
        1 & 0
    \end{bmatrix}

آب و هوا در روز ۱ می تواند توسط به این صورت پیش بینی شود:


    \mathbf{x}^{(1)} = \mathbf{x}^{(0)} P  = 
    \begin{bmatrix}
        1 & 0
    \end{bmatrix}
    \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}
    
    = \begin{bmatrix}
        0.9 & 0.1
    \end{bmatrix}

بنابراین %۹۰ شانس این وجود دارد که روز ۱ آفتابی باشد.

آب وهوای روز ۲ به همین ترتیب پیش بینی می شود:


    \mathbf{x}^{(2)} =\mathbf{x}^{(1)} P  = \mathbf{x}^{(0)} P^2 
    = \begin{bmatrix}
        1 & 0
    \end{bmatrix}
    \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}^2
    
    = \begin{bmatrix}
        0.86 & 0.14
    \end{bmatrix}

یا


    \mathbf{x}^{(2)} =\mathbf{x}^{(1)} P 
    = \begin{bmatrix}
        0.9 & 0.1
    \end{bmatrix}
    \begin{bmatrix}
        0.9 & 0.1 \\
        0.5 & 0.5
    \end{bmatrix}
    
    = \begin{bmatrix}
        0.86 & 0.14
    \end{bmatrix}

فرمول کلی به این صورت است:


    \mathbf{x}^{(n)} = \mathbf{x}^{(n-1)} P

    \mathbf{x}^{(n)} = \mathbf{x}^{(0)} P^n

حالت ثابت آب و هوا[ویرایش]

در این مثال، پیش بینی هوا در روزهای دور از هم غلط از آب در می آید و متمایل به بردار حالت پایدار است.این بردار احتمال هوای آفتابی و بارانی را در همه ی روزها نشان می دهد و مستقل از آب وهوای اولیه است.

بردار حالت ثابت به این صورت تعریف می شود: 
    \mathbf{q} = \lim_{n \to \infty} \mathbf{x}^{(n)}

ولی تنها زمانی به یک مقدار منظم همگراست که p یک ماتریس انتقال منظم باشد(بعبارت دیگر حداکثر یک Pn با ورودیهای غیر صفر وجود دارد)

از آنجایی که q مستقل از شرایط اولیه است، زمانی که بوسیله ی P ترجمه می شود، بایستی بدون تغییر بماند. که این باعث میشود که q تبدیل به بردار ویژه شود، به این معنی که از P مشتق شود. برای مثال آب و هوا:


    \begin{matrix}
        P & = & \begin{bmatrix}
            0.9 & 0.1 \\
            0.5 & 0.5
        \end{bmatrix}
        \\
       \mathbf{q} P  & = & \mathbf{q}
        & \mbox{(} \mathbf{q} \mbox{ is unchanged by } P \mbox{.)}
        \\
        & = & \mathbf{q}I 
        \\
       \mathbf{q} (P - I)  & = & \mathbf{0} \\
        & = & \mathbf{q} \left( \begin{bmatrix}
            0.9 & 0.1 \\
            0.5 & 0.5
        \end{bmatrix}
        -
        \begin{bmatrix}
            1 & 0 \\
            0 & 1
        \end{bmatrix}
        \right) 
        \\
        & = & \mathbf{q} \begin{bmatrix}
            -0.1 & 0.1 \\
            0.5 & -0.5
        \end{bmatrix} 
    \end{matrix}

     \begin{bmatrix}
        q_1 & q_2
    \end{bmatrix}
    \begin{bmatrix}
        -0.1 & 0.1 \\
        0.5 & -0.5
    \end{bmatrix}
    = \begin{bmatrix}
        0 & 0
    \end{bmatrix}

پس 
    -0.1 q_1 + 0.5 q_2 = 0
و از آنجایی که این دو بردارند داریم 
q_1 + q_2 = 1

حل این دو معادله یک توزیع حالت یکنواخت را میدهد:


    \begin{bmatrix}
        q_1 & q_2
    \end{bmatrix}
    = \begin{bmatrix}
        0.833 & 0.167
    \end{bmatrix}

در نتیجه %۸۳ روزها آفتابی است.

منابع[ویرایش]

مشارکت‌کنندگان ویکی‌پدیا، «Examples of Markov chains»، ویکی‌پدیای انگلیسی، دانشنامهٔ آزاد.

پیوند به بیرون[ویرایش]