Kararlı Kocalar

Özet

Rastgele seçilmiş $n$ erkek ve $n$ kızın birbirlerini tercih sırasına koyduğunu varsayalım. Eğer $\epsilon$ herhangi bir pozitif sabit ise, bu sıralamalar tarafından tanımlanan tüm Gale/Shapley kararlı eşlemeleri kümesinde, herhangi bir kızın en az $({1\over 2}-\epsilon) \ln n$ ve en fazla $(1+\epsilon)\ln n$ farklı kocaya sahip olma olasılığının, $n \to \infty$ iken 1'e yaklaştığını gösteriyoruz. Kanıt, diğer birçok kombinatoryal algoritmanın analizi için de yararlı olabilecek genel yöntemleri vurgulamaktadır.[^1]

1. Giriş

Bu, Gale ve Shapley [3] tarafından geliştirilen “kararlı eşleme” adlı bir oyunu oynayan $n$ kız ve $n$ erkeğin hikayesidir. Her oyuncu, karşı cinsten her oyuncuyu tercihine göre sıralar; dolayısıyla, bireysel kızların tercihini temsil eden, erkekler kümesinin $n$ adet permütasyonu ve bireysel erkeklerin tercihlerini temsil eden, kızlar kümesinin $n$ adet permütasyonu vardır. Oyunun amacı, hiçbir kız ve erkeğin birbirlerini mevcut partnerlerine tercih etmeyeceği anlamında kararlı olan $n$ adet evlilik elde edecek şekilde erkeklerin ve kızların eşleşmesidir.

Örneğin, Alice, Brigitte, Cindy ve Debra'nın Wilfred, Xavier, Yuri ve Zeke ile oynadığını varsayalım; ve tercih sıralamalarının, en çok beğenilenden en az istenene doğru şu şekilde olduğunu farz edelim:

$$\begin{array}{ll} \text{Alice'in tercihleri} \quad Y > X > Z > W & \text{Wilfred'ın tercihleri} \quad A > B > D > C \\ \text{Brigitte'in tercihleri} \quad X > W > Y > Z & \text{Xavier'in tercihleri} \quad C > A > D > B \\ \text{Cindy'nin tercihleri} \quad W > Y > X > Z & \text{Yuri'nin tercihleri} \quad B > D > A > C \\ \text{Debra'nın tercihleri} \quad X > W > Z > Y & \text{Zeke'in tercihleri} \quad B > A > C > D \end{array}$$

Eşleme $(AW, BX, CY, DZ)$ kararsızdır, çünkü örneğin $A$ (Alice), $Z$'yi (Zeke) $W$'ye (Wilfred) tercih ederken aynı zamanda $Z$, $A$'yı $D$'ye (Debra) tercih etmektedir. Ancak $(AZ, BW, CX, DY)$ eşlemesi kararlıdır; oyuncuların çoğu birinci tercihlerinden başka biriyle eşleşmiştir, ancak sevdikleri kişiler durumlarını değiştirmek istememektedir. Verilen tercihler, $(AY, BW, CX, DZ)$ adında başka bir kararlı eşlemeye de izin verir. Bu örnekte yalnızca iki eşleme kararlıdır.

Bir kızın kararlı kocaları, en az bir kararlı eşlemede evli olabileceği erkeklerdir. Dolayısıyla, Alice'in bu örnekteki kararlı kocaları Yuri ve Zeke'dir. Brigitte'in ise yalnızca bir kararlı kocası vardır, o da Wilfred'dır; Xavier'i daha çok sevmektedir ancak Xavier ona katlanamamaktadır.

2. Bir Algoritma

Gale ve Shapley [3], herhangi bir tercih kümesi verildiğinde kararlı bir eşleme bulmak için bir prosedür sunmuşlardır; McVitie ve Wilson [10] ise tüm kararlı eşlemelerin bulunabilmesi için bu yöntemi genişletmişlerdir. Yakın zamanda Gusfield [5] kararlı eşlemelerin ilginç kafes (lattice) yapısını kullanarak, tüm kızların kararlı kocalarını eşzamanlı olarak $O(n^2)$ adımda belirleyen şık bir algoritma kurmuştur. Bu makaledeki amaçlarımız doğrultusunda, bu prosedürlerin yalnızca belirli bir $G$ kızının kararlı kocalarını bulan basitleştirilmiş bir varyantını ele almak yeterli olacaktır.

Temel fikir, şu anda bir partneri olan her erkeğin, belirli bir sınıftaki tüm kararlı eşlemeler arasında mümkün olan en iyi tercihi ile eşleştirildiği kısmi eşlemeleri sürdürmektir. Mevcut bir partneri olmayan erkeklerden birine geçici olarak $P$ denir; bu erkek kızlardan birine teklif götürecek ve kız da bu teklifi (en azından şimdilik) kabul edip etmemeye karar verecektir. $P$ rolü, aşağıdaki basit kurallara göre erkekten erkeğe geçer:

• A0. Başlangıçta tüm erkekler ve kızlar eşleşmemiştir.
• A1. Eğer en az bir erkeğin mevcut bir partneri yoksa, $P$ böyle bir erkek olsun. Aksi takdirde, tüm erkekler ve kızlar zaten eşleşmiştir ve elimizde kararlı bir eşleme vardır; $G$'nin partneri $S$'yi onun kararlı kocalarından biri olarak çıktı (output) olarak verin, ardından $GS$ çiftini mevcut eşlemeden çıkarın ve $P = S$ yapın. (Bundan sonra, yalnızca $G$'nin $S$ ile evli olmadığı kararlı eşlemeleri dikkate alacağız.)
• A2. Eğer $P$ zaten tüm kızlara teklif götürmüşse algoritmayı sonlandırın. Aksi takdirde, $H$, $P$'nin şimdiye kadar yaklaşmadığı kızlar arasında en çok beğendiği kız olsun; $P$ şimdi $H$'ye teklif götürür.
• A3. Eğer $H$ kızına, $P$'ye tercih ettiği bir erkek tarafından zaten teklif yapılmışsa, $P$'nin teklifini reddeder. Aksi takdirde $P$'yi kabul eder ve mevcut eşlemede eşleşirler; varsa önceki partneri şimdi $P$ rolünü üstlenir. Önceki bir partneri yoksa algoritma A1 adımından devam eder, aksi takdirde A2 adımından devam edin. $\ddot{\smile}$

Örneğin, bu algoritmayı giriş bölümünde verilen tercih sıralamaları üzerinde çalıştırdığımızı ve A1 adımında bir seçim yapılması gerektiğinde her zaman alfabetik olarak en önde gelen erkeği seçtiğimizi varsayalım. Özel $G$ kızı Alice olsun. Bu durumda şu olaylar gerçekleşir:

İlk kararlı eşleme bulunduktan sonra özel kız Alice'in A2 adımında asla bir partneri olmaması dışında, her kız şimdiye kadar kendisine en iyi teklifi yapan erkekle eşleşir. Bu tablodaki ‘$(AZ)$’ gösterimi, Alice'in mevcut bir partnerinin olmadığını, ancak şimdiye kadarki en iyi teklifinin Zeke'den geldiğini ifade eder. ‘$(AY)$’ ifadesinin göründüğü bir yerde, $A$ (Alice) şu anda boşta olmasına rağmen $X$'i reddeder, çünkü $Y$'yi $X$'e tercih etmektedir ve önceki standartlarını düşürmeyecektir.

Bu algoritmanın $G$'nin tüm kararlı kocalarını bulduğunu kanıtlamak için, kolaylık olması açısından birim zaman başına tam olarak bir teklif yapıldığını varsayalım, böylece A2 adımının $t$. yürütülmesi $t$ anında gerçekleşir. $M_t$, $G$'nin $t$ anından önce zaten çıktı verilmiş olan hiçbir $S$ ile evli olmadığı tüm kararlı eşlemelerin kümesini göstersin. Bu durumda $M_0$ tüm kararlı eşlemelerin kümesidir ve $t \le t'$ olması $M_t \supseteq M_{t'}$ olmasını gerektirir. Algoritmanın doğruluğu şu kritik gerçeğe dayanmaktadır:

