Stasioneritas dan Ergodisitas

Stasioneritas dan Ergodisitas

Atribusi sumber. Unit ini mengadaptasi Continuous Time Markov Chains karya Thomas J. Sargent dan John Stachurski, tepat pada komit 8b06e0aa5a438692445b2c896f9d238c5a7d5eb7, berkas lectures/ergodicity.md. Sumber dan adaptasi ini tunduk pada CC BY-SA 4.0; seluruh atribusi dan hak penulis sumber dipertahankan. Edisi independen ini tidak menyiratkan dukungan penulis maupun QuantEcon.

Selain yang tersedia di lingkungan ilmiah Python, kuliah ini memerlukan QuantEcon, NumPy, Matplotlib, dan SciPy.

# Dependensi unit disediakan oleh lingkungan luring yang dikunci.
# Tidak ada instalasi paket pada saat pembaca dijalankan.

Catatan adaptasi hilir. Sumber menjalankan !pip install quantecon di dalam pembaca. Instalasi saat eksekusi dihapus agar edisi ini dapat diputar ulang secara luring dan deterministik. Sel kode serta posisinya dipertahankan sebagai jejak asal-usul.

Gambaran Umum

Dalam kuliah ini kita membahas kestabilan dan perilaku kesetimbangan rantai Markov waktu kontinu.

Sebagai salah satu gambaran tentang pentingnya teori ini, tinjau sistem antrean, yang sering dimodelkan sebagai rantai Markov waktu kontinu.

Teori antrean digunakan dalam penerapan seperti

• penanganan pasien yang tiba di rumah sakit;
• perancangan optimal proses manufaktur;
• permintaan kepada peladen berkas;
• lalu lintas udara; dan
• pelanggan yang menunggu layanan bantuan melalui telepon.

Salah satu topik utama dalam teori antrean adalah perilaku rata-rata dalam jangka panjang.

• Apakah panjang antrean akan tumbuh tanpa batas?
• Jika tidak, adakah suatu bentuk kesetimbangan jangka panjang?
• Jika ada, berapakah waktu tunggu rata-rata dalam kesetimbangan itu?
• Berapakah panjang rata-rata antrean selama satu minggu atau satu bulan?

Kita akan menggunakan impor berikut.

import numpy as np
import matplotlib.pyplot as plt
import quantecon as qe
from scipy.linalg import expm

from matplotlib import cm
from mpl_toolkits.mplot3d.art3d import Poly3DCollection

Catatan adaptasi hilir. Impor scipy as sp, numba.njit, dan Axes3D pada sumber tidak digunakan oleh sel-sel unit ini dan dihapus. Semua impor yang benar-benar diperlukan untuk pemutaran ulang tetap ada.

Distribusi Stasioner

Definisi

Misalkan \(S\) terhitung.

Ingat bahwa, untuk rantai Markov waktu diskret dengan matriks Markov \(P\) pada \(S\), suatu distribusi \(\psi\) disebut stasioner bagi \(P\) jika \(\psi P=\psi.\)

Artinya, jika \(X_t\) berdistribusi \(\psi\), maka \(X_{t+1}\) juga berdistribusi \(\psi\).

Untuk rantai Markov waktu kontinu, definisinya serupa.

Diberikan semigrup Markov \((P_t)\) pada \(S\), distribusi \(\psi^*\in\dD\) disebut stasioner bagi \((P_t)\) jika

\[ \psi^* P_t = \psi^* \text{ untuk setiap } t \geq 0. \]

Sebagai contoh, kita meninjau kembali rantai pada \(S=\{0,1,2\}\) dengan matriks intensitas

Q = ((-3, 2, 1),
     (3, -5, 2),
     (4, 6, -10))

Gambar berikut pernah ditampilkan sebelumnya, tetapi kini sebuah titik hitam menandai distribusi yang tampaknya didekati ketiga lintasan.

(Dalam skema warnanya, lintasan berubah dari warna panas ke warna sejuk seiring berjalannya waktu.)

Tampilkan kode sel tersembunyi 1

