دانلود کتاب Markov chains

زنجیره مارکف که به افتخار آندری مارکوف ریاضی‌دان اهل روسیه این گونه نام‌گذاری شده یک سیستم ریاضی است که در آن انتقال از یک حالت به حالت دیگر صورت می‌گیرد که البته تعداد این حالات قابل شمارش است. زنجیره مارکف یک فرایند تصادفی بدون حافظه‌است بدین معنی که توزیع احتمال شرطی حالت بعد تنها به حالت فعلی بستگی دارد و به وقایع قبل از آن وابسته نیست. این نوع بدون حافظه بودن خاصیت مارکف نام دارد. زنجیره مارکف در مدل سازی دنیای واقعی کاربردهای زیادی دارد.

معرفی
زنجیره مارکوف (Markov Approach modeling) یک فرایند تصادفی گسسته در زمان با خاصیت مارکف است. اگرچه برخی از نویسندگان در مورد فرایندهای پیوسته در زمان هم از اصطلاح زنجیره مارکف استفاده می‌کنند. یک فرایند تصادفی گسسته در زمان شامل سیستمی است که در هر مرحله در حالت خاص و مشخصی قرار دارد و به صورت تصادفی در هر مرحله تغییر حالت می‌دهد. مراحل اغلب به عنوان لحظه‌های زمانی در نظر گرفته می‌شوند ولی می‌توان آن‌ها را فاصله فیزیکی یا هر متغیر گسسته دیگری در نظر گرفت. خاصیت مارکف بیان می‌کند که توزیع احتمال شرطی برای سیستم در مرحله بعد فقط به حالت فعلی سیستم بستگی دارد و به حالت‌های قبل بستگی ندارد. چون سیستم به صورت تصادفی تغییر می‌کند به‌طور کلی پیش‌بینی حالت زنجیره مارکف در نقطه‌ای خاص در آینده غیرممکن است. با این حال ویژگی‌های آماری سیستم در آینده قابل پیش‌بینی است. در بسیاری از کاربردها چیزی که دارای اهمیت است همین ویژگی‌های آماری است.

تغییرات حالات سیستم انتقال نام دارند و احتمال‌هایی که به این تغییر حالت‌ها نسبت داده می‌شوند احتمال انتقال نام دارند. مجموعه‌ای از حالت‌ها و احتمال انتقال‌ها به‌طور کامل یک زنجیره مارکف را مشخص می‌کنند. طبق قرار داد، ما فرض می‌کنیم همیشه حالت بعدی وجود دارد و در نتیجه فرایند تا ابد ادامه پیدا می‌کند.

یکی از معروف‌ترین زنجیره‌های مارکف که موسوم به «پیاده‌روی می خواره» است یک پیاده‌روی تصادفی است که در آن در هر قدم موقعیت با احتمال برابر به اندازه ۱+ یا ۱- تغییر می‌کند. در هر مکان دو انتقال ممکن وجود دارد یکی به عدد صحیح بعدی(۱+) و یکی به عدد صحیح قبلی(۱-). احتمال هر انتقال فقط به حالت کنونی بستگی دارد. برای مثال احتمال انتقال از ۵ به ۶ برابر با احتمال انتقال از ۵ به ۴ است و هر دوی این احتمالات برابر با ۰٫۵ هستند. این احتمالات مستقل از حالت قبلی (که یا ۴ بوده یا ۶) هستند.

مثالی دیگر عادات غذایی که فقط انگور، پنیر و کاهو می‌خورد و عادات غذایی او از قوانین زیر پیروی می‌کند:

او فقط یک بار در روز می‌خورد.
اگر امروز پنیر بخورد فردا انگور یا کاهو را با احتمال برابر خواهد خورد.
اگر امروز انگور بخورد فردا با احتمال ۰٫۱ انگور، با احتمال ۰٫۴ پنیر و با احتمال ۰٫۵ کاهو خواهد خورد.
اگر امروز کاهو بخورد فردا با احتمال ۰٫۴ انگور و با احتمال ۰٫۶ پنیر خواهد خورد.
عادات غذایی این موجود را می‌توان با یک زنجیره مارکف مدل سازی کرد به دلیل این که چیزی که فردا می‌خورد (حالت بعدی) تنها به چیزی که امروز خورده‌است (حالت فعلی) بستگی دارد. یکی از ویژگی‌های آماری که می‌توان در مورد این زنجیره محاسبه کرد امید ریاضی (یا همان مقدار چشمداشتی Expected Value) درصد روزهایی است که انگور خورده‌است (در یک دوره طولانی).