ماتریس تصادفی

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

یک ماتریس تصادفی راست یک ماتریس مربعی حقیقی است که جمع هر سطرش $1$ می‌باشد.

یک ماتریس تصادفی چپ یک ماتریس مربعی حقیقی است که جمع هر ستونش $1$ می‌باشد.

یک ماتریس تصادفی دوگانه یک ماتریس مربعی از اعداد حقیقی غیر منفی است که جمع هر سطر و ستونش $1$ می‌باشد.

به همین شیوه می‌توان بردار تصادفی (بردار احتمال نیز نامیده می‌شود) را تعریف کرد؛ که برداری است با مقادیر حقیقی غیرمنفی و مجموع $1$. بنابراین هر سطر از ماتریس تصادفی راست (یا ستون از ماتریس تصادفی چپ) یک بردار تصادفی است.

قرارداد رایج در ادبیات ریاضی دانان انگلیسی زبان این است که از بردار سطری ماتریس تصادفی راست و احتمالات استفاده کنند تا بردار ستونی ماتریس تصادفی چپ و احتمالات؛ در این مقاله از این قرارداد رایج استفاده شده‌است.

تعریف و ویژگی‌ها

یک ماتریس تصادفی زنجیره مارکوف $X_{t}$ با تعداد حالات محدود از فضای $S$ را توصیف می‌کند.

اگر احتمال حرکت از حالت $i$ به حالت $j$ در یک مرحله زمانی را با عبارت $Pr(j|i)=P_{i,j}$ ماتریس تصادفی $P$ با استفاده از $P_{i,j}$ با عنصر ردیف $i$ و ستون $j$ مشخص خواهد شد،

$P=\left({\begin{matrix}P_{1,1}&P_{1,2}&\dots &P_{1,j}&\dots \\P_{2,1}&P_{2,2}&\dots &P_{2,j}&\dots \\\vdots &\vdots &\ddots &\vdots &\ddots \\P_{i,1}&P_{i,2}&\dots &P_{i,j}&\dots \\\vdots &\vdots &\ddots &\vdots &\ddots \end{matrix}}\right).$

با توجه به اینکه مجموع احتمال گذار از حالت $i$ به تمام حالات دیگر باید $1$ باشد، این ماتریس یک ماتریس تصادفی راست، پس

$\sum _{j}P_{i,j}=1.\,$

حاصل ضرب دو ماتریس تصادفی راست نیز یک ماتریس تصادفی راست است. به ویژه توان $k$ ماتریس تصادفی راست $P$، $P^{k}$ نیز یک ماتریس تصادفی راست است. احتمال انتقال از حالت $i$ به حالت $j$ در دو گام با عنصر$(i,j)$ از مربع ماتریس $P$:

$\left(P^{2}\right)_{i,j}.$

در کل احتمال انتقال رفتن از هر حالت به حالت دیگر در زنجیره مارکوف با ماتریس $P$ و در k مرحله با ماتریس $P^{k}$.

توزیع اولیه با بردار سطری نمایش داده می‌شود.

بردار احتمال مانا $\pi$ که به عنوان یک توزیع تعریف می‌شود، به صورت یک بردار سطری نوشته می‌شود، که با اعمال ماتریس انتقال تغییر نمی‌کند؛ به عبارت دیگر، این بردار به صورت توزیع احتمال روی مجموعه $\{1,2,...,n\}$ تعریف می‌شود. این بردار، بردار ویژه ماتریس احتمال متناظر با مقدار ویژه $1$ می‌باشد:

${\boldsymbol {\pi }}P={\boldsymbol {\pi }}.$

شعاع طیفی راست هر ماتریس تصادفی راست حداکثر $1$ می‌باشد. علاوه بر این، هر ماتریس تصادفی راست یک بردار ویژه ستونی بدیهی متناظر با مقدار ویژه $1$ دارد: بردار $1$ می‌باشند. همان‌طور که مقادیر ویژه چپ و راست یک ماتریس مربعی یکسان هستند، هر ماتریس تصادفی، حداقل یک بردار ویژه سطری متناظر با مقدار ویژه $1$ دارد و اندازه مطلق بزرگترین مقادیر ویژه‌اش $1$ است. در نهایت طبق قضیه مقدار ثابت براوئر (اعمال شده به مجموعه محدب فشرده از تمام توزیع‌های احتمال مجموعه متناهی $\{1,2,...,n\}$) حاکی از آن است که بردارهای ویژه چپی هم وجود دارند که بردار احتمال مانا باشند.

