Stochastic Processes - IV Polya Teoremi

Notların dördüncü bölümünde Markov Zincir'lerinin birkaç özelliğinden daha bahsedip ilk notlarda konuyu açtığımız 'Basit Rastgele Yürüyüş' modeline geri dönüp Polya Teoremini gösterip epey ilginç sonuçlar elde edeceğiz. Öncelikle Markov Zincir'lerine dair birkaç tanım daha yapalım.

$\mathbb{X}$ yine $\mathcal{S}$ durum uzayına ve $P$ geçiş matrisine sahip bir Markov Zinrici olsun. Markov zinciri zamanla bir durumdan diğerine $P$'de verilen olasılıklarla geçiyor. Herhangi bir $j$ durumundan ilk kez geçtiği zamana 'ilk geçiş zamanı' olarak adlandıracağız ve bu zaman aşağıdaki gibi tanımlıyoruz:
$$T_j = min \{n \in\mathbb{N}: \hspace{0.5cm} X_n = j\} \tag{1}$$Markov Zinciri bu noktadan birden fazla kez (hatta sonsuz kere) geçiyor olabilir, biz bunların minimumunu alıp buna ilk geçiş zamanı $T_j$ diyoruz.

Soru: Eğer zincir $i$ durumundan başladığında, ileriki bir zamanda $i$'ye tekrar gelmek zorunda mı? Geliyorsa ne kadar sık geliyor?

Tanım: Bir $i$ durumu için
$$ \mathbb{P}(T_i < \infty) =  \mathbb{P}(T_i < \infty | X_0 = i) = 1 \tag{3}$$ ise $i$ durumuna 'tekrar eden' (recurrent) durum denir.

Tanım: Eğer bir durum 'tekrar eden' bir durum değilse ona 'geçici' (transient) durum denir.

Teorem: Bir $i$ durumu ancak ve ancak aşağıdaki şart sağlanıyorsa 'tekrar eden' bir durumdur:
$$\sum_{n = 0}^{\infty}  \mathbb{P}_{i, j}(n) = \infty \tag{4}$$Yukarıdaki ifadede $\mathbb{P}_{i, j}(n)$, terimi $i$ durumundan $j$ durumuna $n$ adımda geçme olasılığını gösteriyor. Eğer bir durum 'tekrar eden' bir durumsa, yani zincirin o duruma tekrar gelme ihtimali 1 ise, sonsuz adımda buraya sonsuz kere geleceğinden, tekrar tekrar geldiği adımlar için olasılıkları topladığımızda sonsuz elde edeceğiz. Bunu kanıtlamak için 'üreteç fonksiyonları' (generating functions) kullanmak gerekiyor; tartışmayı detaylandırmamak adına bu kanıtı geçiyorum.

Tekrar eden ve geçici durumları da tanımladıktan sonra 'Basit Rastgele Yürüyüş' modeline geri dönelim. Model farklı boyutlar için kesikli ya da sürekli olarak tanımlanabiliyor. Bir boyutta bir doğru üzerinde sağa ve sola doğru hareket edilirken, iki boyutta kafes (lattice) şeklinde bi yapı üzerine noktanın en yakınındaki dört komşusuna geçişler yaparak ilerleniyor. Üç boyut için komşu sayısı altıya çıkıyor ve bu böyle artarak devam ediyor. Bizim ilgilendiğimiz sürekli rastgele hareketler olacak. Problemimiz şu: Belirli bir noktadan başlayan bir rastgele yürüyüşçümüz tekrar bulunduğu noktaya geri döner mi? Bunu bize ünlü Polya Teoremi söylüyor.

Polya Teoremi: Köşeleri tam sayılardan oluşan d boyutlu $\mathbb{Z}^d$ kafesini (lattice) alalım. $\mathbb{Z}^d$ üzerinde simetrik rastgele hareket ($p = q = 1/2$):

1) $d \le 2$ için tekrar edendir.
2) $d \ge 3$ için geçicidir.

Polya teoremi bize simetrik rasgele hareketin başladığı noktaya yalnızca 1 ve 2 boyutta geri gelebileceğini, 3 ve daha fazla boyut için bunun kesin olmadığını, yürüyüşün başını alıp gidebileceğini söylüyor!

Kanıt: 