def unit_simplex(angle):
    
    fig = plt.figure(figsize=(8, 6))
    ax = fig.add_subplot(111, projection='3d')

    vtx = [[0, 0, 1],
           [0, 1, 0], 
           [1, 0, 0]]
    
    tri = Poly3DCollection([vtx], color='darkblue', alpha=0.3)
    tri.set_facecolor([0.5, 0.5, 1])
    ax.add_collection3d(tri)

    ax.set(xlim=(0, 1), ylim=(0, 1), zlim=(0, 1), 
           xticks=(1,), yticks=(1,), zticks=(1,))

    ax.set_xticklabels(['$(1, 0, 0)$'], fontsize=12)
    ax.set_yticklabels(['$(0, 1, 0)$'], fontsize=12)
    ax.set_zticklabels(['$(0, 0, 1)$'], fontsize=12)

    ax.xaxis.majorTicks[0].set_pad(15)
    ax.yaxis.majorTicks[0].set_pad(15)
    ax.zaxis.majorTicks[0].set_pad(35)

    ax.view_init(30, angle)

    # Pindahkan sumbu ke titik asal.
    ax.xaxis._axinfo['juggled'] = (0, 0, 0)
    ax.yaxis._axinfo['juggled'] = (1, 1, 1)
    ax.zaxis._axinfo['juggled'] = (2, 2, 0)
    
    ax.grid(False)
    
    return ax

Q = np.array(Q)
ψ_00 = np.array((0.01, 0.01, 0.98))
ψ_01 = np.array((0.01, 0.98, 0.01))
ψ_02 = np.array((0.98, 0.01, 0.01))

ax = unit_simplex(angle=50)    

def flow_plot(ψ, h=0.001, n=300, angle=50):
    colors = cm.jet_r(np.linspace(0.0, 1, n))

    x_vals, y_vals, z_vals = [], [], []
    for t in range(n):
        x_vals.append(ψ[0])
        y_vals.append(ψ[1])
        z_vals.append(ψ[2])
        ψ = ψ @ expm(h * Q)

    ax.scatter(x_vals, y_vals, z_vals, c=colors, s=20, alpha=0.2, depthshade=False)

flow_plot(ψ_00)
flow_plot(ψ_01)
flow_plot(ψ_02)

# Tambahkan distribusi stasioner.
P_1 = expm(Q)
mc = qe.MarkovChain(P_1)
ψ = mc.stationary_distributions[0]
ax.scatter(ψ[0], ψ[1], ψ[2], c='k', s=30, depthshade=False)

plt.show()

Alternatif aksesibel untuk gambar. Simpleks probabilitas tiga keadaan memiliki titik sudut \((1,0,0)\), \((0,1,0)\), dan \((0,0,1)\). Tiga lintasan dimulai dekat masing-masing titik sudut, lalu bergerak menuju titik hitam yang sama. Titik itu adalah \(\psi^*\approx(0{,}520548,0{,}356164,0{,}123288)\). Urutan warna panas ke warna sejuk menyatakan arah waktu; informasi matematis utamanya adalah bahwa ketiga kondisi awal mendekati distribusi yang sama.

Catatan koreksi hilir. Ketiga vektor awal pada sumber memakai 0.99 bersama dua koordinat 0.01, sehingga jumlah massanya 1.01 dan lintasan tidak berada pada simpleks probabilitas. Koordinat besar diperbaiki menjadi 0.98; setiap vektor awal kini berjumlah satu, dan evolusi Markovnya dapat mendekati distribusi stasioner yang ditandai.

Titik hitam tersebut adalah distribusi stasioner \(\psi^*\) dari semigrup Markov \((P_t)\) yang dibangkitkan oleh \(Q\).

Distribusi itu dihitung dengan atribut stationary_distributions dari kelas MarkovChain QuantEcon, dengan memilih sembarang \(t>0\)—misalnya \(t=1\)—lalu menyelesaikan \(\psi P_1=\psi\).

Di bawah ini kita menunjukkan bahwa, untuk pilihan \(Q\) tersebut, distribusi stasioner \(\psi^*\) tunggal dalam \(\dD\) karena rantainya tak tereduksi.