از سوی دیگر قضیه پرون-فربنیوس تضمین می‌کند که هر ماتریس تصادفی کاهش ناپذیر چنین بردار مانایی دارد و اندازه مطلق بزرگترین مقدار ویژه اش همیشه $1$ است. این قضیه را نمی‌توان به‌طور مستقیم به این ماتریس‌ها اعمال کرد، زیرا لازم نیست کاهش ناپذیر باشند.

به‌طور کلی ممکن است چندین بردار مانا وجود داشته باشند. هرچند، برای ماتریس با مقادیر مثبت آرایه (یا به‌طور کلی تر برای ماتریس تصادفی کاهش ناپذیر غیرپریودیک) این بردار منحصر به فرد است و با استفاده از حد زیر می‌توان آن را بدست آورد:

$\lim _{k\rightarrow \infty }\left(P^{k}\right)_{i,j}={\boldsymbol {\pi }}_{j},$

که $\pi _{j}$ عنصر $j$ از بردار سطری $\pi$. به بیان دیگر در دراز مدت، احتمال بودن در حالت $j$ مستقل از حالت اولیه $i$. نتیجه هر دوی این محاسبات بردار مانای یکسانی خواهد بود و این نتیجه از نظریه ارگودیک است، که به صورت عمومی در طیف گسترده‌ای از سیستم‌های دینامیکی اتلافی درست است: سیستم در طول زمان به یک حالت ایستا تکامل می‌یابد.

به‌طور شهودی، یک ماتریس تصادفی، نشان دهنده یک زنجیره مارکوف است؛ با اعمال ماتریس تصادفی به توزیع احتمال، جرم احتمال توزیع اولیه را با حفظ جرم کلی مجدداً توزیع می‌کند. اگر این روال برای زنجیره مارکوف به صورت مداوم تکرار شود، توزیع به توزیع مانا همگرا خواهد شود.

مثال: گربه و موش

فرض کنید شما یک تایمر و یک ردیف از پنج جعبه مجاور دارید؛ در زمان صفر یک گربه در جعبه اول و یک موش در جعبه پنجم قرار گرفته‌اند. با جلو رفتن زمان تایمر، گربه و موش هر دو به صورت تصادفی پرشی به یکی از جعبه‌های مجاورشان خواهند داشت. برای مثال اگر گربه در جعبه دوم و موش در جعبه چهارم باشد، احتمال اینکه با گذر یک مرحله از زمان تایمر، گربه در جعبه اول و موش در جعبه پنجم قرار گیرد یک چهارم است. اگر گربه در جعبه اول و موش در جعبه پنجم باشد، با احتمال $1$ با گذر یک مرحله از زمان، گربه در جعبه دو و موش در جعبه چهار خواهد بود. اگر گربه و موش به داخل جعبه یکسانی پرش داشته باشند، گربه موش را می‌خورد و بازی تمام خواهد شد. متغیر تصادفی $K$ نشان دهند تعداد مراحل زمانی است که موش در بازی زنده خواهند ماند.

زنجیره مارکوفی این بازی $5$ حالت دارد که هر حالت نشان دهنده موقعیت گربه و موش در بازی است. توجه داشته باشید گرچه شمارش عادی تعداد حالات $25$ خواهد بود، اما تعدادی از آن‌ها حالات غیرممکن هستند: چون موش نمی‌تواند شماره کوچکتری از شماره گربه داشته باشد (که معنی ماوس را اشغال گربه جعبه و جان سالم به در برد به گذشته حرکت می‌کند) یا اینکه مجموع دو شماره آن‌ها باید همیشه زوج باشد. ضمناً $3$ حالت منجر به مرگ مو خواهند شد و این سه حالت را ترکیب کرده و یک حالت در نظر می‌گیریم:

• حالت $1$: $(1,3)$
• حالت $2$: $(1,5)$
• حالت $3$: $(2,4)$
• حالت $4$: $(3,5)$
• حالت $5$: انتهای بازی: $(2,2)$، $(3,3)$ و $(4,4)$.

برای نمایش احتمال انتقال این سیستم از ماتریس تصادفی استفاده می‌کنیم (سطرها و ستون‌های این ماتریس با شماره حالات ممکن ذکر شده در بالا شماره گذاری شده‌اند. حالت قبل از انتقال به صورت ردیف و حالت پس از انتقال به صورت ستون در نظر گرفته می‌شود).

$P={\begin{bmatrix}0&0&1/2&0&1/2\\0&0&1&0&0\\1/4&1/4&0&1/4&1/4\\0&0&1/2&0&1/2\\0&0&0&0&1\end{bmatrix}}.$

میانگین‌های دراز مدت

حالت اولیه گربه هر حالتی که باشد، در نهایت گربه موش را می‌گیرد (با احتمال $1$) و یک حالت مانای پیشنهادی $\pi =[0,0,0,0,1]$ است. برای محاسبه میانگین دراز مدت یا امید متغیر تصادفی $Y$، برای هر حالت $S_{j}$ و زمان $t_{k}$ سهم $Y_{j,k}.P(S=S_{j},t=t_{k})$ وجود دارد. بقا را می‌توان با یک متغیر باینری با $Y=1$ برای حالت بقا و $Y=0$ برای حالت اختتام نشان داد. حالت‌های با $Y=0$ در میانگین دراز مدت دخیل نیستند.

نمایش فاز-نوع

تابع بقای موش. موش حداقل پس از یک مرحله زمانی زنده خواهد ماند.

حالت $5$ یک حالت جذب است، توزیع زمان جذب، توزیع فاز-نوع گسسته است. فرض کنید سیستم با حالت $2$ شروع شود که آن را با بردار $[0,1,0,0,0]$ نشان می‌دهیم. حالاتی که در آن‌ها موش می‌میرد، در میانگین بقا تأثیری نخواهند داشت و می‌توان حالت $5$ را نادیده گرفت. حالت اولیه و ماتریس انتقال را می‌توان به صورت زیر کاهش داد:

${\boldsymbol {\tau }}=[0,1,0,0]$

و

$T={\begin{bmatrix}0&0&1/2&0\\0&0&1&0\\1/4&1/4&0&1/4\\0&0&1/2&0\end{bmatrix}}\,,$

$(I-T)^{-1}{\boldsymbol {1}}={\begin{bmatrix}2.75\\4.5\\3.5\\2.75\end{bmatrix}}\,,$

که در آن $I$ ماتریس همانی و $1$ بردار ستونی تماماً ۱ می‌باشد (نقش جمع‌کننده روی حالات را دارد).

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

$E[K]={\boldsymbol {\tau }}(I+T+T^{2}+\cdots ){\boldsymbol {1}}={\boldsymbol {\tau }}(I-T)^{-1}{\boldsymbol {1}}=4.5.$

ممان‌های مرتبه بالاتر با عبارت زیر تعیین می‌شوند

$E[K(K-1)\dots (K-n+1)]=n!{\boldsymbol {\tau }}(I-{T})^{-n}{T}^{n-1}\mathbf {1} \,.$

جستارهای وابسته

• نامساوی مویرهد
• قضیه پرون-فربنیوس
• ماتریس چگالی
• ماتریس تصادفی دوگانه
• توزیع فاز-نوع گسسته
• اتوماتای احتمالاتی
• مدل‌های سیر تکاملی دی‌ان‌ای
• کرنل مارکوف هم ارز ماتریس تصادفی در فضای حالت پیوسته

منابع

• G. Latouche, V. Ramaswami. Introduction to Matrix Analytic Methods in Stochastic Modeling, 1st edition. Chapter 2: PH Distributions; ASA SIAM, 1999.