$$\begin{array}{l} \text{Eğer } H \text{ kızı } t \text{ ile } t+1 \text{ zamanları arasında bir } R \text{ talibini reddederse,} \\ \text{o halde } HR \text{ çifti, } M_{t+1} \text{ içindeki hiçbir kararlı eşlemenin parçası değildir.} \end{array} \tag{*}$$

Kanıt $t$ üzerinden tümevarımla yapılır. Eğer $(*)$ ilk kez $t$ anında başarısız oluyorsa, $H$'nin $Q$'yu tercih etmesi nedeniyle A3 adımında $R$'yi reddettiğini varsayalım. (Ya $Q=P$ ve $R$ onun önceki en iyi partneridir ya da $R=P$ ve $Q$ onun önceki en iyisidir.) O halde $HR$'nin $M_{t+1}$ içindeki bir kararlı eşlemenin parçası olduğunu varsayıyoruz ve bu eşlemede kararlılık koşulu bize $Q$ erkeğinin, $H$'ye tercih ettiği bir $J$ kızıyla eşleşmiş olması gerektiğini söyler. Ancak bu durumda $Q$, $H$'ye teklif etmeden önce $J$'ye teklif etmiş olmalıdır, dolayısıyla $t' < t$ olan bir $t'$ anında $J$ tarafından reddedilmiş olmalıdır. Dolayısıyla, $(*)$ ve tümevarım uyarınca, $JQ$ çifti $M_{t'}$ içindeki bir kararlı eşlemenin parçası olamaz; bu durum $M_{t'} \supseteq M_{t+1}$ gerçeğiyle çelişir. Dolayısıyla $R$'nin $H$ tarafından reddedilmesi A3 adımında değil A1 adımında gerçekleşmiş olmalıdır; başka bir deyişle $H=G$ ve $R=S$ (kararlı bir koca) olmalıdır. Ancak tanım gereği $M_{t+1}$ zaten $GS$ çiftini içermez. Dolayısıyla $(*)$ doğru olmalıdır.

A1 adımında bulunan eşlemeler kararlı olmalıdır. Çünkü eğer bir $H$ kızı, $U$ erkeğini mevcut partnerine tercih ediyorsa, $U$ ona henüz teklif götürmemiştir; dolayısıyla $U$ kendi mevcut partnerini tercih etmektedir. Aslında $(*)$ bize, A1'de bulunan kararlı eşlemelerin, her erkeğin $M_t$ içindeki tüm eşlemeler arasında en iyi tercihine sahip olması özelliğiyle karakterize edildiğini söyler. Böylece, algoritma $S$'yi çıktı olarak verdiğinde, her erkek, $G$'nin $S$ ile eşleştiği tüm kararlı eşlemeler arasında en iyi tercihine sahip olur.

Algoritma, bir erkek tüm kızlar tarafından reddedildiğinde sonlanır. $(*)$ uyarınca bu durum, $M_t = \emptyset$ olduğunda, yani $G$'nin tüm kararlı kocaları $S$ çıktı olarak verildiğinde, $t$ anında gerçekleşir.

3. Rastgele Bir Model

Mümkün olan $n!^{2n}$ adet tercih dizisinin düzgün rastgele (uniformly at random) seçildiği varsayımı altında, eğer $c < 1/2$ olan herhangi bir sabit ise, az önce belirtilen algoritmanın en az $c \ln n$ adet çıktı üreteceğini ve bu olasılığın 1'e yaklaşacağını göstermek istiyoruz.

Temel fikir, [7] çalışmasında le principe d'ajournement des décisions olarak adlandırılan, “cehaletin korunumu” veya “ertelenmiş kararlar” (deferred decisions) ilkesi olarak da bilinen geç bağlama (late binding) ilkesini kullanmaktır. Tercih dizilerini önceden sabitlemek yerine, algoritma çalıştıkça onlara ne kadar ihtiyaç duyuyorsa o ölçüde ortaya çıkmalarına izin veririz. Böylece, bir erkeğin teklif yapması her istendiğinde, henüz denemediği kızlar arasından düzgün rastgele seçilen bir kıza teklif götürür. Bir kız $k$. teklifini aldığında bunu $1/k$ olasılıkla kabul eder. Bu özelliklere sahip bir stokastik süreç, rastgele tercih dizileri üzerinde çalışan orijinal algoritmayla eşdeğerdir, çünkü durumlar (states) arasında aynı geçiş olasılıklarına sahiptir.

Ayrıca, sanki her erkeğin “amnezisi” varmış [7] ve daha önce teklif götürdüğü kızların hiçbirini hatırlayamıyormuş gibi, her teklifin düzgün rastgele olduğunu varsayarak algoritmayı daha da basitleştirebiliriz. Eğer bir erkeğin kendisini tekrarladığı ortaya çıkarsa, bir yinelenen teklif (redundant proposal) yaptığını söyleriz; bu tür teklifler her zaman reddedilir. Algoritma şimdi şu veri yapılarını kullanan oldukça basit bir stokastik sürece indirgenir:

• $A_1, \ldots, A_n$: $1$ ile $n$ arasındaki erkekler tarafından şimdiye kadar teklif yapılan kızları temsil eden kümeler.

• $l$: teklifçi rolünü oynamış olan erkeklerin sayısı.

• $p$: şu anda teklif yapan erkek.

• $h$: şu anda kendisine teklif yapılan kız.

• $x_1, \ldots, x_n$: $1$ ile $n$ arasındaki kızlara şimdiye kadarki en iyi teklifi yapan erkekler veya kız hiçbir teklif almamışsa sıfır.

• $k_1, \ldots, k_n$: $1$ ile $n$ arasındaki kızların aldığı teklif sayıları.

• B0. $1 \le j \le n$ için $A_j = \emptyset$, $x_j = 0$ ve $k_j = 0$ olsun; ayrıca $l = 0$ olsun.

• B1. Eğer $l < n$ ise $l$'yi $1$ artırın ve $p = l$ yapın. Aksi takdirde, özel kız $G$'nin numarası $g$ olmak üzere $x_g$'yi çıktı olarak verin; ve $p = x_g$ yapın.

• B2. $h$, $1$ ile $n$ arasında düzgün olarak seçilen rastgele bir sayı olsun. (Erkek $p$'nin, kız $h$'ye teklif yaptığını söyleriz.) Eğer $h \in A_p$ ise (yani $p$'nin teklifi yineleniyorsa) bu adımı tekrarlayın. Aksi takdirde, $A_p$ yerine $A_p \cup \{h\}$ yazın ve B3 adımına geçin.

• B3. $k_h$'yi bir artırın. $1 - 1/k_h$ olasılıkla B2 adımına geri dönün (kız $h$'nin teklifi reddettiğini söyleriz). Aksi takdirde $p \leftrightarrow x_h$ değiş-tokuşunu yapın (kız teklifi kabul eder ve eski partneri başka birine teklif götürmek zorunda kalır). Eğer $p$'nin yeni değeri sıfır ise veya $h = g$ ve en az bir çıktı zaten gerçekleşmişse B1 adımına geri dönün; aksi takdirde B2 adımından devam edin. $\ddot{\smile}$

B Algoritması, yinelenen teklifler hariç, rastgele girdi üzerindeki önceki A Algoritmasını aslına sadık biçimde modeller. Yeni algoritmanın asla sonlanmadığına dikkat edin; A2 adımı, $P$'nin teklif yapacak kimsesi kalmadığında durur, ancak B2 adımı, $A_p = \{1, \ldots, n\}$ olduğunda sonsuza dek yinelenen teklifler yapmaya devam eder. B Algoritmasının ayrıntıları son derece basit değildir, ancak kısmen hiç sonlanmaması nedeniyle, olası davranışının belirli yönlerinin analiz edilmesinin oldukça kolay olduğunu göreceğiz.

4. Olasılıksal Ön Bilgiler

B Algoritması, B2 adımının $t$. kez gerçekleştirilmesine karşılık gelen $t = 1, 2, 3, \dots$ seviyelerindeki düğümlerden oluşan sonsuz bir ağaç, bir dallanma süreci (branching process) olarak düşünülebilir. Bu ağaçtaki her $\alpha$ düğümü, algoritmanın $t$ zamanına kadar olan olası davranışlarından birini temsil eden, kökten başlayan benzersiz bir yola karşılık gelir. Bu yol, $\alpha$ düğümündeki $(A_1, \dots, A_n, l, p, h, x_1, \dots, x_n, k_1, \dots, k_n)$ veri yapılarının değerlerini belirler.

Her $\alpha$ düğümünün, $\alpha_h^a$ ve $\alpha_h^r$'nin sırasıyla $h$ tarafından kabul edilen veya reddedilen bir teklifi takip eden düğümleri temsil ettiği $2n$ adet $\alpha_1^a, \alpha_1^r, \dots, \alpha_n^a, \alpha_n^r$ çocuğu (children) vardır. Eğer $h \in A_p$ ise, $\alpha$'dan $\alpha_h^a$'ya geçiş olasılığı $0$ ve $\alpha$'dan $\alpha_h^r$'ye geçiş olasılığı $1/n$'dir; bu durum, her zaman reddedilen bir yinelenen teklife karşılık gelir. Eğer $h \notin A_p$ ise, $\alpha$'dan $\alpha_h^a$'ya geçiş olasılığı $1/(k_h+1)n$ ve $\alpha$'dan $\alpha_h^r$'ye geçiş olasılığı $k_h/(k_h+1)n$'dir, burada $k_h$, B3 adımında $k_h+1$ haline gelen veri değeridir.

$\alpha$ düğümünün $\operatorname{Pr}(\alpha)$ olasılığı, kökten $\alpha$'ya giden yol üzerindeki geçiş olasılıklarının çarpımıdır; bu, B Algoritmasının $\alpha$ ile temsil edilen hesaplama yolunu izleme olasılığıdır. Her düğümden çocuklarına olan geçiş olasılıklarının toplamı $1$ olduğundan, belirli bir $t$ seviyesindeki tüm $\alpha$ düğümleri için $\operatorname{Pr}(\alpha)$ toplamı da $1$'dir.

Eğer $\rho$, algoritmanın $\alpha$'ya ulaştığı varsayımı altında olayın koşullu olasılığı ise, bir olayın $\alpha$ düğümünde yerel olasılık $\rho$ ile gerçekleştiğini söyleriz. Dolayısıyla, örneğin, bir teklifin $\alpha$'da kabul edilmesinin yerel olasılığı şudur: $$\frac{1}{n} \sum_{h \notin A_p} \frac{1}{k_h + 1}\ ,$$ yani olayın gerçekleştiği geçiş olasılıklarının toplamıdır.

$\alpha$'da yalnızca $\alpha$'dan çocuklarına olan geçiş olasılıklarına bağlı olan bir olaya hemen gerçekleşen olay (immediate event) denir. Daha genel olaylar, $\alpha$ düğümünün altındaki alt ağaçta (subtree) bir dizi düğüm geçişini içerebilir; bu tür tüm olayların $\alpha$'daki yerel olasılıkları yukarıda tanımlandığı gibidir. Örneğin, en fazla beş ardışık reddin hemen $\alpha$ düğümünü takip etmesinin yerel olasılığından bahsedebiliriz. $\alpha$'daki yerel olasılıklar, kökü $\alpha$ olan alt ağaç tarafından temsil edilen dallanma sürecindeki koşulsuz olasılıklara eşdeğerdir.

Kanıtlarımız sıklıkla, uygun bir şekilde ihmal edilebilir pertürbasyon ilkesi (principle of negligible perturbation) olarak adlandırılabilecek bir olasılık tahmin tekniğine dayanacaktır. Fikir, belirli düğümler arasındaki geçiş olasılıklarını değiştirerek, belirli bir olayın olasılığını hesaplamanın nispeten kolay olduğu bir “pertürbe edilmiş” (perturbed) $\operatorname{Pr}'$ olasılık dağılımı elde etmektir. $t$, ağacın bir seviyesi olsun ve $E$, $t$ seviyesindeki verilen olayın doğru olduğu tüm düğümlerin kümesi olsun. $C$, kökten $\alpha$'ya giden yol boyunca bir yerde olasılığı pertürbe edilmiş olan $t$ seviyesindeki tüm $\alpha$ düğümlerinin kümesi olsun; dolayısıyla, tüm $\alpha \notin C$ için $\operatorname{Pr}(\alpha) = \operatorname{Pr}'(\alpha)$ olur. Tüm $\alpha \notin C$ üzerinden toplamak ve tümleyenleri almak bize $\operatorname{Pr}(C) = \operatorname{Pr}'(C)$ olduğunu söyler. Eğer $\operatorname{Pr}(C)$ küçükse, pertürbasyonun $E$ olasılığı üzerindeki etkisi ihmal edilebilir düzeyde olacaktır, çünkü:

$$\begin{aligned} \left| \operatorname{Pr}(E) - \operatorname{Pr}'(E) \right| &= \left| \sum_{\alpha \in E} \operatorname{Pr}(\alpha) - \sum_{\alpha \in E} \operatorname{Pr}'(\alpha) \right| \\ &= \left| \sum_{\alpha \in E \cap C} \left( \operatorname{Pr}(\alpha) - \operatorname{Pr}'(\alpha) \right) \right| \\ &\le \sum_{\alpha \in C} \left| \operatorname{Pr}(\alpha) - \operatorname{Pr}'(\alpha) \right| \\ &\le \sum_{\alpha \in C} \left| \operatorname{Pr}(\alpha) \right| + \sum_{\alpha \in C} \left| \operatorname{Pr}'(\alpha) \right| = 2 \operatorname{Pr}(C)\ . \end{aligned}$$

Beklenen değerler de benzer bir şekilde tahmin edilebilir.

(İhmal edilebilir pertürbasyon ilkesi neredeyse gülünç derecede basit görünmektedir, ancak analizlerimizi şaşırtıcı derecede önemsiz olmayan şekillerde basitleştirdiğini göreceğiz. Bu fikir, integral altındaki fonksiyonun tanım kümesinin önemsiz kısımlarında değiştirilmesiyle integrallerin tahmin edildiği Laplace'ın asimptotik analiz yöntemine [9] benzer bir ruha sahiptir. Benzer bir diğer yöntem ise Wilkinson'ın, nümerik hataların yaklaşık verilerden tam yanıtlar elde edildiği varsayılarak incelendiği, meşhur “geriye doğru hata analizi” (backward error analysis) [13] tekniğidir; tam verilerden yaklaşık yanıtların hesaplandığı gerçek durumu doğrudan ele almak çok daha zordur.)

Aşağıdaki kanıtların birçoğu, kuyruk eşitsizlikleri (tail inequalities) olarak adlandıracağımız şu temel eşitsizlikleri kullanarak, olasılık dağılımlarının kuyruklarının tahminlerine dayanmaktadır: Let $$P(z) = p_0 + p_1 z + p_2 z^2 + \cdots = E(z^X)$$ negatif olmayan tam sayı değerler alan bir $X$ rastgele değişkeni için olasılık üreten fonksiyon (pgf) olsun. Bu durumda: $$\begin{aligned} \operatorname{Pr}(X \le r) &\le x^{-r} P(x) \quad 0 < x \le 1 \text{ için}\ ; \\ \operatorname{Pr}(X \ge r) &\le x^{-r} P(x) \quad x \ge 1 \text{ için}\ . \end{aligned}$$

Kanıt kolaydır, çünkü $0 < x \le 1$ ve $k \le r$ olduğunda ve ayrıca $x \ge 1$ and $k \ge r$ olduğunda $p_k \le x^{-r} p_k x^k$ eşitsizliğine sahibiz. Bu kolay kanıta rağmen, kuyruk eşitsizlikleri oldukça etkili sınırlara yol açar çünkü genellikle $x^{-r} P(x)$'i küçük yapacak $x$ değerini seçebiliriz.

(Bu temel eşitsizliklerin geçmişi bizi olasılık teorisinin ilk günlerine götürür. Bienaymé [1] ve Chebyshev [12] her $r>0$ için $\operatorname{Pr}((X-\mu)^2 \ge r) \le E((X-\mu)^2)/r$ olduğunu gözlemlemişlerdir. Kolmogorov [8] daha da ileri giderek, $E(f(X))$ mevcut olmak ve her $x \ge r$ için $f(x) \ge s > 0$ olmak koşuluyla, herhangi bir negatif olmayan $f(X)$ fonksiyonu için $\operatorname{Pr}(X \ge r) \le E(f(X))/s$ olduğunu belirtmiştir. Özel olarak [8], $f(x) = e^{cx}$ ve $c \ge 0$ olduğunda ikinci kuyruk eşitsizliğini elde ama ederiz. Chernoff [2] bu tür tahminlerin geniş uygulanabilirliğine dikkat çekmiştir.)

5. Olasılıksal Lemmalar

$n \to \infty$ iken B Algoritmasının davranışını ele alalım. Bir olayın gerçekleşmeme olasılığı $o(1)$ ise, yani gerçekleşmeme olasılığı $n \to \infty$ iken sıfıra yaklaşıyorsa, o olayın neredeyse kesinlikle (almost surely veya kısaca ‘n.k.’) gerçekleştiğini söyleyeceğiz. Bir olayın gerçekleşmeme olasılığı süper-polinomiyal olarak küçükse, yani sabit her $K$ için $O(n^{-K})$ ise, o olayın oldukça kesinlikle (quite surely veya kısaca ‘o.k.’) gerçekleştiğini söyleyeceğiz. Eğer $p(n)$ herhangi bir polinom fonksiyonu ise, $O(p(n))$ adet süper-polinomiyal olarak küçük olasılığın toplamı da süper-polinomiyal olarak küçüktür; dolayısıyla eğer $m = O(p(n))$ ise ve $E_1, \dots, E_m$ olayları tek tek o.k. gerçekleşiyorsa, ‘$E_1$ ve $\dots$ ve $E_m$’ birleşik olayı da o.k. gerçekleşir.

$0 < \delta < 1/2$ bir sabit olmak üzere $N = \lfloor n^{1+\delta} \rfloor$ olsun. Bu bölüm boyunca yalnızca B Algoritması tarafından yapılan ilk $N$ teklifi dikkate alacağız. Dolayısıyla, olayların olasılıkları, algoritma $\alpha$'ya giden yolu izlerken olayın gerçekleştiği $N+1$ anındaki tüm $\alpha$ düğümleri üzerinden $\operatorname{Pr}(\alpha)$ toplanarak ölçülür.

Lemma 1. Her kız o.k. en az $\frac{1}{2}n^{\delta}$ teklif ve en fazla $2n^{\delta}$ teklif (yinelenenler dahil) alır.

Bu lemmanın ve aşağıdakilerin ifadesi bilerek biraz belirsiz bırakılmıştır. Bir yorum, eğer $g$ belirli bir kız ise, o.k. belirtilen sayıda teklif alacağıdır. Başka bir yorum ise, o.k. tüm $n$ kızın belirtilen sayıda teklif alacağıdır. İkinci ifade, ‘o.k.’nin doğası gereği birincinin bir sonucudur; bu nedenle her lemmayı birinci (zayıf) yorumu kullanarak kanıtlayabiliriz, ancak her lemmayı ikinci (güçlü) yorumu kullanarak uygulayabiliriz.

Kanıt. $g$ kızlardan biri olsun ve $E_k$, $k$. teklifin $g$'ye yapılması olayı olsun. Bu hemen gerçekleşen olayın yerel olasılığı $1/n$'dir, çünkü B2 adımındaki her teklif düzgün rastgeledir. Dolayısıyla $g$'ye yapılan teklifler $1/n$ parametreli Bernoulli denemeleri gibidir ve ilk $N$ seviyede $g$ tarafından alınan toplam teklif sayısının pgf'si basitçe şudur: $$P(z) = \left( \frac{n-1+z}{n} \right)^N\ .$$

$r = \frac{1}{2}n^{\delta}$ olsun. İlk kuyruk eşitsizliği uyarınca, $g$'nin en fazla $r$ teklif alma olasılığı en fazla şudur: $$\left( \frac{1}{2} \right)^{-r} P\left( \frac{1}{2} \right) = 2^r \left( 1 - \frac{1}{2n} \right)^{\lfloor 2nr \rfloor} \le 2^r \left( 1 - \frac{1}{2n} \right)^{2nr-1} \le 2^{r+1} e^{-r}$$ çünkü $1-x \le e^{-x}$'tir ve bu süper-polinomiyal olarak küçüktür.

Benzer şekilde, eğer $r = 2n^{\delta}$ ise, ikinci kuyruk eşitsizliği bize $g$'nin $r$ veya daha fazla teklif alma olasılığının en fazla şunlar olduğunu söyler: $$2^{-r} P(2) = 2^{-r} \left( 1 + \frac{1}{n} \right)^{\lfloor \frac{1}{2}nr \rfloor} \le 2^{-r} \left( 1 + \frac{1}{n} \right)^{\frac{1}{2}nr} \le 2^{-r} e^{\frac{1}{2}r}$$ çünkü $1+x \le e^x$ olup bu da yine süper-polinomiyal olarak küçüktür. $\ddot{\smile}$

Bir erkeğin, B1 veya B3 adımında teklifçi $p$ olduğunda bir teklif serisine (run of proposals) başladığını söyleyelim; serisi, sonraki tekliflerinden biri B3 adımında ilk kez kabul edildiğinde sona erer. Dallanma süreci açısından, bir geçiş $\alpha$ düğümünden $\alpha_h^r$ biçimindeki bir “reddedilmiş” düğüme olduğunda seri devam eder ve $\alpha$'dan $\alpha_h^a$ biçimindeki bir “kabul edilmiş” düğüme geçişte sona erer.

Lemma 2. Her erkek o.k. en fazla $2n^{\delta}$ teklif serisi başlatır.

Kanıt. $b$ erkeklerden biri olsun. Onun ilk teklif serisi, B1 adımında $l$'nin $b$'ye yükselmesinden hemen sonra başlar; sonraki serileri ise B1 adımında $p$ $x_g=b$ yapıldıktan veya B3 adımında $x_h=b$ yapıldıktan hemen sonra başlar. Dolayısıyla, serilerinden en fazla ikisi B1 adımında $p$'nin $b$ olmasından hemen sonra başlar.

Diğer seriler, B3 adımında $p$ $b=x_h$ olduğunda gerçekleşir; ve bu durum ancak $h$, $b$'yi önceki serisinin sonunda kabul eden kız ise gerçekleşebilir. $E_t$, $t$ anındaki teklifin, $b$'yi en son kabul eden kıza (veya $b$ henüz hiç kabul edilmemişse 1. kıza) yapılması biçimindeki hemen gerçekleşen olay olsun. O halde $b$ tarafından başlatılan seri sayısı en fazla 2 artı $E_t$'nin gerçekleşme sayısıdır; başka bir deyişle, $b$ ancak $E_t$ $r-2$ veya daha fazla kez gerçekleşirse $r$ veya daha fazla seri başlatabilir. Ancak $E_t$'nin yerel olasılığı $1/n$'dir, bu nedenle yine şu binom pgf'sine sahibiz: $$P(x) = \left( \frac{n-1+x}{n} \right)^N$$ terimlerin dağılımı için.

Şimdi $r=2n^{\delta}$ alarak kanıtı Lemma 1'deki gibi tamamlarız; $r$ veya daha fazla seri olasılığı tüm $x>1$ için en fazla $x^{2-r}P(x)$ olur. Ve bu sınırın $x=2$ olduğunda süper-polinomiyal olarak küçük olduğunu gördük. $\ddot{\smile}$

Lemma 3. Her seri o.k. en fazla $n^{\delta}(\log n)^2$ yinelenmeyen teklif içerir.

Kanıt. Sabit herhangi bir $t$ ($1 \le t \le N$) anı için, $t$'de başlayan bir serinin o.k. belirtilen özelliğe sahip olduğunu kanıtlayacağız. $\alpha$ $t$ seviyesindeki herhangi bir düğüm olsun ve $P(\alpha,m,t)$ , hangisi önce gelirse, $N+1$ anına ulaşmadan önce veya ilk kabulden önce, $\alpha$'yı hemen takip eden tekliflerin en az $m$ adet reddedilen yinelenmeyen teklif içermesinin yerel olasılığı olsun. O halde şu yinelemeli (recursive) formüllere sahibiz: $$P(\alpha,m,t) = \begin{cases} 1\,, & \text{eğer } m=0\ ; \\ 0\,, & \text{eğer } m>0 \text{ ve } t=N+1\ ; \\ \displaystyle \sum_{h \in A_p} \frac{P(\alpha_h,m,t+1)}{n} + \sum_{h \notin A_p} \frac{k_h P(\alpha_h^r,m-1,t+1)}{(k_h+1)n}\,, & \text{aksi takdirde.} \end{cases}$$

Lemma 1 uyarınca, $1 \le h \le n$ için $k_h \le 2n^{\delta}$ olduğunu varsayabiliriz. (Bu varsayımın geçerliliği aşağıda tartışılmaktadır.) O halde $N+1-t$ üzerinden tümevarımla şu elde edilir: $$P(\alpha,m,t) \le \left( \frac{2n^{\delta}}{2n^{\delta}+1} \right)^m\ .$$

Şimdi $m = \lfloor n^{\delta}(\log n)^2 \rfloor$ seçersek, $\alpha$'da başlayan bir seride $m$'den fazla yinelenmeyen teklif olmasının yerel olasılığı en fazla şudur: $$\exp\left( \frac{-m}{2n^{\delta}+1} \right) = \exp\left( -\frac{1}{2}(\log n)^2 + o(1) \right)\ .$$

$\operatorname{Pr}(\alpha)$ ile çarpmak ve $t$ seviyesindeki tüm $\alpha$ üzerinden toplamak, en fazla $\exp(-\frac{1}{2}(\log n)^2 + o(1))$ olan ve süper-polinomiyal olarak küçük olan bir toplam olasılık verir. $\ddot{\smile}$

Önceki kanıt, ‘Lemma 1 uyarınca, $k_h \le 2n^{\delta}$ varsayabiliriz’ sözleriyle belirtilen elverişli bir basitleştirme kullanmaktadır. Yaptığımız varsayım o.k. geçerlidir, ancak her zaman doğru değildir; dahası, bu $N+1$ anına dair olasılıksal bir iddiadır. Dolayısıyla, geçmişteki olasılık hesaplamalarını etkilemek için geleceği yanıltıcı bir şekilde kullanmadığımızdan emin olmalıyız. Kesin bir gerekçelendirme, ihmal edilebilir pertürbasyon ilkesine başvurularak yapılabilir: $k_h \le 2n^{\delta}$ varsayımı geçersiz olduğunda geçiş olasılıklarını yeniden hesaplarız.

Daha kesin olarak, dallanma sürecindeki herhangi bir $\alpha$ düğümü için, $\alpha$'dan $\alpha_h^a$ ve $\alpha_h^r$'ye olan pertürbe edilmiş geçiş olasılıklarının sırasıyla $1/(k'_h+1)n$ ve $k'_h/(k'_h+1)n$ olmasını sağlarız, burada: $$k'_h = \min(k_h, 2n^{\delta})\ .$$

Lemma 3'ün kanıtı, $P(\alpha,m,t)$ formülünde $k_h$ yerine $k'_h$ kullanılarak pertürbe edilmiş dallanma süreci için geçerlidir. Dolayısıyla kanıt, pertürbe edilmiş dallanma sürecindeki her serinin o.k. en fazla $n^{\delta}(\log n)^2$ yinelenmeyen teklif içerdiğini kanıtlar. Ve bu aynı sonuç, pertürbe edilmemiş dallanma sürecinde de o.k. geçerlidir, çünkü bunun yanlış olma olasılığı en fazla $2\operatorname{Pr}(C)$ kadar artabilir, burada $C$, kök ile $N+1$ seviyesi arasında bazı geçiş olasılıklarının pertürbe edilmiş olması koşuludur. Lemma 1 bize $\operatorname{Pr}(C)$'nin süper-polinomiyal olarak küçük olduğunu söyler, çünkü $N+1$ seviyesindeki bir $\alpha$ düğümüne giden yol, yalnızca $\alpha$ ile temsil edilen durumdaki bir kız $N+1$ anından önce $2n^{\delta}$'den fazla teklif almışsa pertürbe edilmiş bir geçiş olasılığı içerir.

Lemma 4. Her erkek o.k. en fazla $2n^{2\delta}(\log n)^2$ kıza teklif götürür.

Kanıt. Lemma 2 ve 3'ün sonuçlarını çarpın. $\ddot{\smile}$

Lemma 5. Her seri o.k. en fazla $n^{\delta}(\log n)^2$ teklif içerir.

Kanıt. $t$ sabit bir zaman ($1 \le t \le N$) olsun ve $\alpha$, $t$ seviyesindeki herhangi bir düğüm olsun. Bir teklif, şu yerel olasılıkla reddedilir: $$\sum_{h \in A_p} \frac{1}{n} + \sum_{h \notin A_p} \frac{k_h}{(k_h+1)n}\ .$$

Önceki lemmalar ve ihmal edilebilir pertürbasyon ilkesi uyarınca, $|A_p| \le 2n^{2\delta}(\log n)^2$ ve $k_h \le 2n^{\delta}$ olduğunu varsayabiliriz. $\rho = |A_p|/n$ olsun. O halde bir serinin bir adım daha devam etmesinin yerel olasılığı en fazla şudur: $$\rho + (1-\rho)\frac{2n^{\delta}}{2n^{\delta}+1} = \frac{2n^{\delta} + \rho}{2n^{\delta}+1} \le \frac{2n^{\delta} + 2n^{2\delta - 1}(\log n)^2}{2n^{\delta}+1} = \rho'\ .$$

(Eğer varsayımlar başarısız olursa ve yerel olasılık gerçekten bu $\rho'$ sayısından büyükse, reddedilme olasılığını yapay olarak azaltıp kabul edilme olasılığını artırarak bunu pertürbe edebiliriz. Örneğin, $1 \le h \le n$ için $\alpha$'dan $\alpha_h^a$ ve $\alpha_h^r$'ye olan geçiş olasılıklarını sırasıyla $(1-\rho')/n$ ve $\rho'/n$ olarak tanımlayabiliriz. Pertürbe edilmiş algoritmanın orijinal algoritma gibi davranması gerekmez; örneğin, bir erkeğin yinelenen teklifleri pozitif olasılıkla kabul edilebilir. İhmal edilebilir pertürbasyon ilkesi, yalnızca ağacın düğümlerinin aynı kalmasını ve geçiş olasılıklarının kanıtın tüm varsayımlarıyla tutarlı olmasını gerektirir.)

$\delta < 1/2$ olduğundan, $m$ adet ardışık yinelenen veya reddedilen teklifin yerel olasılığı en fazla şudur: $$(\rho')^m < \left( 1 - \frac{1}{3n^{\delta}} \right)^m$$ yeterince büyük $n$ değerleri için. Dolayısıyla kanıtı Lemma 3'teki gibi tamamlayabiliriz. $\ddot{\smile}$

Bu kanıtta ihmal edilebilir pertürbasyon ilkesinin, gelecekteki bir $>t$ anında başarısız olabilecek varsayımları kullanarak $t$ anında başlayan olayların olasılıklarını tahmin etmemizi meşru kıldığına dikkat edin. (Dolayısıyla, $|A_p|$ bir serinin başında $\le 2n^{2\delta}(\log n)^2$ olabilir ancak sonunda olmayabilir.) Yalnızca varsayımların $t$ anında geçerli olmasını gerektiren daha zayıf bir ilkeye dayanan argümanlar daha karmaşık olurdu; $|A_p|$'nin her zaman adımında $1$'den fazla büyüyemeyeceğini savunmamız gerekirdi ve üst sınırımız $(\rho')^m$ yerine $(\rho'+m/(n(2n^{\delta}+1)))^m$ olurdu.

Lemma 6. Her erkek o.k. en fazla $2n^{2\delta}(\log n)^2$ teklif yapar.

Kanıt. Lemma 2 ve 5'in sonuçlarını çarpın. $\ddot{\smile}$

Lemma 7. Her erkek o.k. belirli bir kıza en fazla $\log n$ kez teklif götürür.

Kanıt. $b$ erkeklerden biri ve $j$ kızlardan biri olsun. Süreci, $b$ $n$ adet teklif yaptıktan sonra sonraki tekliflerinin hiçbirinin $j$'ye yapılma olasılığı pozitif olmayacak şekilde pertürbe edelim. Bu pertürbasyon ihmal edilebilirdir, çünkü $b$ o.k. $n$'den az teklif yapar (Lemma 6).

Dahası, eğer $b$ $N+1$ anına kadar $n$ teklif yapmamışsa, bunu $n$ kez yapana kadar teklif vermeye devam ettiğini varsayalım. Bu durum, $j$'ye yaptığı teklif sayısını yalnızca artırabilir.

$b$'nin $j$'ye yaptığı toplam teklif sayısının pgf'si o halde şudur: $$P(z) = \left( \frac{n-1+z}{n} \right)^n\ ,$$ çünkü $b$'nin amnezisi vardır; $n$ teklifinin her biri kızlar arasında düzgündür. Dolayısıyla $j$'ye $\log n$'den fazla teklif yapmış olma olasılığı en fazla şudur: $$(\ln n)^{-\log n} \left( \frac{n-1+\ln n}{n} \right)^n = \exp\bigl(-(\log n)(\ln\ln n) + O(\ln n)\bigr)\ ,$$ ve bu süper-polinomiyal olarak küçüktür. $\ddot{\smile}$

Bu arada, burada [4] (s. 435) kaynağının, tabanın önemsiz olduğu bağlamlarda logaritma için ‘$\log$’ kullanılırken, ‘$\ln$’in doğal logaritmanın özel durumunu gösterdiği kuralını benimsedik.

Lemma 8. Her kız o.k. en az $\frac{1}{2}n^{\delta}/\log n$ yinelenmeyen teklif alır.

Kanıt. Bir kız Lemma 1 uyarınca o.k. $\frac{1}{2}n^{\delta}$ teklif alır, ancak Lemma 7 uyarınca herhangi bir erkekten en fazla $\log n$ teklif alır. $\ddot{\smile}$

6. Ana Teorem

B Algoritmasının n.k. $\Theta(\log n)$ adet çıktı ürettiğini göstermeye neredeyse hazırız. (Bu nihai sonuç “neredeyse kesin” olacak ancak “oldukça kesin” olmayacaktır.) Ancak önce ilk çıktının zamanını analiz etmemiz gerekiyor, çünkü B1 ve B3 adımları o anda davranışlarını değiştirmektedir.

İlk çıktı, $n$ kızın her biri en az bir teklif aldığında gerçekleşir. Bunun, $N = \lfloor n^{1+\delta} \rfloor$ anından çok daha önce o.k. gerçekleştiğini kanıtlayabiliriz:

Lemma 9. Let $N_0 = \lfloor n \ln n \ln\ln n \rfloor$ olsun. Her kız, ilk $N_0$ adımda o.k. en az bir teklif ve en fazla $\ln n\,(\ln\ln n)^2$ teklif alır.

Kanıt. $g$'ye yapılan tekliflerin pgf'si şunu sağlar: $$P(x) = \left( \frac{n-1+x}{n} \right)^{N_0} = \exp\bigl((x-1)\ln n\ln\ln n + o(1)\bigr)$$ tüm gerçel $x$ değerleri için. $g$'nin hiç teklif almama olasılığı $P(0) = \exp\bigl(-\ln n\ln\ln n + o(1)\bigr)$ olur; $\ln n\,(\ln\ln n)^2$ veya daha fazla alma olasılığı ise en fazla şudur: $$2^{-\ln n\,(\ln\ln n)^2} P(2) = \exp\bigl(-(\ln 2)(\ln n)(\ln\ln n)^2 + \ln n\ln\ln n + o(1)\bigr)\ .$$ Bu sınırların her ikisi de süper-polinomiyal olarak küçüktür. $\ddot{\smile}$

Lemma 10. Yinelenmeyen $m$ teklif alan bir kız, $m \to \infty$ iken $1 - O(m^{-\epsilon^2\!/2})$ olasılıkla bunların en az $(1-\epsilon)\ln m$ tanesini kabul edecektir. $m \to \infty$ iken $1 - O(m^{-\epsilon^2\!/2 + \epsilon^3\!/6})$ olasılıkla bunların en fazla $(1+\epsilon)\ln m$ tanesini kabul edecektir. Ve $m \to \infty$ iken $1 - O\bigl(\exp\bigl(-m/(\ln m)^2 + 7m\,(\ln\ln m)/(\ln m)^3\bigr)\bigr)$ olasılıkla bunların en fazla $m/(\ln m)^3$ tanesini kabul edecektir.

Kanıt. Kız $k$. teklifi $1/k$ olasılıkla kabul eder, dolayısıyla toplam kabul sayısının pgf'si şudur: $$P(z) = \left( \frac{z}{1} \right) \left( \frac{1+z}{2} \right) \ldots \left( \frac{m-1+z}{m} \right) = \binom{m-1+z}{m} = \frac{1}{\Gamma(z) m^{\underline{1-z}}}\ .$$ (Faktöriyel kuvvetler için $z^{\underline{w}} = z!/(z-w)!$ gösterimi [4] s. 211'de tartışılmaktadır.)

$(1-\epsilon)\ln m$'den daha azını kabul etme olasılığı en fazla şudur: $$(1-\epsilon)^{-(1-\epsilon)\ln m} P(1-\epsilon) = \frac{m^{-(1-\epsilon)\ln(1-\epsilon)}}{\Gamma(1-\epsilon)\, m^{\underline{\epsilon}}} \le \frac{m^{\epsilon - \epsilon^2\!/2}}{\Gamma(1-\epsilon)\, m^{\underline{\epsilon}}}\ ,$$ ve bu $O(m^{-\epsilon^2\!/2})$ olur çünkü $m^{\underline{\epsilon}} = m^{\epsilon} + O(m^{\epsilon-1})$. (Bkz. [4]'teki alıştırma 9.44'ün yanıtı.)

Benzer şekilde, $(1+\epsilon)\ln m$'den fazlasını kabul etme olasılığı en fazla şudur: $$(1+\epsilon)^{-(1+\epsilon)\ln m} P(1+\epsilon) \le \frac{m^{-\epsilon - \epsilon^2\!/2 + \epsilon^3\!/6}}{\Gamma(1+\epsilon)\, m^{\underline{- \epsilon}}} = O(m^{-\epsilon^2\!/2 + \epsilon^3\!/6})\ .$$

Bunlardan $m_0 = m/(\ln m)^3$'den fazlasını kabul etme olasılığı en fazla şudur: $$\begin{aligned} m_0^{-m_0} P(m_0) &= \exp\bigl(-m_0\ln m_0 + \ln\Gamma(m+m_0) - \ln\Gamma(m_0) - \ln m!\bigr) \\ &= \exp\bigl(-m_0(\ln m - 6\ln\ln m + O(1))\bigr) \end{aligned}$$ Stirling yaklaşımı uyarınca. $\ddot{\smile}$

Teorem. Kızların ve erkeklerin bağımsız rastgele tercih sıralamalarına sahip olduğunu varsayalım ve $G$ kızlardan biri olsun. $c < 1/2$ bir sabit ve $C > 1$ bir sabit olsun. O halde $G$ n.k. en az $c\ln n$ ve en fazla $C\ln n$ kararlı kocaya sahiptir.

Kanıt. $G$'nin kararlı kocaları, B Algoritmasına eşdeğer olan A Algoritması tarafından çıktı olarak verilir. Çıktı sayısı, $g$'nin B Algoritmasında bir teklifi kabul etme sayısı eksi ilk çıktıdan önce bir teklifi kabul etme sayısıdır.

Lemma 8'de, $\delta$ $0$ ile $1/2$ arasında herhangi bir sabit olmak üzere, B Algoritması tarafından yapılan ilk $n^{1+\delta}$ teklif arasında $g$'nin o.k. en az $\frac{1}{2}n^{\delta}/\log n$ yinelenmeyen teklif alacağını gösterdik. Dolayısıyla, Lemma 10'un ilk tahminine göre, n.k. en az $(1-\epsilon)\delta\ln n - O(\log\log n)$ teklif kabul edecektir.

Diğer yandan, $g$ toplamda en fazla $n$ yinelenmeyen teklif alır. Dolayısıyla, Lemma 10'un ikinci tahminine göre, n.k. bunların en fazla $(1+\epsilon)\ln n$ tanesini kabul edecektir.

Dahası, Lemma 9 uyarınca, ilk çıktı o.k. kendisi $m = \ln n\,(\ln\ln n)^2$ yinelenmeyen teklif almadan önce gerçekleşir. Dolayısıyla (Lemma 10'un üçüncü tahminine göre) en fazla şu kadarını kabul edecektir: $$\frac{m}{(\ln m)^3} = \frac{\ln n}{\ln\ln n} \left( 1 + O\left( \frac{\log\log\log n}{\log\log n} \right) \right) = o(\ln n)$$ ilk çıktıdan önce, şu olasılıkla: $$1 - O\left( \exp\left( -\ln n + O\left( \frac{\log n\log\log\log n}{\log\log n} \right) \right) \right) = 1 - \frac{1}{n^{1+o(1)}}\ .$$

Dolayısıyla, $\delta$ ve $\epsilon$'u $(1-\epsilon)\delta > c$ ve $1+\epsilon < C$ olacak şekilde seçersek, tüm büyük $n$ değerleri için çıktı sayısı n.k. $c\ln n$ değerini aşacak ve $C\ln n$ değerinden küçük olacaktır. $\ddot{\smile}$

7. Notlar

Teoremin kanıtının incelenmesi, sonucun, $\gamma$ hem $(1-2c)^2\!/2$ hem de $(C-1)^2\!/2 - (C-1)^3\!/6$ değerlerinden küçük herhangi bir sabit olmak üzere, $1-O(n^{-\gamma})$ olasılığıyla geçerli olduğunu göstermektedir.

Bu tahmini $1-O(n^{-1})$ seviyesine iyileştiremeyiz, çünkü $G$'ye yapılan ilk teklifin onun en çok beğendiği $\sqrt{\ln n}$ erkekten birinden gelme olasılığı $\sqrt{\ln n}/n$'dir. Böyle bir durumda en fazla $\sqrt{\ln n}$ kararlı kocaya sahip olabilir, çünkü A Algoritması tarafından bulunan ilk kararlı evlilik her kıza en az tercih ettiği kararlı kocayı verir.

Teoremimiz, her kararlı koca en az bir kararlı eşlemenin parçası olduğundan, rastgele tercihlerin n.k. sınırsız sayıda kararlı eşlemeyi garanti ettiğini kanıtlamaktadır. Kararlı eşlemelerin n.k. alt sınırının bundan daha hızlı, diyelim ki $\Omega((\log n)^2)$ olarak büyüdüğü gösterilebilir mi? Pittel [11], beklenen kararlı eşleme sayısının asimptotik olarak $e^{-1} n \ln n$ olduğunu kanıtlamıştır. Ancak Pittel'in teoremi, çok sayıda eşlemenin neredeyse kesinlikle gerçekleşeceğini kanıtlamaz; belirli tercih matrislerinin en az $2^{n-1}$ kararlı eşlemeye yol açtığı inşalar bilinmektedir [6] ve bu tür örnekler nispeten yüksek beklenen değeri açıklayacak kadar yaygın olabilir.

Kaynakça

• [1] J. Bienaymé, “Considérations à l'appui de la découverte de Laplace sur la loi de probabilité dans la méthode des moindres carrés,” Comptes Rendus hebdomadaires des séances de l'Académie des Sciences (Paris) 37 (1853), 309–324.
• [2] Herman Chernoff, “A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations,” Annals of Mathematical Statistics 23 (1952), 493–507.
• [3] D. Gale and L. S. Shapley, “College admissions and the stability of marriage,” American Mathematical Monthly 69 (1962), 9–15.
• [4] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics, Addison-Wesley, 1989.
• [5] Dan Gusfield, “Three fast algorithms for four problems in stable marriage,” SIAM Journal on Computing 16 (1987), 111–128.
• [6] Robert W. Irving and Paul Leather, “The complexity of counting stable marriages,” SIAM Journal on Computing 15 (1986), 655–667.
• [7] Donald E. Knuth, Mariages Stables, Les Presses de l'Université de Montréal, 1976.
• [8] A. Kolmogoroff, Grundbegriffe der Wahrscheinlichkeitsrechnung, Springer, 1933. English translation by Nathan Morrison, Foundations of the Theory of Probability, Chelsea, 1950.
• [9] P. S. La Place, “Mémoire sur les approximations des formules qui sont fonctions de très grands nombres,” Mémoires de l'Academie royale des Sciences de Paris (1782), 1–88. Reprinted in his Œuvres Complètes 10, 207–291.
• [10] D. G. McVitie and L. B. Wilson, “The stable marriage problem,” Communications of the ACM 14 (1971), 486–492.
• [11] Boris Pittel, “The average number of stable matchings,” (sunuldu).
• [12] P.-L. Tchébychef, “O srednikh velichinakh,” Matematicheskiĭ Sbornik' 2 (1867), 1–9; reprinted in his Polnoe Sobranie Sochineniĭ, volume 2, 431–437. French translation, “Des valeurs moyennes,” Journal de Mathématiques pures et appliquées, series 2, 12 (1867), 177–184; reprinted in his Œuvres, volume 1, 685–694.
• [13] J. H. Wilkinson, Rounding Errors in Algebraic Processes, Prentice-Hall, 1963.

[^1]: Bu araştırma kısmen CCR-86-10181 sayılı hibe kapsamında Ulusal Bilim Vakfı (NSF) ve N00014-87-K-0502 sayılı sözleşme kapsamında Deniz Araştırmaları Ofisi (ONR) tarafından desteklenmiştir.