Lebih lanjut, seperti disarankan oleh gambar, \(\psi P_t\to\psi^*\) ketika \(t\to\infty\) bagi setiap \(\psi\in\dD\).

Stasioneritas melalui Generator

Dalam banyak kasus, distribusi stasioner lebih mudah dikenali melalui generator semigrup daripada melalui semigrup itu sendiri.

Ini serupa dengan gagasan bahwa suatu titik \(\bar x\) dalam \(\RR^d\) bersifat stasioner bagi ODE vektor \(x'_t=F(x_t)\) ketika \(F(\bar x)=0\).

(Di sini \(F\) merupakan deskripsi infinitesimal dan karena itu analog dengan generator.)

Hasil berikut tetap benar di bawah syarat yang lebih lemah, tetapi versi yang dinyatakan di sini mudah dibuktikan dan mencukupi untuk penerapan kita.

Ketaktereduksian dan Ketunggalan

Misalkan \((P_t)\) suatu semigrup Markov pada \(S\), dan tinjau sembarang keadaan \(x,y\in S\).

Kita mengatakan bahwa keadaan \(y\) dapat dicapai dari keadaan \(x\) jika terdapat \(t\geq0\) sedemikian sehingga \(P_t(x,y)>0\).

Kita mengatakan bahwa \(x\) dan \(y\) berkomunikasi jika \(x\) dapat dicapai dari \(y\) dan \(y\) dapat dicapai dari \(x\).

Semigrup Markov \((P_t)\) pada \(S\) disebut tak tereduksi jika setiap pasangan \(x,y\) dalam \(S\) berkomunikasi.

Kita mencari karakterisasi ketaktereduksian \((P_t)\) melalui generatornya.

Sebagai langkah awal, kita mengatakan bahwa terdapat aliran probabilitas positif-\(Q\) dari \(x\) ke \(y\) jika ada barisan berhingga \((z_i)_{i=0}^m\) dalam \(S\) yang dimulai di \(x=z_0\), berakhir di \(y=z_m\), dan memenuhi \(Q(z_i,z_{i+1})>0\) bagi setiap \(i\).

teorema ekuivalensi ketercapaian langsung menghasilkan akibat kuat berikut.

Catatan pelengkapan hilir. Untuk pasangan diagonal, kepositifan mengikuti langsung dari suku \(k=0\) dalam persamaan unifexp, yang memberi \(P_t(x,x)\geq e^{-mt}>0\) ketika \(m>0\); jika \(m=0\), maka \(P_t=I\). Untuk pasangan berbeda, ekuivalensinya adalah teorema ekuivalensi ketercapaian.

Kestabilan Asimtotik

Kita menyebut semigrup Markov \((P_t)\) stabil asimtotik jika \((P_t)\) memiliki distribusi stasioner tunggal \(\psi^*\) dalam \(\dD\) dan

\[ \|\psi P_t-\psi^*\|\to0 \text{ ketika }t\to\infty \text{ bagi setiap }\psi\in\dD. \]

Tujuan kita adalah menetapkan syarat-syarat kestabilan asimtotik semigrup Markov.

Kontraktivitas

Mari kita ingat beberapa fakta berguna dari kasus waktu diskret.

Pertama, jika \(P\) sembarang matriks Markov, maka dalam norma \(\ell_1\),

\[ \|fP\|\leq\|f\| \text{ bagi setiap } f\in\ell_1. \]

Memang, bagi \(f\in\ell_1\),

\[ \|fP\| =\sum_y\left|\sum_x f(x)P(x,y)\right| \leq\sum_y\sum_x|f(x)|P(x,y) =\|f\|. \]

Dengan menerapkan hasil ini kepada \(f=\psi-\phi\), untuk \(\psi,\phi\in\dD\) kita memperoleh

\[ \|\psi P-\phi P\|\leq\|\psi-\phi\|. \]

Jadi, setiap operator Markov bersifat mengontraksikan pada \(\dD\).

Catatan koreksi hilir. Sumber menyatakan dan membuktikan persamaan allmocontract hanya untuk \(\psi\in\dD\), lalu mengatakan bahwa hasil untuk selisih mengikuti dari linearitas. Bukti yang diperlukan sebenarnya berlaku untuk setiap \(f\in\ell_1\), sebagaimana dinyatakan di atas; barulah ia dapat diterapkan kepada selisih bertanda \(\psi-\phi\).

Lebih lanjut, jika \(P\) positif di setiap entri, ketaksamaan tersebut bersifat ketat.

Catatan pelengkapan hilir. Untuk melihat ketatnya ketaksamaan, tulis \(h:=\psi-\phi=h^+-h^-\) dan \(a:=\|h\|/2>0\). Karena jumlah koordinat \(h\) nol, \(h^+/a\) dan \(h^-/a\) adalah dua distribusi. Kepositifan semua entri \(P\) membuat kedua citra distribusi itu bernilai positif pada setiap koordinat, sehingga keduanya memiliki tumpang tindih positif. Oleh karena itu, variasi total—dan dengan demikian norma \(\ell_1\) dari selisih—berkurang secara ketat setelah dikalikan dengan \(P\).

Lihat, misalnya, Proposisi 3.1.2 dalam Andrzej Lasota dan Michael C. Mackey, Chaos, Fractals, and Noise: Stochastic Aspects of Dynamics (Springer, 1994), Proposition 3.1.2 atau Lema 8.2.3 dalam John Stachurski, Economic Dynamics: Theory and Computation (MIT Press, 2009), Lemma 8.2.3.

Ketunggalan

Ketaktereduksian rantai Markov memastikan tidak adanya himpunan penyerap yang saling lepas.

Hal ini pada gilirannya menghasilkan ketunggalan distribusi stasioner.

Kestabilan melalui Rantai Kerangka

Ingat definisi kestabilan asimtotik dalam persamaan asyms.

Secara analog, kita menyebut sebuah operator Markov \(P\) stabil asimtotik jika \(P\) memiliki distribusi stasioner tunggal \(\psi^*\) dalam \(\dD\) dan \(\psi P^n\to\psi^*\) ketika \(n\to\infty\) bagi setiap \(\psi\in\dD\).

Hasil berikut menghubungkan kestabilan waktu diskret dan waktu kontinu.

Bahan penting yang menghubungkan kedua konsep itu adalah kontraktivitas dalam persamaan allmocontract.

Kestabilan melalui Hanyutan

Pada bagian ini kita membahas syarat hanyutan, yaitu metode ampuh untuk memperoleh kestabilan asimtotik ketika ruang keadaan dapat tak berhingga.

Gagasannya adalah menunjukkan bahwa keadaan cenderung hanyut kembali menuju suatu himpunan berhingga.

Hanyutan semacam itu mencegah massa menyapu menuju tak berhingga, sedangkan ketaktereduksian menyediakan pencampuran dan ketunggalan yang berhubungan dengan mekanisme dalam lema kontraktivitas ketat. Teorema yang dirujuk di bawah menggabungkan unsur-unsur tersebut untuk menghasilkan kestabilan global.

Teorema berikut memberikan salah satu versi yang berguna.

Pembuktian teorema kestabilan hanyutan dapat ditemukan dalam Katarzyna Pichór, Ryszard Rudnicki, dan Marta Tyran-Kamińska, Stochastic Semigroups and Their Applications to Biological Models, Demonstratio Mathematica 45(2), 463–494 (2012).

Catatan ruang lingkup hilir. Sumber menyisipkan kata and ke dalam cabang pertama tampilan potongan dan tidak menyatakan syarat keterdefinisian \(Qv\) ketika \(v\) tak terbatas. Tampilan di atas memperbaiki tata letaknya dan menyatakan domain yang diperlukan. Teorema tetap digunakan hanya dalam ruang lingkup hasil yang dirujuk, bukan sebagai klaim bahwa sembarang matriks formal \(Q\) dapat diterapkan pada sembarang \(v\) tak terbatas.

Latihan berjawaban di bawah meminta Anda memastikan akibat ini.

Latihan