Notların üçüncü bölümünde Stochastic Process'ler konusunda önemli bir denklem olan Chapman-Kolmogorov denklemini ele alacağız. Öncesinde Markov süreçlere dair temel birkaç tanım yaptıktan sonra denklemi ifade edip, çözümüne dair birkaç laf ederek sonunda 'Master Equation' olarak adlandırılan önemli bir denklemi elde edeceğiz.
(NOT: Bu yazıda farklı bir kaynaktan yararlandığım için serinin diğer yazılarından biraz farklı bir notasyon kullandım. Kaynağım V. Balakrishan'ın 'Physical Applications of Stochastic Processes' ders videoları (Lecture 6).)
Elimizde zamanla farklı durumlar arasında 'dolaşan' bir süreç var ve bu süreci gözleyerek zaman serisi şeklinde veriler elde ediyoruz. $\mathbb{X}$ olarak adlandıracağımız bu sürecin durum uzayı ${j_1, j_2, ...}$ (ve kimi zaman da $k$ ve $l$ olarak) ve zaman örnekleri de ${t_1, t_2, ...}$ şeklinde etiketlensin. $\mathbb{X}$ sürecini tanımlayabilmemiz için $j_1$'den başlayıp $n$ adım sonunda $j_n$ durumuna gelen zincir için şu olasılığı yazabilmemiz gerekir:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) \tag{1}$$ $P_n$ ifadesindeki $n$ kaç adımlık bir olasılık yazdığımızı gösteriyor.
Bu ifadeyi koşullu olasılıklar şeklinde yazarsak şunu elde ederiz:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = P_n(j_n, t_n| j_{n-1}, t_{n-1}; ...; j_1, t_1) P_{n-1}(j_{n-1}, t_{n-1}; ... ; j_1, t_1) \tag{2}$$
Üstteki iki olasılık ifadesinden ilki ($P_n$) terimi, fiziksel bir varsayımda bulunursak epey sadeleşiyor; bu da gözlemlediğimiz çoğu sürecin eğer yeteri kadar değişken kullandığımız takdirde bir sonraki adımı, sadece bir önceki adımına bağlı, geçmişteki tüm durumlarından bağımsız olması. Buna Markov özelliği diyoruz. Bu durumda ilk terim şu şekilde sadeleşiyor:
$$P_n(j_n, t_n| j_{n-1}, t_{n-1}; ...; j_1, t_1) = P_2(j_n, t_n|j_{n-1}, t_{n-1}) \tag{3}$$
Markov varsayımını kullandığımızda $(1)$'i aşağıdaki gibi iki adımlık olasılıkların çarpımı şeklinde yazabiliyoruz:
$$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = \big(\prod_{r=1}^{n-1}P_2(j_n, t_n|j_{n-1}, t{n-1})\big)P_1(j_1, t_1) \tag{4}$$
Zincirin yapısı gereği, zamanla durumların istatistiklerinin değişmediği yani zincirin evriminin zamana özel olarak bağlı olmadığı süreçleri durağan (stationary) süreçler olarak tanımlıyoruz. Durağanlık, iki durum arası geçiş olasılıklarının her bir durumun ilgili zamanı yerine, iki durumun zaman farklarına bağlı olmasına neden oluyor. Yani hangi zamanlarda değil de aralarında ne kadar zaman farkı ile geçtikleri önem kazanıyor.
$$P_2(k,t|j, t') = f(t-t')$$
Sadece arada geçen zaman önemli olduğuna göre zamanın başlangıç noktasını kaydırarak (bir önceki yazıdaki Markov zincirlerinin zamanda homojen olma özelliğini kullanarak) bu olasılığı şöyle ifade edebiliriz:
$$P_2(k,t|j, t') = P_2(k, t-t'|j, 0) \equiv P_2(k, t- t'|j) \tag{5}$$
Son adımda başlangıç zamanı $0$'ı notasyondan çıkardık ve bundan sonra verilmediği her durum için $0$'dan başladığını düşünüyoruz. Bu tanımlamalar altında $(1)$ denklemini aşağıdaki gibi ifade ediyoruz: $$P_n(j_n, t_n; j_{n-1}, t_{-1};...;j_1, t_{-1}) = \big(\prod_{r=1}^{n-1}P_2(j_{r+1}, t_{r+1} - t_r|j_r)\big) P_1(j) \tag{6}$$
Son olarak zamanda ilerledikçe ($t \to \infty$) $P(k, t| j)$'nin başlangıç durumu $j$'den bağımsızlaşacağını ve durağan duruma eriştiğinde erişilen durumun durağan olasılığına eşit olacağını varsayıyoruz; kısacası zincir yeteri kadar beklendiğinde geçiş hafızasını tamamen unutuyor. Bu durum Markov zincirlerinde 'mixing' (karışma) şeklinde ifade ediliyor. Kısacası elimizdeki olasılıklar şuna indirgeniyor: $$ P(k, t |j) \longrightarrow P(k)$$
Bu şartlar altında zincirin ilk başta $j$ durumundayken, $t$ kadar süre sonra $k$ konumunda olma olasılığını şu şekilde yazabiliriz:
$$\boxed{ P(k, t|j) = \sum_{l = 1}^N P(k, t - t'| l) P(l, t'|j)} \tag{7}$$
Bu denklem bize şunu söylüyor: Eğer $j$'den $k$'ya gitme olasılığını hesaplamak istiyorsak, aradaki her bir $l$ durumundan geçme olasılıklarını bulup çarparak sonuca erişiyoruz. Bu denklem 'Chapman-Kolmogorov Denklemi' olarak biliniyor. Denklem iki olasılık çarpımından oluşuyor; olasılıklara göre doğrusal olmayan (nonlinear) bir denklem olduğundan hesaplaması oldukça güç. Bunu doğrusal bir şekilde yazabilsek hayat çok daha kolaylaşacak. Bunun için de durumların birim zamanda birbirine ortalama geçiş sayısını belirten bir parametre olarak 'geçiş oranı' (transition rate) $w(k,j)$ tanımlıyoruz.
$$P(k, \delta t|j) = w(k|j)\delta t\hspace{1.5cm} k \not= j \tag{8}$$
Kolmogorov-Chaapman denklemindeki geçiş olasılıkları yerine $(8)$'deki ifadeyi yerleştirip $t - t' = \delta t$ olarak aldığımızda aşağıdaki diferansiyel denklemi elde ederiz.
$$ \boxed{\frac{d}{dt} P(k, t |j) = \sum_{l = 1}^N \big[ w(k,l)P(l,t|j) - w(l,k)P(k,t|j)\big]} \tag{9}$$
Bu denklem 'Master Equation' olarak adlandırılıyor. Görüldüğü gibi $(9)$ birinci dereceden bir diferansiyel denklem. $(7)$'deki doğrusal olmayan terim yerine $P$'nin doğrusal terimleri var artık denklemde. Sağdaki toplam, tüm $l$ ara durumları üzerinden yapılıyor. Denklemin sağ tarafında toplam içindeki terim $j$'den önce ara durum olan $l$'ye, ardından nihai durum $k$'ya geçişi yani olasılıktaki artışı(gain term); ikincisi ise önce $j$'den nihai durum $k$'ya, ardından ara durumlardan biri olan $l$'ye geçişi yani olasılıktaki azalmayı (loss term) veren terimler.
Böylece elimizdeki Markov Zinciri'nin başlangıçtaki bir durumdan $t$ kadar süre sonra başka bir duruma geçme olasılığının zamanla değişimini veren bir denklem elde etmiş olduk.
31 Ocak 2018 Çarşamba
30 Ocak 2018 Salı
Stochastic Processes - II
Notlarımızın ikinci kısmına basit bir toplam 2 duruma sahip basit bir Markov Zinciri'ni inceleyerek başlayalım. Elimizde, 1 ve 2 ile etiketlenmiş iki duruma sahip bir Markov Zinciri olsun; durumlar arasındaki geçişler de aşağıdaki diyagramda gösterildiği gibi verilmiş olsun. Okların üzerinde yazan sayılar geçiş olasılıklarını versin.
Zincirin geçiş matrisi $P$'yi şu şekilde yazabiliriz: $$ \begin{pmatrix} 1- \alpha & \alpha \\ \beta & 1 - \beta \end{pmatrix}$$
$\alpha, \beta \in (0,1)$. Geçiş matrisini başlangıç olasılık dağılımı ($\lambda_0$) ile çarparak bir sonraki adımlardaki dağılımları elde ediyoruz. $$ P \lambda_0 = \lambda_1 \\ P \lambda_1 = \lambda_2 = P^2 \lambda_0 \\ ... \\ P^n \lambda_0 = \lambda_n $$
$P^n$ matrisinin büyük $n$ değerleri için nasıl davranacağını anlamak için, $P$'yi orthogonalize edip özdeğer (eigenvalue) ve özvektörlerini (eigenvecor) bulalım.
$$\text{det} (P - \nu \mathbb{I}) = \begin{vmatrix} 1- \alpha - \nu & \alpha \\~\\ \beta & 1 - \beta - \nu \end{vmatrix} = 0 \\~\\ (1- \alpha - \nu) (1 - \beta - \nu) -\alpha \beta = 0 \\~\\ \nu_{1,2} = \frac{2 - \alpha - \beta \pm (\alpha + \beta)}{2}$$
Bu denklemlerden iki özdeğeri $\nu_1 = 1$, karşılık gelen özvektörü $\begin{bmatrix} 1 \\ 1 \end{bmatrix} $ ve $\nu_2 = 1- \alpha - \beta$, karşılık gelen özvektörü de $\begin{bmatrix} - \alpha \\ \beta \end{bmatrix}$ olarak elde ederiz.
$\nu_1 = 1$ değeri sonradan göreceğiz ki Markov Zinciri'nin uzun vadede durağan dağılımını veren özdeğer olacak. $$\lambda^* P = 1 \lambda^* \hspace {1cm} (\lambda^* \hspace{0.2cm} \text{durağan dağılım})$$
$P$'nin $n$. kuvvetini alabilmek için orthogonalleştirmeye çalışıyorduk. Bunun için $M$, $M^{-1}$ ve $D$ matrislerini oluşturmamız gerekiyor: $$ P = M D M^{-1}$$
$M$ matrisi kolonları $P$'nin özvektörleri, $D$ matrisi de $P$'nin özdeğerlerini köşegenlerinde bulunduran matris; $M^{-1}$ de $M$ matrisinin tersi.
$$M = \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \hspace{0.5cm} D = \begin{pmatrix} 1 &0 \\ 0 & 1- \alpha - \beta \end{pmatrix}\hspace{0.5cm} M^{-1} = \frac{1}{\beta + \alpha} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix}$$
$$P^n = (M D M^{-1})^n = M D^n M^{-1} = \frac{1}{\alpha + \beta} \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \begin{pmatrix} 1^n &0 \\ 0 & (1- \alpha - \beta)^n \end{pmatrix} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix} \\~\\ \\~\\ P^n= \frac{1}{\alpha + \beta}\begin{pmatrix} \beta + \alpha(1-\alpha-\beta)^n & \alpha - \alpha (1-\alpha-\beta)^n \\ \beta - \beta(1-\alpha-\beta)^n & \alpha + \beta(1-\alpha-\beta)^n \end{pmatrix} $$
İlgilendiğimiz soru, büyük $n$ değerleri için ($n \to \infty$) $P^n$ matrisinin nasıl davranacağı. $n$'i sonsuza götürdüğümüzde matriste parantez içindeki üslü terimler sıfıra gidecekler çünkü $(1 - \alpha + \beta) \in (-1, 1).$ $$\lim_{n\to\infty} P^n = \begin{pmatrix} \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \\ \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \end{pmatrix} = P^{\infty}$$
Bu limite bakarak belirli bir zaman geçtikten sonra, durumlar arasındaki geçişlerin dengeye oturacağını ve geçiş olasılıklarının sabitleneceğini görüyoruz. Bu durum $n \to \infty$ için Markov zincirinin bir durağan dağılıma erişiyor olmasıyla da ilişkili. İleriki bölümlerde buna da detaylıca değineceğiz.
Zincirin geçiş matrisi $P$'yi şu şekilde yazabiliriz: $$ \begin{pmatrix} 1- \alpha & \alpha \\ \beta & 1 - \beta \end{pmatrix}$$
$\alpha, \beta \in (0,1)$. Geçiş matrisini başlangıç olasılık dağılımı ($\lambda_0$) ile çarparak bir sonraki adımlardaki dağılımları elde ediyoruz. $$ P \lambda_0 = \lambda_1 \\ P \lambda_1 = \lambda_2 = P^2 \lambda_0 \\ ... \\ P^n \lambda_0 = \lambda_n $$
$P^n$ matrisinin büyük $n$ değerleri için nasıl davranacağını anlamak için, $P$'yi orthogonalize edip özdeğer (eigenvalue) ve özvektörlerini (eigenvecor) bulalım.
$$\text{det} (P - \nu \mathbb{I}) = \begin{vmatrix} 1- \alpha - \nu & \alpha \\~\\ \beta & 1 - \beta - \nu \end{vmatrix} = 0 \\~\\ (1- \alpha - \nu) (1 - \beta - \nu) -\alpha \beta = 0 \\~\\ \nu_{1,2} = \frac{2 - \alpha - \beta \pm (\alpha + \beta)}{2}$$
Bu denklemlerden iki özdeğeri $\nu_1 = 1$, karşılık gelen özvektörü $\begin{bmatrix} 1 \\ 1 \end{bmatrix} $ ve $\nu_2 = 1- \alpha - \beta$, karşılık gelen özvektörü de $\begin{bmatrix} - \alpha \\ \beta \end{bmatrix}$ olarak elde ederiz.
$\nu_1 = 1$ değeri sonradan göreceğiz ki Markov Zinciri'nin uzun vadede durağan dağılımını veren özdeğer olacak. $$\lambda^* P = 1 \lambda^* \hspace {1cm} (\lambda^* \hspace{0.2cm} \text{durağan dağılım})$$
$P$'nin $n$. kuvvetini alabilmek için orthogonalleştirmeye çalışıyorduk. Bunun için $M$, $M^{-1}$ ve $D$ matrislerini oluşturmamız gerekiyor: $$ P = M D M^{-1}$$
$M$ matrisi kolonları $P$'nin özvektörleri, $D$ matrisi de $P$'nin özdeğerlerini köşegenlerinde bulunduran matris; $M^{-1}$ de $M$ matrisinin tersi.
$$M = \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \hspace{0.5cm} D = \begin{pmatrix} 1 &0 \\ 0 & 1- \alpha - \beta \end{pmatrix}\hspace{0.5cm} M^{-1} = \frac{1}{\beta + \alpha} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix}$$
$$P^n = (M D M^{-1})^n = M D^n M^{-1} = \frac{1}{\alpha + \beta} \begin{pmatrix} 1 & \alpha \\ 1 & \beta \end{pmatrix} \begin{pmatrix} 1^n &0 \\ 0 & (1- \alpha - \beta)^n \end{pmatrix} \begin{pmatrix} \beta & \alpha \\ -1 & -1 \end{pmatrix} \\~\\ \\~\\ P^n= \frac{1}{\alpha + \beta}\begin{pmatrix} \beta + \alpha(1-\alpha-\beta)^n & \alpha - \alpha (1-\alpha-\beta)^n \\ \beta - \beta(1-\alpha-\beta)^n & \alpha + \beta(1-\alpha-\beta)^n \end{pmatrix} $$
İlgilendiğimiz soru, büyük $n$ değerleri için ($n \to \infty$) $P^n$ matrisinin nasıl davranacağı. $n$'i sonsuza götürdüğümüzde matriste parantez içindeki üslü terimler sıfıra gidecekler çünkü $(1 - \alpha + \beta) \in (-1, 1).$ $$\lim_{n\to\infty} P^n = \begin{pmatrix} \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \\ \frac{\beta}{\alpha+\beta} & \frac{\alpha}{\alpha+\beta} \end{pmatrix} = P^{\infty}$$
Bu limite bakarak belirli bir zaman geçtikten sonra, durumlar arasındaki geçişlerin dengeye oturacağını ve geçiş olasılıklarının sabitleneceğini görüyoruz. Bu durum $n \to \infty$ için Markov zincirinin bir durağan dağılıma erişiyor olmasıyla da ilişkili. İleriki bölümlerde buna da detaylıca değineceğiz.
29 Ocak 2018 Pazartesi
Discrete Stochastic Processes - I
Matematik Köyü'nde Kış döneminde takip ettiğim Arif Mardin hocanın 'Discrete Stochastic Processes' dersinin notlarnı gün gün tutmaya çalışıyorum. Elimdeki notlardan kendi anladığım şekliyle burada da bir seri şeklinde kısa kısa yazmayı planlıyorum. İlk yazı ile başlayalım o halde.
İlk derse 'Basit Rastgele Yürüyüş' (Simple Random Walk) ile başladık ve sonrasında onun Markov özelliklerinden yola çıkarak Markov Zincir'lerini inceledik. Rastgele yürüyüşü elindeki bir miktar parası olup, kumar masasında her oyunda $p$ olasılıkla parasını $1$ arttıran, $1-p$ olasılıkla da 1 azaltan bir kumarbazın durumu için değerlendirebiliriz. Bu durumda $n$ oyun/adım sonrasında kumarbazın elindeki parayı şu şekilde yazabiliriz: $$S_n = S_0 + \sum_{i = 1}^n X_i$$ Burada $S_0$ başlangıçtaki para ve $X_i$'ler de her oyunda kazanıp kaybettiğimiz parayı gösteren rassal değişken. $X_i$ rassal değişkeni yalnızca $+1$ ve $-1$ değerleri alabilen bir 'Bernouilli rassal değişkeni'. $X_0, X_1, ... , X_n$ serisi $p$ olasılıkla $+1$, $1-p$ olasılıkla da $-1$ değerleri alabilen Bernoulli rassal değişkenlerinden oluşan bir dizidir.
Bu tip basit bir kurala dayalı olarak kurgulanmış bu oyuna dair birçok ilginç soru sorulabilir. Örneğin:
- $n$ oyun sonrasında ne kadar kazanmayı bekleriz?
- Kazancımızın ya da kaybımızın yeteri kadar oynadığımızda sonsuz olmasını bekler miyiz? Hangi koşulda böyle bir durum oluşur?
- Herhangi bir zamanda cebimizdeki bir para değerine sonra tekrar dönmeyi bekler miyiz? Kaç kere döneriz? Bu durum tüm para değerleri için gerçekleşir mi?
Rastgele yürüyüş problemi bunlar gibi birbirinden ilginç ve çoğu zaman çözümü epey uğraştırıcı birçok probleme kaynaklık yapıyor. İlerleyen zamanda daha detaylıca inceleyeceğiz. Birkaç özelliğine göz atalım şimdi.
Lemma 1: Basit rastgele yürüyüş uzayda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_ n = j +b | S_0 = a+b)$$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}(S_n = j +b | S_0 = a + b)$
Lemma 2: Basit rastgele yürüyüş zamanda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_{n+m} = j | S_m= a) $$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}( \sum_{i = m+1}^{m+n} X_i = j - a) = \mathbb{P}(S_{n+m} = j | S_m = a)$
Lemma 3 (Markov Özelliği): Rastgele yürüyüşün belirli bir andan sonraki adımları sadece bulunduğu adımdan bir önceki adımına bağlıdır, ondan öncekilerden tamamen bağımsızdır. $$\mathbb{P} = (S_{m+n} = j | S_0,S_1, ..., S_m) = \mathbb{P}(S_{m+n} = j | S_m)$$ Yukarıdaki şartlı olasılık ifadesindeki $S_0,S_1, ..., S_m$, 0. adımda $S_0$, 1. adımdaki $S_1$, $...$ m. adımda $S_m$ olayının gerçekleştiğini gösteriyor. Rastgele yürüyüş'ün bu özelliği ona birçok ilginç davranış kazandırıyor. Bunları anlayabilmek için öncelikle Markov Zincir'lerine kısaca bir göz atalım.
MARKOV ZİNCİRLERİ
Belirli bir sayılabilir (countable) durumu barındıran bir 'durum uzayı' $\mathcal{S}$ üzerinde tanımlı, bu durumları $n$ ile gösterilen adımlarda dolaşan bir proses olarak tanımlayabiliriz.
$\mathbb{X} = (X_n, n \in \mathbb{N}$, $\mathcal{S}$'den değerler alan birer rassal değişkenler dizisi olsun.
Tanım: $\mathbb{X}$ dizisi tüm $\forall n \in \mathbb{N}$ ve $\forall i_0, i_1, ..., i_n \in \mathcal{S}$ için Markov özelliği $$ \mathbb{P} (X_{n+1} = i_{n+1} | X_0 = i_0, X_1= i_1, ... , X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} | X_n = i_n)$$ sağlıyorsa Markov Zinciri (Markov Chain - MC) olarak adlandırılır.
Markov Zinciri eğer $\forall i, j \in \mathcal{S}$ için $\mathbb{P} ( X_{n+1} = j|X_n = 1)$ $n$'e bağlı değilse homojen olarak adlandırılır.
Olasılıkları hesaplamak için iki şeyi bilmemiz gerekir:
a) Geçiş matrisi (Transition Matrix) $P = (p_{ij} \hspace{0.5cm} i,j \in \mathcal{S})$ aşağıdaki gibi verilir: $$ P_{ij} = \mathbb{P}(X_1 = j| X_0 = i)$$
b) Başlangıç olasılık dağılımı $\lambda = (\lambda_i, i \in \mathcal{S})$
Homojenlik varsayımı gereği şunu yazabiliriz: $$\mathbb{P} (X_{n+1} = j | X_n = i) = P_{ij}$$
Önermeler:
a)$\lambda$ vektörü bir olasılık dağılımıdır. $$ \lambda_i \geqslant 0 \hspace{0.5cm} \forall i \in \mathcal{S} \hspace{0.3cm} \text{ve} \sum_{i \in \mathcal{S}}\lambda_i = 1$$
b) $P = (p_{ij}\hspace{0.3cm}; i,j \in \mathcal{S})$ matrisi bir 'stochastic matris'tir.
i) $P_{ij} \geqslant 0 \forall i,j \in \mathcal{S}$
ii)$\sum_{j \in \mathcal{S}} P_{ij} = 1 \forall i \in \mathcal{S} $ ($P$'nin satır toplamları $1$'e eşit.
Önermelerin kanıtları:
a) $\lambda_i$'ler bir olasılık olduğundan sıfırdan büyük eşit olmalılar. $$\sum_{i \in \mathcal{S}} \lambda_i = \sum_{i \in \mathcal{S} } \mathbb{P} (X_0 = i) = 1 \hspace {1.5cm} \square$$
b)$P_{ij}$'ler olasılık değerleri olduğundan dolayı sıfırdan büyük eşit olmalılar. $$ \sum_{j \in \mathcal{S}}P_{i,j} = \sum_{i \in \mathcal{S}}\mathbb{P} (X_1 = j |X_0 = i) = \mathbb{P}(X_1 \in \mathcal{S} | X_0 = i) = 1 \hspace{1.5cm} \square$$
İlk derse 'Basit Rastgele Yürüyüş' (Simple Random Walk) ile başladık ve sonrasında onun Markov özelliklerinden yola çıkarak Markov Zincir'lerini inceledik. Rastgele yürüyüşü elindeki bir miktar parası olup, kumar masasında her oyunda $p$ olasılıkla parasını $1$ arttıran, $1-p$ olasılıkla da 1 azaltan bir kumarbazın durumu için değerlendirebiliriz. Bu durumda $n$ oyun/adım sonrasında kumarbazın elindeki parayı şu şekilde yazabiliriz: $$S_n = S_0 + \sum_{i = 1}^n X_i$$ Burada $S_0$ başlangıçtaki para ve $X_i$'ler de her oyunda kazanıp kaybettiğimiz parayı gösteren rassal değişken. $X_i$ rassal değişkeni yalnızca $+1$ ve $-1$ değerleri alabilen bir 'Bernouilli rassal değişkeni'. $X_0, X_1, ... , X_n$ serisi $p$ olasılıkla $+1$, $1-p$ olasılıkla da $-1$ değerleri alabilen Bernoulli rassal değişkenlerinden oluşan bir dizidir.
Bu tip basit bir kurala dayalı olarak kurgulanmış bu oyuna dair birçok ilginç soru sorulabilir. Örneğin:
- $n$ oyun sonrasında ne kadar kazanmayı bekleriz?
- Kazancımızın ya da kaybımızın yeteri kadar oynadığımızda sonsuz olmasını bekler miyiz? Hangi koşulda böyle bir durum oluşur?
- Herhangi bir zamanda cebimizdeki bir para değerine sonra tekrar dönmeyi bekler miyiz? Kaç kere döneriz? Bu durum tüm para değerleri için gerçekleşir mi?
Rastgele yürüyüş problemi bunlar gibi birbirinden ilginç ve çoğu zaman çözümü epey uğraştırıcı birçok probleme kaynaklık yapıyor. İlerleyen zamanda daha detaylıca inceleyeceğiz. Birkaç özelliğine göz atalım şimdi.
Lemma 1: Basit rastgele yürüyüş uzayda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_ n = j +b | S_0 = a+b)$$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}(S_n = j +b | S_0 = a + b)$
Lemma 2: Basit rastgele yürüyüş zamanda homojendir. Yani: $$\mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}(S_{n+m} = j | S_m= a) $$
Kanıt: $ \mathbb{P}(S_n = j | S_0 = a) = \mathbb{P}( \sum_i^n X_i = j - a) = \mathbb{P}( \sum_{i = m+1}^{m+n} X_i = j - a) = \mathbb{P}(S_{n+m} = j | S_m = a)$
Lemma 3 (Markov Özelliği): Rastgele yürüyüşün belirli bir andan sonraki adımları sadece bulunduğu adımdan bir önceki adımına bağlıdır, ondan öncekilerden tamamen bağımsızdır. $$\mathbb{P} = (S_{m+n} = j | S_0,S_1, ..., S_m) = \mathbb{P}(S_{m+n} = j | S_m)$$ Yukarıdaki şartlı olasılık ifadesindeki $S_0,S_1, ..., S_m$, 0. adımda $S_0$, 1. adımdaki $S_1$, $...$ m. adımda $S_m$ olayının gerçekleştiğini gösteriyor. Rastgele yürüyüş'ün bu özelliği ona birçok ilginç davranış kazandırıyor. Bunları anlayabilmek için öncelikle Markov Zincir'lerine kısaca bir göz atalım.
MARKOV ZİNCİRLERİ
Belirli bir sayılabilir (countable) durumu barındıran bir 'durum uzayı' $\mathcal{S}$ üzerinde tanımlı, bu durumları $n$ ile gösterilen adımlarda dolaşan bir proses olarak tanımlayabiliriz.
$\mathbb{X} = (X_n, n \in \mathbb{N}$, $\mathcal{S}$'den değerler alan birer rassal değişkenler dizisi olsun.
Tanım: $\mathbb{X}$ dizisi tüm $\forall n \in \mathbb{N}$ ve $\forall i_0, i_1, ..., i_n \in \mathcal{S}$ için Markov özelliği $$ \mathbb{P} (X_{n+1} = i_{n+1} | X_0 = i_0, X_1= i_1, ... , X_n = i_n) = \mathbb{P}(X_{n+1} = i_{n+1} | X_n = i_n)$$ sağlıyorsa Markov Zinciri (Markov Chain - MC) olarak adlandırılır.
Markov Zinciri eğer $\forall i, j \in \mathcal{S}$ için $\mathbb{P} ( X_{n+1} = j|X_n = 1)$ $n$'e bağlı değilse homojen olarak adlandırılır.
Olasılıkları hesaplamak için iki şeyi bilmemiz gerekir:
a) Geçiş matrisi (Transition Matrix) $P = (p_{ij} \hspace{0.5cm} i,j \in \mathcal{S})$ aşağıdaki gibi verilir: $$ P_{ij} = \mathbb{P}(X_1 = j| X_0 = i)$$
b) Başlangıç olasılık dağılımı $\lambda = (\lambda_i, i \in \mathcal{S})$
Homojenlik varsayımı gereği şunu yazabiliriz: $$\mathbb{P} (X_{n+1} = j | X_n = i) = P_{ij}$$
Önermeler:
a)$\lambda$ vektörü bir olasılık dağılımıdır. $$ \lambda_i \geqslant 0 \hspace{0.5cm} \forall i \in \mathcal{S} \hspace{0.3cm} \text{ve} \sum_{i \in \mathcal{S}}\lambda_i = 1$$
b) $P = (p_{ij}\hspace{0.3cm}; i,j \in \mathcal{S})$ matrisi bir 'stochastic matris'tir.
i) $P_{ij} \geqslant 0 \forall i,j \in \mathcal{S}$
ii)$\sum_{j \in \mathcal{S}} P_{ij} = 1 \forall i \in \mathcal{S} $ ($P$'nin satır toplamları $1$'e eşit.
Önermelerin kanıtları:
a) $\lambda_i$'ler bir olasılık olduğundan sıfırdan büyük eşit olmalılar. $$\sum_{i \in \mathcal{S}} \lambda_i = \sum_{i \in \mathcal{S} } \mathbb{P} (X_0 = i) = 1 \hspace {1.5cm} \square$$
b)$P_{ij}$'ler olasılık değerleri olduğundan dolayı sıfırdan büyük eşit olmalılar. $$ \sum_{j \in \mathcal{S}}P_{i,j} = \sum_{i \in \mathcal{S}}\mathbb{P} (X_1 = j |X_0 = i) = \mathbb{P}(X_1 \in \mathcal{S} | X_0 = i) = 1 \hspace{1.5cm} \square$$
21 Ocak 2018 Pazar
Haftanın Makalesi (III): "Simulating Physics with Computers"
"...and I'm not happy with all the analyses that go with just the classical theory, becouse nature isn't classical, dammit, and if you want to make a simulation of nature, you'd better make it quantum mechanical and by golly it is a wonderful problem, because it doesn't look so easy."
Richard P. Feynman
1980'lerin başında bilgisayarda hesaplama ve simulasyona dair fiziğin üstadı Feynman'ın Caltech'de yaptığı bir konuşmaya dayalı klasik bir makale bu haftanın seçimi: "Simulating Physics with Computers". Doğanın en temelde klasik yasaları olarak bildiğimiz klasik fizikten birçok yönden devrimsel olarak ayrılan kuantum mekaniği (ve en genel anlamda kuantum alan teorileri) tarafından açıklanıyor olması, birçok yönden klasik özelliklere sahip görünen bilgisayarlar tarafından benzetiminin (simulasyon) gerçekten yapılıp yapılamayacağı sorununu doğuruyor. Eğer [kuantum mekaniğine dayalı] doğayı tam olarak modelleyip, elimizdeki bilgisayarlarla simule etmek istiyorsak en temelde olasılıkların yattığı farklı tipte bir 'evrensel hesaplayıcıya' ihtiyacımız olduğunu dile getiriyor Feynman makalede.
Makalenin başında, klasik fizikteki uzay ve zamanın, yerel (local), nedensel (causal) ve tersinebilir (reversible) özellikleri dolayısıyla aşina olduğumuz bilgisayarlarda simulasyona elverişli olduğu tartışmasını yürütüyor. Sonrasında bilgisayarlarda olasılığının simulasyonunun nasıl yapılacağına değinip, birden fazla parçacıklı kuantum sistemlerindeki olasılık sayısının çok büyümesiyle ilişkili olarak bu tip bir hesabın mümkün olmayacağını dile getiriyor. (Aklıma, bu duruma Monte Carlo yaklaşımları ile nasıl girişilir acaba? sorusu geliyor...)
Makalenin temel noktası dördüncü bölümde ele aldığı konu, büyük ölçekli kuantum mekanik sistemleri simule etmek için işe yarayacak, tıpkı simule etmeye çalıştığı fenomenler gibi kendisinin de kuantum mekaniğinin prensiplerine dayanan bir evresel hesaplayıcı yani bir 'kuantum bilgisayar'. Bu bölümde kuantum alan teorisinden ödünç aldığı fikirlerle parçacıkların spin özelliklerini kullanarak bu tip sistemler oluşturulabileceğini ifade ediyor ama aralarda birçok belirsizlikler ve boşluklar bırakıyor. Makalenin ilerleyen kısmında klasik bir bilgisayarla kuantum sistemlerinin simule edilemeyeceğinin teknik analizini yapıp ortaya çıkacak problemlerden bahsediyor.
Makalenin sonunda bilgisayarlarla doğanın kendisini birebir simule ederek fiziğe dair yeni birçok şey keşfedeceğimizi ve bu amacın peşinden gidilmeyi fazlasıyla hak ettiğini dile getiriyor Feynman. Günümüzdeki kuantum bilgisayarlar için atılan adımlar ve son zamanlardaki gelişmeler bu fikrin birçok insan tarafından paylaşıldığını gösteriyor. Fizikte her zaman yeni ve farklı yaklaşımları geliştirip çocuk merakı ve kurcalama hissiyle doğaya yaklaştığı bilinen Feynman'ın o dönemde hızla gelişen bilgisayarlarla ilgilenmemesi şaşırtıcı olurdu. Kendisinin ayrıca hesaplamaya dair güzel de bir ders serisi var 'Feynman Lectures on Computation' adında. Kuantum bilgisayarların gündemde olduğu fakat bilinenler çok kısıtlı olması sebebiyle alandaki belirsizliklerin bir o kadar büyük olduğu bir dönemde, bu tip bir bilgisayarın fizik için ne anlam ifadeceğini ele alan, temel kuantum mekaniği bilgisiyle okunabilecek güzel bir makale.
Makaleyi okumak için: "Simulating Physics with Computers"(PDF)
Makale üzerine açıklamalara ve detaylı incelemeye yer veren şu makaleyi de tavsiye ederim: 'Richard Feynman: Simulating Physics with Computers' (M.Demmer ve ark.)
15 Ocak 2018 Pazartesi
Yazı-Tura atmak ne kadar rastlantısaldır?
*Geçmişte GökGünce'de yayınladığım favori yazılarımdan birini buraya aktarmak istedim; öncesinde görmeyenler için iyi okumalar!
Matematik ve fizikte bazı şeyleri günlük hesaplamalarda veya daha karmaşık kavramları temellendirmek için kullandığımızda, çoğu zaman ‘aşikarlığını’ sorgulamadan, içgüdüsel olarak belki de ‘daha başka ne olabilirdi ki?’ diyerek yolumuza devam ederiz. Fizikte yüksek lisans/doktora seviyesinde bir takım şeyleri kavramaya çalışma sürecimde nedense bahsettiğim ‘aşikar' şeyleri anlamak için özel bir çaba sarf etmem gerektiğini hissediyorum son zamanlarda. Tıpkı yakın zamanda karşılaştığım ve sonucunu gördüğümde sandalyemden az kalsın düşe yazdığım basit kavram gibi: ‘yazı-tura atmak gibi mekanik bir süreç ne kadar veya neden rastlantısaldır?’.
Fizikte en sevdiğim şey olabildiğince karmaşık görünen olguları çok basit modeller yardımıyla ‘karikatürünü çizmek’, ardından bunu belli varsayımlar altında çözüp gerçek durum hakkında yorumlar yapmak. Yazı-tura atışına baktığımızda bu mekanik süreci etkileyen birçok karmaşık süreçten bahsedebiliriz. Örneğin hava direnci, kütle-çekimi, paranın düştüğü yüzeyin esnekliği, ilk hız (hem yukarı doğru olan doğrusal hız, hem de dönmeyle ilişkili açısal hız), cismin kütle dağılımı vs vs.. Bir takım akla uygun basitleştirmeler ve kontrol edilebildiğini düşündüğümüz bir deney ortamı kullanarak hava direncinin, yüzey esnekliğinin ve kütle dağılımının temel modelimiz için çok da önemli olmadığını söyleyebiliriz. Geriye kalan, yukarı doğru olan doğrusal $v$ hız ve açısal $\omega$ hızının hemen hemen tüm dinamiği belirlediğini göreceğiz.
Modelimizi aşağıdaki gibi kurarsak: parayı, attığımızda doğrusal hızı sayesinde belirli bir yüksekliğe kadar çıkıp, aynı seviyede bekleyen elimize düşeceğini düşünüyoruz. Bunu yaparken bir taraftan da atış sırasında verdiğimiz ilk $\omega$ açısal hızıyla para dönüyor..
Paramızın iki yüzü var: H: Heads (Yazı), T: Tails (Tura). Paranın ilk $v$ hızı etkisiyle yapacağı hareket bariz bir 'dikey atış problemi' ve ilk baştaki yüksekliğini $y(0)$ ve açısal konumu $\theta(0)$'ı sıfır olarak kabul edip, $\tau$ kadar zaman sonra aynı yüksekliğe geri geldiğini, bu süreçte de yatay olarak harekete başlayan $(\theta(0) = 0)$ paranın $\tau$ süre sonra açısal konumu(oryantasyonu) $\theta(\tau)$ olacağını söyleyebiliriz. Buradaki $\theta$ paranın açısal olarak aldığı yola karşılık geliyor ve örneğin bir saniyede 1 dönüş yapan bir para için açısal hız 360°/s veya açıyı radyan cinsinden ölçtüğümüzde $2 \pi$ $ rad/s$ olduğunu söylüyoruz (Fizikte açı hesabında genelde radyan kullanılır). Paranın havada kalma süresinin lise matematiğiyle $$\tau = \frac{2v}{g}$$ olduğunu söyleyebiliriz. Bu sürede paranın ne kadar yol aldığını ise $$\theta(\tau) = \omega \tau = \omega \frac{2v}{g}$$ olarak buluruz. Buradan yola çıkarak ilk baştaki parametrelerimiz olan $v$ ve $\omega$ arasında temel bir ilişki olduğunu kolaylıkla görebiliriz: $$\omega v = \frac{\theta g}{2}$$ Fiziksel bir sistemin dinamiğini anlamak için öncelikle kritik noktalar dediğimiz sistemin davranışının kırıldığı (değiştiği), hassas noktalardaki durumları inceleriz. Bu problemde bu noktalar paranın dik konumda olduğu yani $\theta$ açısının sırasıyla 90°, 270°, 450°, 630°'ye radyan olarak karşılık gelen $$\frac{\pi}{2}, \frac{3 \pi}{2}, \frac{5 \pi}{2}, \frac{7 \pi}{2}... $$ olduğu durumlara bakalım.
Bu durumlar için yukarıda bahsettiğimiz ilk koşullar arasındaki ilişki, yani $\omega$$v$ çarpımı sırasıyla şöyle olacak: $$\frac{\pi g}{4}, \frac{3 \pi g}{4}, \frac{5 \pi g}{4}, \frac{7 \pi g}{4} ... $$Bu değerlere karşılık gelen $\omega$ ve $v$ değerlerini görmek için bir grafik çizersek şöyle bir şey elde ederiz:
Grafiğin yatay ekseni parayı yukarı attığımız doğrusal hız $v$'yi, dikey eksen de açısal hız $\omega$'yı gösteriyor. Attığımız paranın sadece $\frac{\pi}{2}$ kadar yol aldığı durumda yani yalnızca dörtte bir tur atarak elimize düşdüğü durum $\theta (\tau) = \frac{\pi}{2}$ hiperbolik eğrisini tanımlıyor ve tam eğri üzerindeki $\omega$ ve $v$ değerleri bize 'dik düşen' parayı veriyorlar. Parametreleri bu kadar hassas ayarlayarak fiziksel olarak bu eğri üzerine düşmemiz çok çok güç. O yüzden eğrinin dışındaki bölgeye bakalım: eğrinin hemen altındaki doğrusal ve açısal hız değerleri dönüşün $\frac{\pi}{2} $'den (90°) daha az olduğu, (ilk başta sıfır dereceden başladığımızı düşünürsek) başta başladığımız yüz yine üstte kalacak şekilde elimize düşeceğini, yani sonucun Heads - H olacağını; eğrinin üstü ise $\theta$ açısı $\frac{3 \pi}{2}$ (270°) olana dek paranın ters yüzü yani Tails - T'nin elimize düşeceğini söylüyor. Her bir dik gelme durumu olan $\theta(\tau) = \frac{3 \pi}{2}, \frac{5 \pi}{2}, \frac{7 \pi}{2} ...$ değerlerini de aynı grafiğin üzerine çizersek aşağıdaki gibi bir resim karşımıza çıkıyor.
Pembe renkli bölgelerdeki ilk hızlara karşılık olarak paramız Yazı (Heads), beyaz bölgelerdeki parametrelere karşılık da paramız Tura (Tails) geliyor. O zaman problem çözüldü, dağılabiliriz! Bu sonucu gördüğümde ilk aklıma gelen soru: "Nasıl yani? Madem olayı mekanik olarak bu kadar basit bir şekilde çözebiliyoruz ve başlangıçta verdiğim ilk hız değerlerine göre paranın yazı mı yoksa tura mı geleceğini bilebiliyorum, o zaman 'olasılık' veya 'rastlantısallık' bunun neresinde?" Elde ettiğimiz resim her ne kadar çok temiz ve açıklayıcı görünse de aslında 'şeytan detaylarda saklı'.
Yukarıdaki grafikte yatay eksendeki değerlere baktığımızda 1 m/s'den 15 m/s'ye kadar değişen değerleri görüyoruz. Dikey eksen de 1 radyan/s dönüş hızından, 15 radyan/s dönüşe kadar uzanıyor. Peki tipik bir yazı tura atışında biz paraya ne kadar bir hız veriyoruz? Bu işin üstadı Persi Diaconis'in yaptığı deneyler göstermiş ki verilen doğrusal hız ($v$) tipik olarak 2-3 m/s arasında yani grafikte görebildiğimiz aralıkta. Fakat verdiğimiz açısal hız ise saniyede 36-39 dönüş (radyan olarak 225-250 radyan/s) kadar yüksek bir hız; dolayısıyla fiziksel olarak gerçekleşen parametrelerin değerini yukarıdaki grafikte göremiyoruz. O zaman ölçeği büyütelim, öyle bakalım:
Kırmızı kutuyla gösterilen bölge tipik olarak bir yazı tura atışında elimizle paraya verdiğimiz 2-3 m/s doğrusal hız ile saniyede 225-250 radyan dönüş açısal hız aralığında sistemin nasıl davrandığını gösteren bölge. Gri bölgeler yazı, beyaz alanlar tura gelme durumunu veren parametre bölgeleri. Bu aralığa biraz daha yaklaşalım:
Gördüğünüz gibi yazı ve tura bölgeleri oldukça dar bantlar şeklinde birbirini takip ediyor. Doğrusal hızdaki 0.1 m/s'lik bir değişim dahi parayı gri olan yazı bandından çıkarıp beyaz- tura bandına geçirebiliyor. Sonucun doğrusal hızdaki değişime bağımlılığı açısal hıza bağımlılığından çok daha hassas. Yeşil ok ile gösterilen açısal hassasiyet, yani diğer banda geçmemize neden olan karakteristik değişiklik, kırmızıyla gösterilen doğrusal hassasiyetten daha az etkili. Bu resme bakarak aslında olay açıklığa kavuşuyor: Parayı attığımızda her seferinde elimizle kontrol edemediğimiz başlangıç hızındaki rastlantısal değişiklikler sonunda kendisini tamamen rastlantısal bir sonuç veren bir sürece neden oluyor. İlk hıza bu kadar hassas bir sistemin sonunda yazı mı yoksa tura mı geleceğini kesin olarak söyleyemeyip bunun rastlantısal bir süreç olarak tarif ediyoruz.
Konuyu yukarıda epey kabaca tanımladık aslında. Bunun altında çok derin matematiksel kavramlar yatıyor diyebilirim. Başlangıç koşullarının zamanla ortadan silinip, sistemi 'rastlantısal' bir sisteme dönüştüren bir takım mekanizmalar iş başında aslında, ki bunları ilk olarak 19. yy'ın sonunda ünlü Fransız deha Henri Poincaré incelemiş. Ardından bu süreçlerin altında yatan fiziğe dair 1905'de Einstein'ın 'Brownian Motion' makalesi var. Fakat belki de en ilginci, yazı-tura probleminin bu kadar basi bir mekanik modelinin kurulup incelenmesi için 1986 yılına kadar beklemek gerekmiş... Diğer hepsine tamam da işte buna hayret etmemek elde değil!
Konuyla ilgili ileri okumalar yapmak isteyenlere:
1986'da yayınlanan ilgili makale: J. B. Keller. (1986) The probability of heads, American Mathematical Monthly, 93:191-197
Persi Diaconis'in konuyla ilgili müthiş konuşması: The Search for randomness
Numberphile'da yine P. Diaconis ile yapılan güzel bir video: 'How random is a coin toss?'
*Yazıda kullanılan grafik ve görseller Coursera'daki (artık yayında olmayan) Dr. Santosh S. Venkatesh'in müthiş olasılık dersi Probability'nin ders notlarından alınmıştır. Kitabı için: The Theory of Probability Explorations and Applications (Cambridge Press)
"Bir şeyi dünyadaki en aşikâr şey olarak görmeye başladığımızda, bunu anlamak için sarf edeceğimiz tüm çabayı bir kenara iteriz..." Bertolt Brecht
Matematik ve fizikte bazı şeyleri günlük hesaplamalarda veya daha karmaşık kavramları temellendirmek için kullandığımızda, çoğu zaman ‘aşikarlığını’ sorgulamadan, içgüdüsel olarak belki de ‘daha başka ne olabilirdi ki?’ diyerek yolumuza devam ederiz. Fizikte yüksek lisans/doktora seviyesinde bir takım şeyleri kavramaya çalışma sürecimde nedense bahsettiğim ‘aşikar' şeyleri anlamak için özel bir çaba sarf etmem gerektiğini hissediyorum son zamanlarda. Tıpkı yakın zamanda karşılaştığım ve sonucunu gördüğümde sandalyemden az kalsın düşe yazdığım basit kavram gibi: ‘yazı-tura atmak gibi mekanik bir süreç ne kadar veya neden rastlantısaldır?’.
Fizikte en sevdiğim şey olabildiğince karmaşık görünen olguları çok basit modeller yardımıyla ‘karikatürünü çizmek’, ardından bunu belli varsayımlar altında çözüp gerçek durum hakkında yorumlar yapmak. Yazı-tura atışına baktığımızda bu mekanik süreci etkileyen birçok karmaşık süreçten bahsedebiliriz. Örneğin hava direnci, kütle-çekimi, paranın düştüğü yüzeyin esnekliği, ilk hız (hem yukarı doğru olan doğrusal hız, hem de dönmeyle ilişkili açısal hız), cismin kütle dağılımı vs vs.. Bir takım akla uygun basitleştirmeler ve kontrol edilebildiğini düşündüğümüz bir deney ortamı kullanarak hava direncinin, yüzey esnekliğinin ve kütle dağılımının temel modelimiz için çok da önemli olmadığını söyleyebiliriz. Geriye kalan, yukarı doğru olan doğrusal $v$ hız ve açısal $\omega$ hızının hemen hemen tüm dinamiği belirlediğini göreceğiz.
Modelimizi aşağıdaki gibi kurarsak: parayı, attığımızda doğrusal hızı sayesinde belirli bir yüksekliğe kadar çıkıp, aynı seviyede bekleyen elimize düşeceğini düşünüyoruz. Bunu yaparken bir taraftan da atış sırasında verdiğimiz ilk $\omega$ açısal hızıyla para dönüyor..
Paramızın iki yüzü var: H: Heads (Yazı), T: Tails (Tura). Paranın ilk $v$ hızı etkisiyle yapacağı hareket bariz bir 'dikey atış problemi' ve ilk baştaki yüksekliğini $y(0)$ ve açısal konumu $\theta(0)$'ı sıfır olarak kabul edip, $\tau$ kadar zaman sonra aynı yüksekliğe geri geldiğini, bu süreçte de yatay olarak harekete başlayan $(\theta(0) = 0)$ paranın $\tau$ süre sonra açısal konumu(oryantasyonu) $\theta(\tau)$ olacağını söyleyebiliriz. Buradaki $\theta$ paranın açısal olarak aldığı yola karşılık geliyor ve örneğin bir saniyede 1 dönüş yapan bir para için açısal hız 360°/s veya açıyı radyan cinsinden ölçtüğümüzde $2 \pi$ $ rad/s$ olduğunu söylüyoruz (Fizikte açı hesabında genelde radyan kullanılır). Paranın havada kalma süresinin lise matematiğiyle $$\tau = \frac{2v}{g}$$ olduğunu söyleyebiliriz. Bu sürede paranın ne kadar yol aldığını ise $$\theta(\tau) = \omega \tau = \omega \frac{2v}{g}$$ olarak buluruz. Buradan yola çıkarak ilk baştaki parametrelerimiz olan $v$ ve $\omega$ arasında temel bir ilişki olduğunu kolaylıkla görebiliriz: $$\omega v = \frac{\theta g}{2}$$ Fiziksel bir sistemin dinamiğini anlamak için öncelikle kritik noktalar dediğimiz sistemin davranışının kırıldığı (değiştiği), hassas noktalardaki durumları inceleriz. Bu problemde bu noktalar paranın dik konumda olduğu yani $\theta$ açısının sırasıyla 90°, 270°, 450°, 630°'ye radyan olarak karşılık gelen $$\frac{\pi}{2}, \frac{3 \pi}{2}, \frac{5 \pi}{2}, \frac{7 \pi}{2}... $$ olduğu durumlara bakalım.
Bu durumlar için yukarıda bahsettiğimiz ilk koşullar arasındaki ilişki, yani $\omega$$v$ çarpımı sırasıyla şöyle olacak: $$\frac{\pi g}{4}, \frac{3 \pi g}{4}, \frac{5 \pi g}{4}, \frac{7 \pi g}{4} ... $$Bu değerlere karşılık gelen $\omega$ ve $v$ değerlerini görmek için bir grafik çizersek şöyle bir şey elde ederiz:
Grafiğin yatay ekseni parayı yukarı attığımız doğrusal hız $v$'yi, dikey eksen de açısal hız $\omega$'yı gösteriyor. Attığımız paranın sadece $\frac{\pi}{2}$ kadar yol aldığı durumda yani yalnızca dörtte bir tur atarak elimize düşdüğü durum $\theta (\tau) = \frac{\pi}{2}$ hiperbolik eğrisini tanımlıyor ve tam eğri üzerindeki $\omega$ ve $v$ değerleri bize 'dik düşen' parayı veriyorlar. Parametreleri bu kadar hassas ayarlayarak fiziksel olarak bu eğri üzerine düşmemiz çok çok güç. O yüzden eğrinin dışındaki bölgeye bakalım: eğrinin hemen altındaki doğrusal ve açısal hız değerleri dönüşün $\frac{\pi}{2} $'den (90°) daha az olduğu, (ilk başta sıfır dereceden başladığımızı düşünürsek) başta başladığımız yüz yine üstte kalacak şekilde elimize düşeceğini, yani sonucun Heads - H olacağını; eğrinin üstü ise $\theta$ açısı $\frac{3 \pi}{2}$ (270°) olana dek paranın ters yüzü yani Tails - T'nin elimize düşeceğini söylüyor. Her bir dik gelme durumu olan $\theta(\tau) = \frac{3 \pi}{2}, \frac{5 \pi}{2}, \frac{7 \pi}{2} ...$ değerlerini de aynı grafiğin üzerine çizersek aşağıdaki gibi bir resim karşımıza çıkıyor.
Pembe renkli bölgelerdeki ilk hızlara karşılık olarak paramız Yazı (Heads), beyaz bölgelerdeki parametrelere karşılık da paramız Tura (Tails) geliyor. O zaman problem çözüldü, dağılabiliriz! Bu sonucu gördüğümde ilk aklıma gelen soru: "Nasıl yani? Madem olayı mekanik olarak bu kadar basit bir şekilde çözebiliyoruz ve başlangıçta verdiğim ilk hız değerlerine göre paranın yazı mı yoksa tura mı geleceğini bilebiliyorum, o zaman 'olasılık' veya 'rastlantısallık' bunun neresinde?" Elde ettiğimiz resim her ne kadar çok temiz ve açıklayıcı görünse de aslında 'şeytan detaylarda saklı'.
Yukarıdaki grafikte yatay eksendeki değerlere baktığımızda 1 m/s'den 15 m/s'ye kadar değişen değerleri görüyoruz. Dikey eksen de 1 radyan/s dönüş hızından, 15 radyan/s dönüşe kadar uzanıyor. Peki tipik bir yazı tura atışında biz paraya ne kadar bir hız veriyoruz? Bu işin üstadı Persi Diaconis'in yaptığı deneyler göstermiş ki verilen doğrusal hız ($v$) tipik olarak 2-3 m/s arasında yani grafikte görebildiğimiz aralıkta. Fakat verdiğimiz açısal hız ise saniyede 36-39 dönüş (radyan olarak 225-250 radyan/s) kadar yüksek bir hız; dolayısıyla fiziksel olarak gerçekleşen parametrelerin değerini yukarıdaki grafikte göremiyoruz. O zaman ölçeği büyütelim, öyle bakalım:
Kırmızı kutuyla gösterilen bölge tipik olarak bir yazı tura atışında elimizle paraya verdiğimiz 2-3 m/s doğrusal hız ile saniyede 225-250 radyan dönüş açısal hız aralığında sistemin nasıl davrandığını gösteren bölge. Gri bölgeler yazı, beyaz alanlar tura gelme durumunu veren parametre bölgeleri. Bu aralığa biraz daha yaklaşalım:
Konuyu yukarıda epey kabaca tanımladık aslında. Bunun altında çok derin matematiksel kavramlar yatıyor diyebilirim. Başlangıç koşullarının zamanla ortadan silinip, sistemi 'rastlantısal' bir sisteme dönüştüren bir takım mekanizmalar iş başında aslında, ki bunları ilk olarak 19. yy'ın sonunda ünlü Fransız deha Henri Poincaré incelemiş. Ardından bu süreçlerin altında yatan fiziğe dair 1905'de Einstein'ın 'Brownian Motion' makalesi var. Fakat belki de en ilginci, yazı-tura probleminin bu kadar basi bir mekanik modelinin kurulup incelenmesi için 1986 yılına kadar beklemek gerekmiş... Diğer hepsine tamam da işte buna hayret etmemek elde değil!
Konuyla ilgili ileri okumalar yapmak isteyenlere:
1986'da yayınlanan ilgili makale: J. B. Keller. (1986) The probability of heads, American Mathematical Monthly, 93:191-197
Persi Diaconis'in konuyla ilgili müthiş konuşması: The Search for randomness
Numberphile'da yine P. Diaconis ile yapılan güzel bir video: 'How random is a coin toss?'
*Yazıda kullanılan grafik ve görseller Coursera'daki (artık yayında olmayan) Dr. Santosh S. Venkatesh'in müthiş olasılık dersi Probability'nin ders notlarından alınmıştır. Kitabı için: The Theory of Probability Explorations and Applications (Cambridge Press)
14 Ocak 2018 Pazar
Haftanın Makalesi (II): "Statistical Modeling: The Two Cultures"
Bu hafta istatistik ve veri analizi üzerinden iki bakış açısını inceleyen bir makale 'Haftanın Makalesi'nin konusu. Makale için, yazarının bir süre akademide istatistikle uğraştıktan sonra ara verip on yılın üzerinde dışarıda 'gerçek dünya problemleri' üzerine kafa yorup danışmanlık yaptığı, ardından bölüme geri döndüğünde karşılaştığı duruma bir tepki niteliği yazdığı bir yazı demek daha doğru olur belki de. 2001 gibi yakın bir zamanda yayınlandığında belki dönemin istatistikçileri ve belki alternatif olarak bilgisayar bilimcilerini ilgilendiren bir konuya değiniyordu ama günümüzdeki gelişmeleri göz önüne aldığımızda artık hemen hemen tüm bilim alanlarının dert ettiği bir konuya parmak basıyor: model'den yola çıkarak mı yoksa sadece veriden yola çıkarak mı analiz yapacağız?
Makale, başlığında görüldüğü üzere iki tip istatistiksel modelleme kültürü tartışması üzerinden ilerliyor. Birincisi 'Veri Modelleme' (Data Modelling) kültürü. Bu kültürdeki temel yöntem, elimizdeki verinin belirli parametrelere, belirleyici değişkenlere ve rastgele hatayı içeren bir modelden elde edilmiş bağımsız örnekler olduğunu varsayarak ve bu modelin belirli bir model ailesinden olduğu bilgisiyle başlayıp bir takım sonuçlar elde etmek; bu sonuçlardan da bu veriyi oluşturan doğadaki sürecin mekanizmasına dair fikir yürütme. Örneğin veriyi üreten sürecin doğrusal olduğunu varsayan doğrusal ya da lojistik regresyon gibi... İkincisi 'Algoritmik Modelleme' (Algorithmic Modelling) kültürü. Bunda da doğada bir takım girdilere karşı elde edilen çıktıların üretilme mekanizmalarının oldukça karmaşık ve çoğu zaman bilinemeyecek kara kutular olduğunu varsayıp, probleme algoritma perspektifinden yaklaşmak temel yöntem. Çıktıları en iyi üreten ve çalışma mekanizmaları çoğu zaman net bir şekilde yorumlanamayan tipte modelleme şeklinde düşünülebilir. Örneğin günümüzde sıkça duyduğumuz 'yapay sinir ağları' ya da 'karar ağaçları' tipi yapay öğrenme (machine learning) yöntemleri gibi...
Yazar ilk tipten modellemenin çoğu zaman doğadaki mekanizmalarla alakasız ve sonuçları kuşkulu çıkarımlara neden olduğunu ve bu yaklaşımının görüntü işleme, ses tanıma, doğrusal olmayan süreçlerin verileri gibi alanlar için oldukça eksik kaldığını dile getiriyor. Bunun için danışmanlık yaptığı işlerde uğraştığı üç örnek problem üzerinden 'algoritmik modelleme' ile nasıl yaklaşımlar getirdiğini ve bu yaklaşımların standart veri modelleme yaklaşımlarına göre açık ara farklı olduğunu gösteriyor.
Yazarın 'algoritmik modelleme' dediği kültürün tekniklerini çeşitli 'yapay öğrenme' yönemleri oluşturuyor. Günümüzde bu yöntemler elimizin altındaki bilgisayarların işlem gücünün müthiş artışı, özellikle yapay sinir ağlarını eğitmek için oldukça efektif yöntemlerin geliştirilmiş olması ve birçok kanalda 'büyük veri' akışı sebebiyle neredeyse karşı konulamaz bir güce erişmiş durumdalar. Fizik gibi 'veri modelleme' kültürü üzerine inşa edilmiş ve üretilen modelin Ockham'ın Usturası üstrubu gereği yorumlanabilme ölçütü üzerinden değerlendirildiği bir alanda dahi yavaş yavaş kendisine uygulama alanları bulabiliyor. (Durumun geldiği noktayı daha iyi görmek adına geçen sene Science'ın yayınladığı kapak konusu aydınlatıcı olabilir. ) Kısacası yazarın yaklaşın 15 yıl önce vardığı sonuçların en azından şu anda fazlasıyla doğrulandığı ve mevcut "kültür trendini" belirlediği açıkça görülüyor. Elbette bu tip yöntemler oldukça yeniler ve bir takım darboğazlara da sahipler; 'algoritmik kültürün' hızlı yükselişiyle birlikte zaman hangi kültürün baskın çıkacağını gösterecek.
Makaleyi okumak için: Statistical Modelling: Two Cultures (Statist. Sci. Volume 16, Issue 3 (2001), 199-231.)
Makale, başlığında görüldüğü üzere iki tip istatistiksel modelleme kültürü tartışması üzerinden ilerliyor. Birincisi 'Veri Modelleme' (Data Modelling) kültürü. Bu kültürdeki temel yöntem, elimizdeki verinin belirli parametrelere, belirleyici değişkenlere ve rastgele hatayı içeren bir modelden elde edilmiş bağımsız örnekler olduğunu varsayarak ve bu modelin belirli bir model ailesinden olduğu bilgisiyle başlayıp bir takım sonuçlar elde etmek; bu sonuçlardan da bu veriyi oluşturan doğadaki sürecin mekanizmasına dair fikir yürütme. Örneğin veriyi üreten sürecin doğrusal olduğunu varsayan doğrusal ya da lojistik regresyon gibi... İkincisi 'Algoritmik Modelleme' (Algorithmic Modelling) kültürü. Bunda da doğada bir takım girdilere karşı elde edilen çıktıların üretilme mekanizmalarının oldukça karmaşık ve çoğu zaman bilinemeyecek kara kutular olduğunu varsayıp, probleme algoritma perspektifinden yaklaşmak temel yöntem. Çıktıları en iyi üreten ve çalışma mekanizmaları çoğu zaman net bir şekilde yorumlanamayan tipte modelleme şeklinde düşünülebilir. Örneğin günümüzde sıkça duyduğumuz 'yapay sinir ağları' ya da 'karar ağaçları' tipi yapay öğrenme (machine learning) yöntemleri gibi...
Yazar ilk tipten modellemenin çoğu zaman doğadaki mekanizmalarla alakasız ve sonuçları kuşkulu çıkarımlara neden olduğunu ve bu yaklaşımının görüntü işleme, ses tanıma, doğrusal olmayan süreçlerin verileri gibi alanlar için oldukça eksik kaldığını dile getiriyor. Bunun için danışmanlık yaptığı işlerde uğraştığı üç örnek problem üzerinden 'algoritmik modelleme' ile nasıl yaklaşımlar getirdiğini ve bu yaklaşımların standart veri modelleme yaklaşımlarına göre açık ara farklı olduğunu gösteriyor.
Yazarın 'algoritmik modelleme' dediği kültürün tekniklerini çeşitli 'yapay öğrenme' yönemleri oluşturuyor. Günümüzde bu yöntemler elimizin altındaki bilgisayarların işlem gücünün müthiş artışı, özellikle yapay sinir ağlarını eğitmek için oldukça efektif yöntemlerin geliştirilmiş olması ve birçok kanalda 'büyük veri' akışı sebebiyle neredeyse karşı konulamaz bir güce erişmiş durumdalar. Fizik gibi 'veri modelleme' kültürü üzerine inşa edilmiş ve üretilen modelin Ockham'ın Usturası üstrubu gereği yorumlanabilme ölçütü üzerinden değerlendirildiği bir alanda dahi yavaş yavaş kendisine uygulama alanları bulabiliyor. (Durumun geldiği noktayı daha iyi görmek adına geçen sene Science'ın yayınladığı kapak konusu aydınlatıcı olabilir. ) Kısacası yazarın yaklaşın 15 yıl önce vardığı sonuçların en azından şu anda fazlasıyla doğrulandığı ve mevcut "kültür trendini" belirlediği açıkça görülüyor. Elbette bu tip yöntemler oldukça yeniler ve bir takım darboğazlara da sahipler; 'algoritmik kültürün' hızlı yükselişiyle birlikte zaman hangi kültürün baskın çıkacağını gösterecek.
Makaleyi okumak için: Statistical Modelling: Two Cultures (Statist. Sci. Volume 16, Issue 3 (2001), 199-231.)
6 Ocak 2018 Cumartesi
Haftanın Makalesi (I): "Best Practices for Scientific Computing"
Uzun bir süredir tez çalışmalarımda, kendi araştırmalarımda, aldığım derslerin projelerinde ve verdiğim derslerin uygulamalarında bilgisayar kodu yazıyorum. Çoğu zaman fiziksel/bilimsel bir problemi çözmek üzerine olan bu kodların yapısı genelde "günü kurtaran", bir şekilde çalışıp bir sonuç üreten tipte oluyor. Bu haliyle çoğu zaman içinde kendini tekrar eden kod kümeleri barındıran, nerede-ne yaptığı belli olmayan, iyi belgelenmemiş ve başka birisi aldığında bırakın tekrar çalıştırıp aynı sonuçları üretebilmeyi kodu okuyup ne yaptığını dahi anlaşılmayacak kadar karmaşık türde kodlar yazdığını fark ediyor insan. Küçük çaplı çalışmalarda "iş gören" kodlar, problem biraz karmaşıklığında tam bir baş belasına dönüşebiliyor ve o anda artık biraz "iyi alışkanlıklar" (best practices) takip edip hayatı kolaylaştıran yöntem ve araçlara yönelmek durumunda kalınıyor. Bu hafta okuyup kısaca özetleyeceğim G. Wilson ve arkadaşları tarafından 2014'de yayınlanan "Best Practices for Scientific Computing" makalesinin temel fikri de tam olarak bu.
Yazarlar öncelikle bilimsel amaçla yazılan programların bir bilim insanı için başka bir tür "deney aracı" olduğunu ve tıpkı fiziksel bir deney aracı gibi yapılandırılıp, kontrol edilerek dikkatli bir şekilde kullanılması gerektiğini belirterek başlıyorlar. Sonrasında da bilimsel kod yazımında dikkat edilmesi önerilen sekiz maddeyi sıralıyorlar:
1- Yazdığınız kodu bilgisayarlar için değil, insanlar için yazın.
2- Bırakın bilgisayarlar işi yapsın.
3- Değişiklikleri ufak ufak yapın.
4- Kendinizi (ya da başkalarını) tekrar etmeyin.
5- Hatalar için önceden plan yapın.
6- Programı ancak doğru çalıştıktan sonra optimize edin.
7- Tasarım ve amacı dokümante edin, çalışma prensibini değil.
Araştırmalarda bu tip "iyi alışkanlıkları" edinmek için gerekli öğrenme ve bunları uygulama sürelerinin, sonunda elde edilen verimlilik ile fazlasıyla karşılandığı belirtiliyor. Makalenin başında tıpkı laboratuardaki deneylerde olduğu gibi standartları birebir uygulamanın her zaman mümkün olmadığını ve bu alışkanlıkların hepsini bir anda uygulamaya çalışmaktansa teker teker çalışma rutinlerine entegre edilmesi gerektiğini ifade ediyorlar.
Yazarlar öncelikle bilimsel amaçla yazılan programların bir bilim insanı için başka bir tür "deney aracı" olduğunu ve tıpkı fiziksel bir deney aracı gibi yapılandırılıp, kontrol edilerek dikkatli bir şekilde kullanılması gerektiğini belirterek başlıyorlar. Sonrasında da bilimsel kod yazımında dikkat edilmesi önerilen sekiz maddeyi sıralıyorlar:
1- Yazdığınız kodu bilgisayarlar için değil, insanlar için yazın.
- Yazılan kodu başkalarının veya özellikle gelecek bir zamanda kendisinin anlayabilmesi için insanların anlık hafızalarının kısıtlılığı, örüntü tanıma becerilerinin hassas bir şekilde ayarlanmış olduğu ve dikkat sürelerinin kısa oluşunu göz önüne alarak yazmak gerektiği vurgulanıyor. Bunun için verilen temel öneri kodu tıpkı bir makaledeki bölümler gibi, belirli amaçlar için oluşturulmuş fonksiyonlara bölmek.
- Programda kullanılan isim ve etiketleri ayırdedilebilir, tutarlı ve anlamlı bir şekilde vermeli.
- Kodun her bölümünde stil ve formatı koruyarak ilerlemeli.
2- Bırakın bilgisayarlar işi yapsın.
- Gerçekleştirilmesi hedeflenen prosedürü tekrar tekrar elle yapmak yerine bir script ile çalıştırılacak komutları otomatize etmeyi ve "build tool"lar kullanmayı öneriyorlar.
3- Değişiklikleri ufak ufak yapın.
- Küçük adımlarla, sık sık geri bildirim alarak düzenlemeler yapıp ilerlemeyi öneriyorlar. Her iterasyonda çalışan bir program yazmak amaç ve her iterasyondaki değişiklikleri kaydedip gerektiğinde geriye almak için de GitHub gibi versiyon kontrol sistemleri kullanmayı öneriyorlar.
4- Kendinizi (ya da başkalarını) tekrar etmeyin.
- Bu prensip hem veri için hem de kod için geçerli. Sistemdeki her bir verinin tek bir temsili bulunması gerek; yani kodun bir yerinde değişiklik yapıldığında bu değişiklik tüm her yere paralel olarak yansıması gerek.
- Kopya-yapıştır yapmak yerine kodu modüler hale getirmek, fonksiyonlar ve class'lar ile ilerlemek en sağlıklısı.
5- Hatalar için önceden plan yapın.
- Hatalar kaçınılmaz, sadece onlara karşı "hazırlıklı" olmak gerekiyor. Bunun için "savunmacı programlama" yöntemi geliştirmeyi öneriyorlar. Kodun içine yanlış gitmesi muhtemel durumları kontrol amaçlı "assertion"lar ekleyip gerektiği durumda müdehale etmek gerekiyor. Assertion'lar program içinde örneğin belirli değişkeni, bir fonksiyon çıktısını kontrol edip programın devamını sağlayan mantıksal ifadeler. Bu ifadeleri kullanmanın kodun bölümlerine açıklama yazmaktan daha fazla anlaşılırlık kattığını söylüyorlar.
- Otomatik testler uygulamak için standart test kütüphaneleri kullanmayı ve bugları bulmak için sembolik debugger'lar kullanmayı öneriyorlar.
6- Programı ancak doğru çalıştıktan sonra optimize edin.
- Araştırmalarda kod yazan kişilerin kullandıkları dilden bağımsız olarak birim zamanda neredeyse aynı satır sayısında kod yazdığını gözlemişler. Buradan yola çıkarak kodu öncelikle daha az satır kodla yazılabilecek Python, R gibi "yüksek-seviyeli" dillerde prototipleyip ardından daha iyi performans için C, Java gibi düşük seviye dillere geçmeyi öneriyorlar.
7- Tasarım ve amacı dokümante edin, çalışma prensibini değil.
- Yazılan kodu açıklamak için bir paragraf adım adım nasıl çalıştığını anlatmak yerine, kullanılan arayüzleri açıklayıp amaç ve nedenlerini açıklamak gerektiğini vurguluyorlar. Nasıl çalıştığının adım adım anlatılması gereken kodun tekrar geri dönülüp buna ihtiyaç kalmayacak şekilde tekrar düzenlenmesi gerektiğini söylüyorlar.
- Dokümantasyonu yazılımın içine gömmeyi öneriyorlar ayrı bir yerde tutmak yerine (örneğin Jupyter Notebook'larda olduğu gibi); böylece program başkaları tarafından modifiye edildiğinde paralel olarak dokumantasyonun da güncellenebileceğini ekliyorlar.
8- Birlikte çalışın.
- Yazılan programları proje üzerine çalışan kişiler arasında incelenip, gözden geçirilmesini öneriyorlar. Hatayı çok daha aza indirmek için aynı kod üzerinde beraber çalışmayı öneriyorlar.
Bu yazıyı okuyup, konuyla uğraşan kişilerin bu tip "iyi alışkanlıklar" önerileri varsa da duymayı çok isterim!
Makaleyi okumak için: "Best Practices for Scientific Computing" (PLOS Biology - Open Access)
Kaydol:
Kayıtlar (Atom)