1-boyutta, $\mathbb{Z}^1$'de, pozitif yönde bir adım atma olasılığı $p$, negatif yönde bir adım atma olasılığı $q$ olan, $p \not= q$ yürüyüşe bakalım. Orijinden $(j = 0)$ başlayan bir yürüyüşün tekrar geri gelmesi için sağ tarafa ve sol tarafa eşit sayıda adım atması gerekir, bu da toplam adım sayısının çift olmasını gerektirir. $2n$ adımda $0$ noktasından $0$'a geri  gelme olasılığını şöyle yazabiliriz:
$$\mathbb{P}_{0,0}(2n) = \binom{2n}{n} p^n q^n \tag{5}$$
$2n \choose n$ $2n$ tane adımdan yarısını sağa, yarısını da sola olacak şekilde kaç farklı şekilde atabileceğimizi gösteren kombinatorik katsayı. Büyün $n$ sayıları için bu durumu incelediğimiz için $\binom{2n}{n}=\frac{(2n)!}{(n!)^2}$ ifadesi için meşhur Stirling yaklaşımını (Stirling's Approximation) kullanacağız:
$$n! \approx \sqrt{2 \pi n} \bigg( \frac{n}{e}\bigg)^n \hspace{1.5cm} \text{(Stirling yak.)} \tag{6}$$
$$ \binom{2n}{n}= \frac{(2n)!}{(n!)^2}  \approx \frac{\sqrt{4 \pi n} \big( \frac{2n}{e}\big)^{2n}}{2 \pi n \big( \frac{n}{e}\big)^{2n}}  = \frac{1}{\sqrt{\pi n} 4^n} $$ $$ \Rightarrow \mathbb{P}_{0,0}(2n) \approx  \frac{1}{\pi n} (4 p q) ^n \tag{7}$$
Simetrik yürüyüş, yani $p = q = 1/2$ için:
$$\mathbb{P}_{0,0}(2n) \approx \frac{1}{\pi n} \tag{8}$$
Bu olasılıkların tüm $n$'ler için toplamını alıp $0$ durumunun tekrar edip etmeme şartına bakarsak $(4)$:
$$\sum_{n = 1}^{\infty} \mathbb{P}_{0,0}(2n) =  \sum_{n = 1}^{\infty} \frac{1}{\pi n} = \infty \tag{9}$$
Sonucumuzu denklem $(4)$ ile karşılaştırdığımızda 1 boyutta simetrik rastgele yürüyüşün 'tekrar eden' bir yapıda olduğunu kanıtlamış olduk. $p \not= q$ için ise rastgele yürüşün 'geçici' yapıda olduğunu denklem $(7)$'de $p$ ve $q$'yu yerine koyup tüm $n$'ler üzerinden topladığınızda olasılığın sonlu çıkacağını göstererek kanıtlayabilirsiniz.

2-boyuta geldiğimizde ise, rastgele yürüyüşü sağ/sol yönünün yanında yukarı/aşağı olarak da yapıyor olacağız. Herhangi bir anda belirli bir konumda bulunan bir yürüyüş 1/4 olasılıkla sağa/sola ya da yukarı/aşağı hareket edebiliyor olacak (simetrik durum). Orijinden $(0)$ başlayan bir yürüyüşün aynı sebeplerden ötürü ancak çift sayıda adımda aynı noktaya geri gelebileceği bariz. İki boyutta da aynı noktaya geleceğinden dolayı, sağ/sol yönünde de, yukarı/aşağı yönünde de ayrı ayrı eşit sayıda adım atması gerekiyor. Toplamda $2n$ tane adımda $0$ noktasından başlayıp $0$'a geri gelen tüm adım dizilerinin her birinin olasılığı $\bigg( \frac{1}{4}\bigg)^{2n}$'dir. Peki bu adımlardan toplam kaç tane vardır?

$2n$ adımdan sağa $(n-k)$ tane, sola $(n-k)$ tane; yukarı $k$ tane ve aşağı $k$ tane olmak üzere kaç farklı şekilde adım atılabilir?
$$\binom{2n}{n-k, n-k, k, k} = \frac{(2n)!}{(n-k)! (n-k)! k! k!}$$
O halde oriinden başlayıp $2n$ adımda tekrar orijine geri gelme ihtimalini yazarsak:
\begin{align}
\mathbb{P}_{0,0} (2n) &= \sum_{k=0}^n \binom {2n}{n-k, n-k, k, k} \big( \frac{1}{4} \big)^{2n} \\ \\
&= \sum_{k=0}^n \frac{(2n)!}{(n-k)!^2(k!)^2 \big( \frac{1}{4} \big)^{2n} }\\ \\
&= \frac{(2n)!}{(n!)^2} \sum_{k=0}^n \frac{(n)!}{(n-k)!^2(k!)^2 \big( \frac{1}{4} \big)^{2n} }\\ \\
&= \binom{2n}{n} \sum_{k=0}^n \binom{n}{k}^2 \big(\frac{1}{4}\big)^{2n} = \binom{2n}{n}^2 \big(\frac{1}{4}\big)^{2n} \tag{10}
\end{align}
$(10)$'daki sonuç ifadesi 1-boyutta yürüyüş için bulduğumuz (5) olasılık değerinin  $p = q = 1/2$ için karesi olduğu görülebilir.
$$\mathbb{P}_{0,0}(2n) = \bigg[ \bigg( \frac{1}{2} \bigg)^{2n} \binom{2n}{n} \bigg]^2 \approx \frac{1}{\pi n} \tag{11}$$
Bu olasılığı da tüm $n$ değerleri üzerinden toplarsak:
$$\sum_{n = 1}^{\infty} P_{0,0}(2n) \approx  \frac{1}{\pi} \sum_{n=1}^{\infty} \frac{1}{n} = \infty \tag{12}$$
Olasılıkların toplamı 1-boyutta yürüyüş için olduğu gibi yine sonsuz çıktı. Tekrar etme koşulu $(4)$'e göre 2-boyutta yürümenin de tekrar eden bir yapıda olduğunu göstermiş olduk.

2-boyutta simetrik, eşit olasılıklar için kanıtladığımız tekrarlı olma özelliği olasılıkların simetrik olmadığı durumlar için geçerli değil. Bildiğim kadarıyla sadece sağ/sol ve yukarı/aşağı olasılıkların kendi içinde $1/2$'ye toplandıkları durum için de tekrarlı oluyor fakat diğer durumlar için muhtemelen(emin değilim) geçici özellikte.

Polya teoreminin en vurucu kısmı $d \ge 3$ için söyledikleri. Fakat buna bir sonraki yazıda değineceğiz.

(Solda: Orijinden başlayıp uzun bir süre ilerleyen 2 boyutlu bir rastgele yürüyüş simülasyonu görülüyor. Hareketin boyut arttıkça ne kadar karmaşıklaştığı açıkça görünüyor. Görüldüğü kadarıyla henüz orijine uğramamış. Kaynak: Wolfram)


2-boyutta rastgele hareketi biraz programlama (javascript) kullanarak kolayca kurcalamak isteyenlere şu sayfayı öneririm: p5.js Brownian Motion

Stochastic Processes - III ( Chapman-Kolmogorov denklemi)

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.

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.

Uygulamalı Çizge Kuramı - III

Üçüncü bölümde periyodik çizge yapılarından yola çıkarak farklı dallanma tiplerine sahip 'ağaçsı çizgeler' için karakteristik uzunluk ve yarıçap tanımı yapacağız. Ardından bu uzunluğun  düğüm sayısı ile logaritmik ilişkisi ile 'küçük dünya' fenomenini ortaya koyacağız.. Son olarak, ilk iki bölümde incelediğimiz rastgele ağ modellerinin aslında birer 'küçük dünya' olduklarını göstereceğiz.

İki boyutlu, düğümleri arası birim uzunlukta, her bir boyutu L uzunluğunda periyodik bir çizge (örneğin bir lattice-kafes) ele alalım. Öncelikle bu tip bir çizgede $N = L^2$ tane düğüm noktası olduğunu görüyoruz. Bu çizgedeki düğümler arasındaki uzaklıklara baktığımızda, arasında en uzun mesafe olan iki düğümün arasındaki uzaklığın en fazla $2L$ olduğunu, dolayısıyla bu çizge üzerinde karakteristik uzaklığın $\sim L$ ($L$ mertebesinde) olduğunu söyleyebiliyoruz. Benzer bir hesaplamayı gene düzgün, periyodik fakat üç boyutlu bir çizge üzerinde yaptığımızda düğüm sayısının $N^3$ ile fakat uzaklığın gene $\sim L$ ile gittiğini görüyoruz. Bunu genelleştirdiğimizde bu tip periyodik çizgelerdeki karakteristik uzaklığın şu şekilde olduğunu söyleyebiliriz: $$\bar{l} \sim N^{\frac{1}{d_E}}$$ $d_E$ çizgemizin Öklidyen boyutu olarak tanımlanıyor. İki boyut için $2$, üç boyut için $3$ vs vs...

Ağaçsı çizgeleri oluşturmak için ilk başta bir düğüm (kök) ile başlayarak, her bir iterasyonda (jenerasyonda) $b$ tane düğüm ekleyip bunu bir önceki köke bağlayarak çizgeyi büyütüyoruz. İlk noktayı $0.$ jenerasyon olarak tanımlarsak, ilk jenerasyonda $b$ tane, ikinci jenerasyonda $b^2$ tane yeni düğümümüz ve bağlantımız oluyor. $r$ tane jenerasyona sahip bu tip bir çizgedeki toplam düğüm sayısı: $$N = 1 + b + b^2 + b^3 + ... + b^r = \sum_{n=0}^r b^n = \frac{b^{r+1} - 1}{b-1} \sim b^r$$ $$ N \sim b^r$$

Ağaçsı çizgelere iki örnek; sağdaki $b = 2$ dallanma katsayısına sahip, soldakinin dallanma katsayısı her jenerasyonda farklı (2-3-4... diye gidiyor) 

Bizim peşinde olduğumuz büyüklük, bu tip bir çizgedeki karakteristik uzunluk, yani $\bar{l}$. Ağacın yapısını incelediğimizde birbiri arasında en uzun mesafeye sahip olan düğümlerin, ilk jenerasyonda birbirinden ayrılan dalların en ucundaki düğümler olduğunu; bunların arasındaki mesafenin de $l_{max} = 2r$ olduğunu görüyoruz. Dolayısıyla yukarıdaki düğüm sayısını veren ifadeden $r$'yi çekmek için: $$ \log{N} = r\log{b}$$ $$r = \frac{\log{N}}{\log{b}}$$ $$l_{max}= \frac{2\log{N}}{\log{b}}$$ $$\bar{l} \sim \frac{\log{N}}{\log{b}} \tag{1}$$ $(1)$ nolu ifadenin gösterdiği üzere karakteristik uzaklık ($\bar{l}$) düğüm sayısının logaritması ile gidiyor. Periyodik çizgeler için hesapladığımız $1/d_E$ üssünden de yavaş bir şekilde gidiyor kısacası. Bunun anlamı ise, bu tip ağaçsı çizgelerde düğüm sayısı çok büyüse de bir düğümden diğer herhangi bir düğüme ulaşmak için kat edilmesi gereken mesafe çok yavaş artıyor, dolayısıyla herkes birbirine oldukça 'yakın'. Bu tip yapıya sahip çizgelere 'küçük dünya' (small world) ağları adı veriliyor. Bunlara en güzel örnek olarak belki de Amerika'da 1950'lerde insanların sosyal ağları üzerine yapılan bir araştırmada, rastgele bir Amerikan vatandaşının önceden belirlenen bir kişiye, kendisi veya tanıdığı (ya da tanıdığının tanıdığı vs..) vasıtasıyla kaç adımda 'tanışıklık' üzerinden uzak olduğunu belirlemeye çalıştıkları çalışma verilebilir. Elde edilen verilere göre ortalama 5.2 kişide bahsi geçen kişiye ulaşabiliyorsunuz. Benzer 'küçük dünya' etkisini internet gibi diğer ölçeksiz ağlarda da gözlemek mümkün...

İkinci kısımda, Erdös-Renyi çizgelerinde $L$ uzunluğundaki döngülerin sayılarına bakarak, bu sayının düğüm sayısı $N$'den bağımsız olduğunu göstereceğiz. Böylece çok büyük düğüm sayısına sahip çizgelerde bu tip döngülerin epey nadir ve ihmal edilebilir oldukları sonucuna varacağız. Ardından ortalama dallanma sayını hesaplayıp (1) nolu ifadede yerine koyarak bu çizgelerin de birer 'küçük dünya' olduklarını göstereceğiz.

İlk olarak L uzunluğundaki ortalama döngü sayısını hesaplayalım. Böyle bir dögü için öncelikle $N$ tane düğümden birini seçelim, ardından geriye kalan $N-1$ tanesinden de $L-1$ tane seçip bunları toplam L tane bağlantı olacak şekilde bağlayalım. Her bir bağlama olasılığımızın $\langle q \rangle N$ olduğunu biliyoruz. Oluşacak her bir kenarı yönden bağımsız seçmek için  yarısını alıp, ilk baştaki seçimizi L farklı şekilde uygulayıp aynı çizgeyi elde edebileceğimizden bir de $1/L$ faktörü geliyor olacak. Kısacası formülümüz şu şekilde: $$ N_L = N \binom{N-1}{L-1} \frac{(L-1)!}{2} \Big( \frac{\langle q \rangle}{N} \Big)$$ $$ = \frac{N(N-1)(N-2)..(N-L+1)}{(L-1)!}\frac{(L-1)!}{2L}\Big( \frac{\langle q \rangle}{N} \Big)^L$$ Yine $N>>1$ ve $L \leq < N$ olmak üzere $$N_L \sim \frac{N^L}{2L}\frac{\langle q \rangle^L}{N^L} = \frac{\langle q \rangle^L}{2L} \tag{2}$$
(2)'de elde ettiğimiz $L$ uzunluğundaki ortalama döngülerin sayısının düğüm sayısı $N$'den bağımsız olduğunu bulduk.

İkinci olarak, ortalama dallanma katsayısı için bir değer bulmak amacıyla, ele aldığımız bir düğüme komşu bir düğümün $q$ tane kenara yani $q$ derecesine sahip olması olasılığına bakacağız. İlk bakışta bunun dağılımının da derece dağılımı ile aynı şekilde ($\langle q \rangle$) olacakmış gibi, görünse de, bahsi geçen olasılığı koşullu olasılık gibi düşündüğümüzde biraz daha farklı bir sonuç vereceğini göreceğiz. Bu olasılığı şu şekilde tanımlayalım: $P_a(q)$, seçilen bir düğüme komşu olan $a$ ile isimlendirdiğimiz düğümün $q$ tane düğüme sahip olma olasılığını göstersin: $$P_a(q) = \frac{qN(q)}{N \langle q \rangle} \tag{3}$$ (3) nolu ifadede paydaki değer $q$ derecesine sahip tüm düğüm sayısı ile düğümlerin çarpımı, paydadaki değer ise tüm düğüm sayısını veriyor. Bahsi geçen $a$ düğümünün ortalama düğüm derecesini hesaplamak için de: $$\langle q_a \rangle = \sum_q qP_a(q) = \frac{1}{\langle q \rangle}\sum_q q^2 \frac{N(q)}{N}$$ $$\langle q_a \rangle = \frac{\langle q^2 \rangle}{\langle q \rangle} = \frac{\langle q \rangle^2}{\langle q \rangle} +1 = \langle q \rangle +1$$ $$\langle q^2 \rangle = \langle q \rangle^2 + \langle q \rangle$$ $$\Rightarrow \bar{b} = \langle q_a \rangle -1 = \langle q \rangle$$

E-R çizgelerinin, büyük düğüm sayıları için, içinde çok nadir bulunan döngüleri nedeniyle topolojik olarak 'ağaçsı' olduklarını (2) ile göstermiştik. Dolayısıyla ağaçsı çizgelerdeki karakteristik uzunluğu veren ifadeyi (1) E-R çizgeleri için de uygulayabiliriz. Dolayısıyla: $$\bar{l} \sim \frac{\ln{N}}{\ln {b}} = \frac{\ln{N}}{ln{\langle q \rangle}}$$ Elde ettiğimiz bu sonuca göre E-R tipi bir rastgele çizgede düğüm sayıları arttıkça sadece logaritmik, yavaş bir artışın yanında; artan ortalama düğüm derecesi ile de azalan bir uzaklık söz konusu. Yani E-R çizgelerini de tıpkı ölçeksiz bir ağda olduğu gibi birer 'küçük dünya' olduklarını söyleyebiliriz.

Dördüncü bölümde, çizgeleri ifade etmek ve üzerinde bir takım şeyler hesaplamak için kullanılan bir takım matrisler tanımlayacağız. Bunlardan ilki komşuluk ve derece matrisi olacak, ardından bunları birleştirip çizge Laplasyenini oluşturup bu operatörün işlevini ve özdeğer spektrumunu çıkaracağız.

Uygulamalı Çizge Kuramı - II

Bir önceki yazıda rastgele çizgelere giriş yapıp Gilbert çizgesinden bahsetmiştik. Bu yazıda öncelikle Erdös-Renyi (E-R) çizgesi olarak bilinen çizgeyi gösterip bu çizgenin Gilbert modeli ile eşdeğer olduğunu göstereceğiz. Ardından kuvvet yasası şeklinde farklı bir olasılık dağılımına sahip başka tip çizgeler üzerine konuşup bu çizgeler üzerindeki derece dağılımlarını inceleyeceğiz.

Erdös-Renyi Çizgeleri

Kısaca E-R çizgesi olarak ifade edilen bu çizgede, Gilbert çizgesine benzer şekilde, $N$ tane düğüm sayımız var,  fakat bu sefer düğümlerin birbirine bağlanma olasılığı $p$ yerine, toplam kenar sayısı $E$ veriliyor. Dolayısıyla $E$ tane kenarı, $N$ tane düğüm arasında paylaştırıyoruz gibi düşünebiliriz. Bu şekilde düşündüğümüzde, verilen her $N$ ve $E$ sayıları için oluşturduğumuz her bir çizgenin, bu yolla oluşturulabilecek tüm çizge ailesinin bir üyesi olduğunu söyleyebiliriz (Bu kavram aslında istatistiksel fizikteki 'grand canonical ensemble'ın çizgeler üzerinde bir analogu ve sabit olan düğüm sayısı parçacık sayısına, kenar sayısı da kimyasal potansiyele denk geliyor).

Bu çizge üzerinde gene derece dağılımıyla ilişkili olarak ortalama derece sayısını hesaplayabiliriz. $d_i$ i. düğümün derecesi olmak üzere, şunları biliyoruz: $$\frac{1}{N} \sum_i d_i = \langle d \rangle $$ $$\sum_i^N d_i = 2E $$ $$\Rightarrow \langle d \rangle = \frac{2E}{N} \tag{1}$$ Düğüm sayıları toplamının $2E$ olmasının sebebi, her bir kenarın ucunda ikişer düğüm bulunuyor, dolayısıyla tüm dereceleri topladığımızda kenar sayısının iki katı kadar düğüm toplamış oluyoruz.

Bir E-R çizgesinde $N$ tane düğüm ile elde edebileceğimiz en fazla kenar sayısı bağlantısı: $$E_{max} = \frac{N(N-1)}{2} = \binom{N}{2}$$ Bu çizge üzerinde kenarlar için tanımlayacağımız $p$ olasılığı, mevcut (ortalama) kenar sayısı ve olabilecek tüm $E_{max}$ kenarı arasında şöyle bir ilişkiyi temsil ediyor: $$ \langle E \rangle = E_{max}p $$ Yukarıdaki $(1)$ nolu eşitliğe geri dönüp, $E$ yerine bu ifadeyi yazarsak:
$$\langle d \rangle = \frac{2 E_{max}p}{N} = \frac{2N(N-1)p}{2N} = Np \tag{2} $$ Sonda yapılan $$(N-1)p \sim Np$$ yaklaşımı bir önceki bölümdeki hesapta da karşılaşmıştık ($N>>1$). Dolayısıyla $(2)$'de gösterdiğimiz üzere: $$\langle d \rangle = Np $$ Bulduğumuz ifade, $G_{N,p}$ Gilbert çizgesinde elde ettiğimizin aynısı! Buradan bu iki çizge modelinin her ne kadar farklı tanımlansalar da çok sayıda düğüm ve düşük bağlanma olasılıklarında birbirlerine denk olduğunu göstermiş oluyoruz.

Kuvvet Yasası Derece Dağılımlı Çizgeler

Şu ana kadar değindiğimiz iki tip çizge de birbirine denk olduğundan, her ikisinin de derece dağılımlarının benzer yani Poisson olduğunu söyleyebiliyoruz. Bu dağılımın karakteristik özelliğine göre, dereceler üzerinden konuşuyorsak, derece sayısını ortalama etrafında kümelenmiş bir değer civarında bulmayı bekliyoruz. Bir düğümün yüksek sayıda derece sayısına sahip olma olasılığı, ortalama değerden sonra paydaki $e^{-Np}$ ve $N!$ faktörleri nedeniyle hızlı bir şekilde azalıp sıfıra gidiyor. Alternatif olarak bu tip sıfıra düşme durumunun bu kadar hızlı gerçekleşmediği, dolayısıyla yüksek sayıda dereceye sahip düğümleri hala oldukça yüksek olasılıklarla bulduğumuz dağılımlara bir örnek olarak 'kuvvet yasası(power-law) dağılımları' verilebilir. Bu tip dağılımlar $P(q) \sim q^{- \gamma}$ şeklinde ifade ediliyorlar.

Bu dağılımlara yönelmemizin motivasyonu aslında zamanında A. Barabasi ve o zamanlar doktora öğrencisi R. Albert'in özellikle internet ağı tipi büyük ağların nasıl büyüdükleri üzerine yaptıkları çalışmalardan kaynaklanıyor. İkilinin önerdikleri 'seçmeli büyüme' (preferential attachment) modeliyle basitçe, düğümlere yeni bir kenar bağlanma olasılığı o düğümün mevcut derecesi ile doğru orantılı olacak şekilde bir çizge büyüme kuralı ortaya atıyorlar. Bu model ile mevcut internet ağını oldukça gerçeğe yakın modelleyerek, aynı zamanda bu tip bir çizgede ortaya çıkabilecek ilginç yapıları da gösteriyorlar. Bunlardan en öne çıkanı, merkez (hub) olarak tanımlanan derecesi çok yüksek ve o ağ üzerindeki bir çok bağlantıyla ilişkili düğümlerin varlığı... Sosyal ilişkilerde 'popüler insanlar', internet ortamında 'çok takip edilen ünlü kişiler', çok ziyaret edilen ve çok fazla bağlantı verilen internet siteleri gibi örnekler bu merkezlere örnek verilebilir. Bu modelin en önemli çıktısı, bu tip bir büyüme modeliyle oluşturulan çizgelerin derece dağılımlarının $\gamma = 3$ parametresi ile karakterize edilen kuvvet yasası dağılımları olduğunu göstermesi. Modelden elde edilen $\gamma = 3$ değerinin internet ağı için gerçek değere çok yakın olduğu görülüyor.

Bu tip kuvvet yasası dağılımına sahip çizgelerde Poisson dağılımlı çizgelerin tersine çok sayıda düğümle bağlantıya sahip düğüm sayısı sıfıra çok yavaş gidiyor, dolayısıyla yüksek sayıda dereceye sahip düğümleri bu tip çizgelerde gözleyebiliyoruz (örneğin bir önceki paragraftaki 'hub'lar). Bu tip dağılımları karakterize etmek için belirli bir ölçek olmadığını görüyoruz çünkü birazdan hesaplayarak göstereceğimiz üzere bu tip dağılımlara sahip çizgelerin belirli bir ortalamaları veya standart sapmaları genellikle olmayabiliyor. Bu nedenle bu tip çizgelere 'ölçeksiz (scale-free) çizgeler' deniyor. Bu çizgeleri karakterize eden kuvvet yasası dağılımları, büyük değerler için sıfıra gitmeleri nedeniyle 'kalın-kuyruklu' (fat-tail) dağılımlar olarak da adlandırılabiliyorlar.

Rasgele(random) ve ölçeksiz(scale-free) çizgelerin derece dağılımları arasındaki fark. Sağdaki kuvvet yasası dağılımının logaritmik ölçekte çizildiğine dikkat edin. (Kaynak)

Şimdi bu tip dağılıma sahip çizgeler için ortalama ve standart sapma hesapları yapacağız. Düğüm derecesine, integrasyondaki $d$ ile karışmaması için $q$ deyip devam edeceğiz. $q$ düğüm derecesinin ortalaması için:
$$\langle q \rangle = \sum_{d=0}^N P(q)q \sim \int_{0}^N P(q) q dq$$
$$\langle q \rangle = \int_{0}^N q^{- \gamma} q dq = \frac{q^{-\gamma +2}}{-\gamma + 2}\Big|_0^N $$ Eğer $\gamma >2$ ise: $$\langle q \rangle = \frac{-1}{2- \gamma}\Big[\frac{1}{N^{\gamma - 2}} - \frac{1}{a^{\gamma -2}}\Big] \tag{3}$$ $(3)$'deki ifade $N \to \infty$ için $0$'a gidiyor, Fakat eğer $\gamma < 2$ durumunda $\frac{1}{N^{\gamma-2}}$ terimi patlıyor ve $\langle q \rangle$ sonsuza gidiyor: $$\langle q \rangle \to \infty$$ Kısacası $\gamma < 2$ için ortalama ıraksıyor yani belirli bir ortalama değeri yok. Benzer hesabı $\sigma^2$ için yaptığımızda, hesaplarken gelen $\langle q^2 \rangle $ terimi için de benzer bir ıraksaklık problemi ile karşılaşıyoruz. $$\langle q^2 \rangle = \int_{0}^N q^{- \gamma} q^2 dq = \frac{q^{-\gamma +3}}{-\gamma + 3}\Big|_0^N $$ Eğer $\gamma <3$ ise $\langle q^2 \rangle$ ıraksıyor: $$\langle q^2 \rangle \to \infty$$Dolayısıyla varyans $\sigma^2 = \langle q^2 \rangle - \langle q \rangle^2$ da ıraksıyor. Böylece $P(q) \sim q^{-\gamma}$ şeklinde derece dağılımına sahip çizgelerin belirli bir ölçeğe sahip olmadığını göstermiş olduk.

Ölçeksiz çizgelerin, içinde bulundurdukları yüksek dereceli düğümler sayesinde örneğin E-R çizgelerine göre daha dayanıklı (robust) olarak tanımlanıyorlar (R. Albert, H. Jeong, A. Barabassi, Error and attack tolerance of complex networks, Nature, 2000). Burada bahsi geçen dayanıklılık, çizgeden yavaş yavaş kenarlar koparmaya başlandığında çizge yapısının, birbirine sıkı bağlarla bağlı merkezi bir yapıyı sürekli koruyarak, dağılmaya karşı ne kadar dirençli olduğunu ifade ediyor. E-R çizgeleri bunun tam tersi, küçük sayıda kenar koparılmasıyla birbirinden tamamen bağlantısız küçük parçalara ayrılabiliyorlar. Koparma sıklığı/olasılığı şeklinde bir $f$ parametresi belirlediğimizde E-R çizgelerinde bu $f$ bir kritik değere ($f_{critical}$) ulaştığında çizge tamamen kopmuş oluyor. Bu davranış aslında bir tip 'faz geçişi' şeklinde modellenebiliyorlar (dolayısıyla aslında bunun istatistiksel fizikteki 'percolation' davranışına denk geldiği belirtiliyor).

Bu bölümde Erdös-Renyi çizgesini tanımlayıp, bunların ilk bölümdeki Gilbert çizgesi ile eşdeğer olduklarını gösterdik. Ardından kuvvet yasası dağılımı gösteren çizgeleri inceleyerek belirli $\gamma$ parametreleri için derece ortalama ve varyanslarının ıraksadığını görüp buradan yola çıkıp ölçeksiz çizgeleri tanımladık. Bir sonraki bölümde çizgelerdeki düğümler arası ortalama uzaklıkları inceleyip 'ağaçsı çizgeler' üzerinden 'küçük dünya'(small world) fenomenini inceleyeceğiz.

Uygulamalı Çizge Kuramı - I

Yaklaşık bir haftadır Nesin Matematik Köyü'nde çeşitli derslere katılıyorum. Bu yıl, geçmiş yıllardan farklı olarak MK'da fizikçiler için açılan dersler sebebiyle buradayım aslında ama bir hafta öncesinde gelip özellikle 'Uygulamalı Çizgeler Kuramı' ve 'Diferansiyel Denklemler' derslerini dinlemek istedim. Köydeki ilk haftamın ardından, ilk derslerden aklımda kalanları dokümante etmek ve ileride göz atmak adına düzgün notlar hazırlamak için gün gün derslerin kısa özetlerini yazmayı düşündüm.


Her ne kadar 'Matematik' Köyü'nde olsak da İTÜ Fizik Mühendisliği Bölümü'nden yakın zamanda emekli olan Ayşe Erzan'ın verdiği 'Uygulamalı Çizge Kuramı' dersi, tipik matematiksel notasyondan ve teorem-kanıt akışından farklı olarak, belki de tam anlamıyla 'uygulamalı' bir şekilde, daha çok istatistiksel fizik perspektifinde bir dersti. Dolayısıyla ben de tanımlarım ve hesaplamalarımda benzer yaklaşımı izlemeye çalışacağım. İlk günkü notlarla başlayalım o halde.

Bir çizgeyi (graf ya da ağ'ı) en basit şekliyle belirli ya da sonsuz sayıda düğümler (node) ve bunları ikili şekilde birbirine bağlayan kenarların (edge) bütünü olarak tanımlayabiliriz. Bu köşeler genelde her birine bir isim verilip $V$ kümesi ile ve bunların birbiriyle bağlantılarını ifade eden kenarlar ikililerden oluşan $E$ kümesi ile gösterilirler. Fakat bizim işimiz doğrudan bu kümelerin içindeki bir takım 'matematiksel' ilişkilerin ötesinde, ilerde daha iyi anlaşılacak olan bu yapıların daha çok global özelliklerini anlamak olduğundan bu tip bir formal tanımlamalar üzerinde çok durmayacağız. Üzerinde çalışacağımız çizgeler yönsüz çizgeler olacak; düğümler arasındaki kenarlar herhangi bir yönlü ilişki belirtmiyor olacaklar.

Bir çizgenin karakterini belirleyen çok temel birkaç parametre bulunuyor. Bunlardan ilki düğüm sayısı $N$. Sonlu bir çizgede düğümleri 1'den $N$'ye kadar etiketleyebiliriz ($i = 1,2, ... N$). Diğer önemli parametre ise verili bir düğüme(düğümleri $i$ ile etiketleyelim) bağlı kenar sayısı, yani o düğümün derecesi $d_i$. Yukarıdaki çizgede her bir düğümün derecesini şu şekilde yazabiliriz:

$d(1) = 2$, $d(2) = 3$
$d(3) = 3$, $d(4) = 2$



Bunlardan yola çıkarak tanımlayabileceğimiz bir başka büyüklük, $d$ dereceye sahip ortalama nod sayısı, ki bunu  $p(d)$ ile gösterelim: $p(d) = \frac{N(d)}{N}$; hatırlayalım $N$ toplam düğüm sayısı ve $N(d)$ ise $d $ dereceye sahip düğüm sayısı. Bu değerin $N$ sonsuza giderken $d$ derecesine sahip düğümlerin olasılığına eşit olacağını söyleyebiliriz: $$ p(d) = \lim_{d \to \infty} \frac{N(d)}{N} $$ Böylece, çizgeler üzerinde tanımlayacağımız çeşitli özelliklerin istatistiksel hesaplarında (örneğin ortalama, standart sapma ve çok daha fazlası) kullanabileceğimiz bir olasılık tanımı geliştirmiş bulunuyoruz. Bunu 'derece dağılımı' olarak adlandırırsak, bir çizgenin derece dağılımı bilgisi üzerinden çizgeye dair epey işe yarar şey hesaplamak mümkün. İlk olarak elimizdeki sonsuz sayıda (ya da çok çok fazla) düğüme sahip bir çizgedeki derece dağılımını elde etmeye çalışacağız. Bunun için de 'rasgele çizgeler' olarak tanımlanan iki tip çizgeyi Gilbert çizgesi (bu yazıda) ve Erdös-Renyi çizgesini (ikinci yazıda) inceleyeceğiz.

Gilbert çizgesi:

$G_{N,P}$ olarak gösterilen bu çizge iki parametre ile tanımlanabiliyor: toplam düğüm sayısı $N$ ve bir düğümün diğerine bağlanma olasılığını veren $p$. Sözle ifade edersek; N tane düğümümüzü yerleştiriyoruz ve bunlardan seçtiğimiz tüm ikililer için bunları birbirine bağlayıp bağlamayacağımızı kendimize soruyoruz. $p$ olasılıkla bağlıyoruz, $1-p$ olasılıkla bağlamıyoruz (dolayısıyla yalnız iki seçeneğimiz var ve ikisinin olasılıkları toplamı $p +(1-p) = 1$). Problemi formüle ederken fark edileceği üzere iki durumumuz var ve $N$ tane düğüm arasından seçim yapıyoruz. Rastgele bir şekilde oluşturduğumuz bir çizgede bir düğüme, kalan $N-1$ tane düğümden $d$ tane kenar bağlanma olasılığını binom dağılımı ile karakterize edebiliriz: $$p(d) = \binom{N-1}{d}p^d(1-p)^{N-1-d}$$ $$\sum_{d=0}^{N-1} p(d) = 1$$
Şimdi bu dağılım üzerinde bir takım yaklaşımlar uygulayıp, dağılımın belirli limitlerde nasıl davranacağına bakacağız.

Öncelikle çok büyük N düğüm sayıları için $N-1  \sim  N$ diyebiliriz. Yukarıdaki dağılımın çok küçük bağlanma olasılığı ($p <<1$) için nasıl davrandığına baktığımızda aşağıdaki adımlarla ilerliyoruz:
$$ P(d) = \frac{N!}{d!(N-d)!}p^d(1-p)^{N-1-d} $$ $$  P(d) = \frac{N(N-1)...(N-d+1)}{d!}p^d[1-(N-d)p]$$
$p<<1$ için $(1-p)^{N-1-d} \sim 1-(N-d)p$ diyebiliriz. $N$'nin çok büyük olmasını tekrar kullanıp gönül rahatlığıyla $1-(N-d)p \sim 1-Np $ yazabiliriz. Ayrıca $p$'nin çok çok küçük olmasından yola çıkarak $1- (Np)$ ifadesini de $e^{-Np}$ olarak gösterebiliriz. Son yapacağımız yaklaşıklık ise $N(N-1)...(N-d+1) \sim N^d$ olacak(her bir parantezden bir $N$ çarpanı dışarı çıkarıyoruz). Sonuçta şöyle bir ifade ile karşılaşıyoruz $$ p(d) = \frac{N^dp^d}{d!}e^{-Np}$$ Elde ettiğimiz dağılım meşhur Poisson dağılımı. Yani çok sayıda düğüme sahip, bağlanma olasılığı oldukça düşük rastgele bir çizgede, seçtiğimiz herhangi bir düğümün $d$ derecesine sahip olma olasılığı Poisson dağılımı ile ifade ediliyor. Poisson dağılımı tek bir parametre ile karakterize edilebilen, özellikle fizikte birçok durumda karşımıza çıkan bir dağılım. Bahsi geçen parametre, yukarıda da muhtemelen gözünüze çarpan $Np$ parametresi. Bu parametreyi $\lambda$ ile isimlendirirsek, dağılımın son halini şu şekilde yazabiliriz: $$p(d) = \frac{\lambda^d}{d!}e^{-\lambda}$$ Bu dağılım altında çizgemizdeki ortalama derece sayısını hesapladığımızda:$$\langle d \rangle = \sum_{d=0}^{N-1} P(d)d = \lambda$$ olduğu kolaylıkla görülebilir. Aynı şekilde derece dağılımının standart sapmasını hesapladığımızda ($\sigma_d^2  = \langle d^2 \rangle-\langle d \rangle^2$ ifadesinden yararlanıp) bunun da ortalama değere yani $\lambda$'ya eşit olduğunu görebiliriz. Bunun anlamı, küçük $\lambda$ değerleri yani ortalama değerler için dağılımımız oldukça dar ve ortalama etrafında çok saçılmamış; fakat büyük ortalama değerler için varyansın da aynı şekilde büyüyerek gittikçe daha geniş ve çokça saçılmış bir dağılıma benzediğini gözlüyoruz.

Uzun lafın kısası, sadece $N$ ve $p$ ile karakterize edilen Gilbert çizgemizin çok büyük $N$ düğüm sayıları için, düğüm derecelerinin Poisson şekilde dağıldığını bulmuş olduk. Buradan yola çıkarak da ortalama düğüm derecesinin ve bunun varyansının Poisson dağılımındaki parametre olan $\lambda = Np$ olduğunu göstermiş olduk.

Bir sonraki bölümde, bir diğer rastgele çizge tipi ola Erdös-Renyi çizgesini ele alıp, benzer hesaplamaları onun için de yapıp bunların eş değer olduğunu göstereceğiz. Ayrıca Poisson dağılım gösteren çizgelere alternatif olarak kuvvet yasası gereğince dağılım gösteren çizge tiplerini inceleyeceğiz.