Waktu Henti

Teori Dasar

Seperti dalam pendahuluan, kita mulai dengan suatu proses stokastik \( \bs{X} = \{X_t: t \in T\} \) pada ruang probabilitas yang mendasarinya \( (\Omega, \mathscr{F}, \P) \), dengan ruang keadaan \( \R \), dan dengan himpunan indeks \( T \) (yang menyatakan waktu) berupa \( \N \) (waktu diskret) atau \( [0, \infty) \) (waktu kontinu). Selanjutnya, kita memiliki suatu filtrasi \(\mathfrak{F} = \{\mathscr{F}_t: t \in T\} \), dan kita mengandaikan bahwa \( \bs{X} \) teradaptasi terhadap \( \mathfrak{F} \). Jadi, \( \mathfrak{F} \) merupakan keluarga menaik subaljabar-\( \sigma \) dari \( \mathscr{F} \), dan \( X_t \) terukur terhadap \( \mathscr{F}_t \) untuk \( t \in T \). Kita memandang \( \mathscr{F}_t \) sebagai koleksi kejadian hingga waktu \( t \in T \). Kita mengandaikan bahwa \( \E\left(\left|X_t\right|\right) \lt \infty \), sehingga rata-rata \( X_t \) ada sebagai bilangan riil untuk setiap \( t \in T \). Terakhir, dalam waktu kontinu ketika \( T = [0, \infty) \), kita menggunakan asumsi standar bahwa \( \bs X \) kontinu kanan dan memiliki limit kiri, serta bahwa filtrasi \( \mathfrak F \) kontinu kanan dan lengkap.

Tujuan umum kita dalam bagian ini adalah menentukan apakah beberapa sifat penting martingal tetap berlaku ketika waktu deterministik \( t \in T \) diganti dengan suatu waktu henti (acak). Ingat bahwa waktu acak \( \tau \) yang bernilai dalam \( T \cup \{\infty\} \) merupakan waktu henti terhadap \( \mathfrak F \) jika \( \{\tau \le t\} \in \mathscr{F}_t \) untuk \( t \in T \). Jadi, waktu henti adalah waktu acak yang tidak mengharuskan kita melihat ke masa depan. Artinya, kita dapat menentukan apakah \( \tau \le t \) dari informasi yang tersedia pada waktu \( t \). Ingat pula bahwa aljabar-\( \sigma \) yang terkait dengan waktu henti \( \tau \) adalah \[ \mathscr{F}_\tau = \left\{A \in \mathscr{F}: A \cap \{\tau \le t\} \in \mathscr{F}_t \text{ untuk setiap } t \in T\right\} \] Jadi, \( \mathscr{F}_\tau \) merupakan koleksi kejadian hingga waktu acak \( \tau \), sebagaimana \( \mathscr{F}_t \) merupakan koleksi kejadian hingga waktu deterministik \( t \in T \). Dalam gambaran seorang penjudi yang memainkan serangkaian permainan, waktu ketika penjudi memutuskan untuk berhenti bermain harus berupa waktu henti; bahkan, penafsiran inilah asal nama tersebut. Artinya, waktu ketika penjudi memutuskan berhenti hanya boleh bergantung pada informasi yang dimilikinya hingga saat itu.

Penghentian Opsional

Persamaan dasar martingal \( \E(X_t \mid \mathscr{F}_s) = X_s \) untuk \( s, \, t \in T \) dengan \( s \le t \) dapat diperumum dengan mengganti \( s \) dan \( t \) dengan waktu henti terbatas. Hasil ini dikenal sebagai teorema penghentian opsional Doob dan kembali dinamai menurut Joseph Doob. Misalkan \( \bs X = \{X_t: t \in T\} \) memenuhi asumsi dasar di atas terhadap filtrasi \( \mathfrak F = \{\mathscr{F}_t: t \in T\} \).

Misalkan \( \rho \) dan \( \tau \) merupakan waktu henti terbatas terhadap \( \mathfrak F \) dengan \( \rho \le \tau \).

Jika \( \bs X \) merupakan martingal terhadap \( \mathfrak F \), maka \( \E(X_\tau \mid \mathscr{F}_\rho) = X_\rho \).
Jika \( \bs X \) merupakan submartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau \mid \mathscr{F}_\rho) \ge X_\rho \).
Jika \( \bs X \) merupakan supermartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau \mid \mathscr{F}_\rho) \le X_\rho \).

Rincian:

Bukti dalam waktu diskret:

Misalkan \( \tau \le k \), dengan \( k \in \N_+ \), dan ambil \( A \in \mathscr{F}_\tau \). Untuk \( j \in \N \) dengan \( j \le k \), berlaku \( A \cap \{\tau = j\} \in \mathscr{F}_j \). Oleh karena sifat martingal, \[ \E(X_k ; A \cap \{\tau = j\}) = \E(X_j ; A \cap \{\tau = j\}) = \E(X_\tau ; A \cap \{\tau = j\})\] Karena \( k \) merupakan batas atas bagi \( \tau \), kejadian \( A \cap \{\tau = j\} \) untuk \( j = 0, 1, \ldots, k \) membentuk partisi \( A \). Dengan menjumlahkan persamaan yang ditampilkan terhadap \( j \), diperoleh \( \E(X_k ; A) = \E(X_\tau ; A) \). Menurut definisi nilai harapan bersyarat, \( \E(X_k \mid \mathscr{F}_\tau) = X_\tau \). Karena \( k \) juga merupakan batas atas bagi \( \rho \), kita juga memiliki \( \E(X_k \mid \mathscr{F}_\rho) = X_\rho \). Terakhir, dengan menggunakan sifat menara, kita memperoleh \[ X_\rho = \E(X_k \mid \mathscr{F}_\rho) = \E[\E(X_k \mid \mathscr{F}_\rho) \mid \mathscr{F}_\tau] = \E[\E(X_k \mid \mathscr{F}_\tau) \mid \mathscr{F}_\rho] = \E(X_\tau \mid \mathscr{F}_\rho)\]
Jika \( \bs X \) merupakan submartingal, maka menurut teorema dekomposisi Doob, \( X_n = Y_n + Z_n \) untuk \( n \in \N \), dengan \( \bs Y = \{Y_n: n \in \N\} \) merupakan martingal terhadap \( \mathfrak F \), sedangkan \( \bs Z = \{Z_n: n \in \N\} \) menaik dan terprediksi terhadap \( \mathfrak F \). Jadi, \[ \E(X_\tau \mid \mathscr{F}_\rho) = \E(Y_\tau \mid \mathscr{F}_\rho) + \E(Z_\tau \mid \mathscr{F}_\rho)\] Namun, \( \E(Y_\tau \mid \mathscr{F}_\rho) = Y_\rho \) menurut bagian (a), dan karena \( \bs Z \) menaik, \( \E(Z_\tau \mid \mathscr{F}_\rho) \ge \E(Z_\rho \mid \mathscr{F}_\rho) = Z_\rho \). Oleh karena itu, \( \E(X_\tau \mid \mathscr{F}_\rho) \ge X_\rho \).
Bukti ketika \( \bs X \) merupakan supermartingal sama seperti bagian (b), kecuali bahwa proses \( \bs Z \) menurun.

Bukti dalam waktu kontinu: Misalkan \( \bs X \) merupakan martingal. Kita perlu menunjukkan bahwa \( \E(X_\tau; A) = \E(X_\rho; A) \) untuk setiap \( A \in \mathscr{F}_\rho \). Tetapkan \( \rho_n = \lceil 2^n \rho \rceil / 2^n \) dan \( \tau_n = \lceil 2^n \tau \rceil / 2^n \) untuk \( n \in \N \). Waktu henti \( \rho_n \) dan \( \tau_n \) bernilai dalam himpunan terhitung \( T_n \) untuk setiap \( n \in \N \), serta \( \rho_n \downarrow \rho \) dan \( \tau_n \downarrow \tau \) ketika \( n \to \infty \). Proses \( \{X_t: t \in T_n\} \) merupakan martingal waktu diskret untuk setiap \( n \in \N \). Berdasarkan kekontinuan kanan \( \bs X \), \[ X_{\rho_n} \to X_\rho, \; X_{\tau_n} \to X_\tau \text{ saat } n \to \infty \] Selanjutnya, misalkan \( \tau \le c \), dengan \( c \in (0, \infty) \), sehingga \( \rho \le c \) juga. Maka \( \rho_n \le c + 1 \) dan \( \tau_n \le c + 1 \) untuk \( n \in \N \), sehingga waktu henti diskret tersebut terbatas seragam. Berdasarkan versi diskret teorema, \( X_{\rho_n} = \E\left(X_{c+1} \mid \mathscr{F}_{\rho_n}\right) \) dan \( X_{\tau_n} = \E\left(X_{c+1} \mid \mathscr{F}_{\tau_n}\right) \) untuk \( n \in \N \). Dengan demikian, barisan \( \left\{X_{\rho_n}: n \in \N\right\} \) dan \( \left\{X_{\tau_n}: n \in \N\right\} \) terintegralkan seragam; oleh karena itu, \( X_{\rho_n} \to X_\rho \) dan \( X_{\tau_n} \to X_\tau \) ketika \( n \to \infty \), baik dalam rata-rata maupun dengan probabilitas 1. Sekarang ambil \( A \in \mathscr{F}_\rho \). Karena \( \rho \le \rho_n \), berlaku \( \mathscr{F}_\rho \subseteq \mathscr{F}_{\rho_n} \), sehingga \( A \in \mathscr{F}_{\rho_n} \) untuk setiap \( n \in \N \). Berdasarkan teorema dalam waktu diskret, \[ \E\left(X_{\tau_n}; A\right) = \E\left(X_{\rho_n}; A\right), \quad n \in \N \] Dengan membiarkan \( n \to \infty \), diperoleh \( \E(X_\tau; A) = \E(X_\rho; A) \). Bukti bagian (b) dan (c) sama seperti dalam waktu diskret.

Asumsi bahwa waktu henti terbatas sangat penting. Suatu contoh tandingan ketika asumsi ini tidak berlaku diberikan dalam . Berikut dua akibat sederhana:

Misalkan kembali bahwa \( \rho \) dan \( \tau \) merupakan waktu henti terbatas terhadap \( \mathfrak F \) dengan \( \rho \le \tau \).

Jika \( \bs X \) merupakan martingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) = \E(X_\rho) \).
Jika \( \bs X \) merupakan submartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) \ge \E(X_\rho) \).
Jika \( \bs X \) merupakan supermartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) \le \E(X_\rho) \).

Rincian:

Ingat bahwa \( \E(X_\tau) = \E[\E(X_\tau \mid \mathscr{F}_\rho)] \), sehingga hasil-hasil tersebut langsung mengikuti teorema penghentian opsional .

Misalkan \( \tau \) merupakan waktu henti terbatas terhadap \( \mathfrak F \).

Jika \( \bs X \) merupakan martingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) = \E(X_0) \).
Jika \( \bs X \) merupakan submartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) \ge \E(X_0) \).
Jika \( \bs X \) merupakan supermartingal terhadap \( \mathfrak F \), maka \( \E(X_\tau) \le \E(X_0) \).

Martingal yang Dihentikan

Untuk pembahasan berikutnya, kita perlu terlebih dahulu mengingat kembali cara menghentikan suatu proses stokastik pada waktu henti.

Misalkan \( \bs X \) memenuhi asumsi di atas dan \( \tau \) merupakan waktu henti terhadap filtrasi \( \mathfrak F \). Proses yang dihentikan \( \bs X^\tau = \{X^\tau_t: t \in T\} \) didefinisikan oleh \[ X^\tau_t = X_{t \wedge \tau}, \quad t \in T \]

Rincian:

Dalam waktu kontinu, asumsi standar kita memastikan bahwa \( \bs{X}^\tau \) merupakan proses stokastik yang sah dan teradaptasi terhadap \( \mathfrak F \). Artinya, \( X^\tau_t \) terukur terhadap \( \mathscr{F}_t \) untuk setiap \( t \in [0, \infty) \). Selain itu, \( \bs{X}^\tau \) juga kontinu kanan dan memiliki limit kiri.

Jadi, \( X^\tau_t = X_t \) jika \( t \lt \tau \), dan \( X^\tau_t = X_\tau \) jika \( t \ge \tau \). Secara khusus, perhatikan bahwa \( X^\tau_0 = X_0 \). Jika \( X_t \) adalah kekayaan seorang penjudi pada waktu \( t \in T \), maka \( X^\tau_t \) adalah kekayaan yang disesuaikan pada waktu \( t \) ketika \( \tau \) menjadi waktu henti penjudi tersebut. Hasil berikutnya, yang dikenal sebagai teorema penghentian elementer, menyatakan bahwa martingal yang dihentikan pada suatu waktu henti tetap merupakan martingal.

Misalkan kembali bahwa \( \bs X \) memenuhi asumsi di atas dan \( \tau \) merupakan waktu henti terhadap \( \mathfrak F \).

Jika \( \bs X \) merupakan martingal terhadap \( \mathfrak F \), maka demikian pula \( \bs{X}^\tau \).
Jika \( \bs X \) merupakan submartingal terhadap \( \mathfrak F \), maka demikian pula \( \bs{X}^\tau \).
Jika \( \bs X \) merupakan supermartingal terhadap \( \mathfrak F \), maka demikian pula \( \bs{X}^\tau \).

Rincian:

Bukti umum: Jika \( s, \, t \in T \) dengan \( s \le t \), maka \( \tau \wedge s \) dan \( \tau \wedge t \) merupakan waktu henti terbatas dengan \( \tau \wedge s \le \tau \wedge t \). Jadi, hasil tersebut langsung mengikuti teorema penghentian opsional .

Bukti khusus dalam waktu diskret: Dalam waktu diskret, terdapat bukti langsung yang sederhana dengan menggunakan transformasi martingal. Jadi, misalkan \( T = \N \) dan definisikan proses \( \bs Y = \{Y_n: n \in \N_+\} \) oleh \[ Y_n = \bs{1}(\tau \ge n) = 1 - \bs{1}(\tau \le n - 1), \quad n \in \N_+ \] Menurut definisi waktu henti, \( \{\tau \le n - 1\} \in \mathscr{F}_{n-1} \) untuk \( n \in \N_+ \), sehingga proses \( \bs Y \) terprediksi. Tentu saja, \( \bs Y \) juga merupakan proses terbatas dan nonnegatif. Transformasi \( \bs X \) oleh \( \bs Y \) adalah \[ (\bs Y \cdot \bs X)_n = X_0 + \sum_{k=1}^n Y_k (X_k - X_{k-1}) = X_0 + \sum_{k=1}^n \bs{1}(\tau \ge k)(X_k - X_{k-1}), \quad n \in \N_+ \] Namun, perhatikan bahwa \( X^\tau_k - X^\tau_{k-1} = X_k - X_{k-1} \) jika \( \tau \ge k \), dan \( X^\tau_k - X^\tau_{k-1} = X_\tau - X_\tau = 0 \) jika \( \tau \lt k \). Artinya, \( X^\tau_k - X^\tau_{k-1} = \bs{1}(\tau \ge k)(X_k - X_{k-1}) \). Oleh karena itu, \[ (\bs Y \cdot \bs X)_n = X_0 + \sum_{k=1}^n (X^\tau_k - X^\tau_{k-1}) = X_0 + X^\tau_n - X^\tau_0 = X^\tau_n, \quad n \in \N_+ \] Jika \( \bs X \) merupakan martingal (submartingal) (supermartingal), maka demikian pula transformasi \( \bs Y \cdot \bs X = \bs{X}^\tau\).

Teorema penghentian elementer membawa kabar buruk bagi penjudi yang memainkan serangkaian permainan. Jika permainannya adil atau merugikan, tidak ada waktu henti—secerdik apa pun rancangannya—yang dapat membantu penjudi. Karena martingal yang dihentikan tetap merupakan martingal, sifat rata-ratanya tetap berlaku.

Misalkan kembali bahwa \( \bs X \) memenuhi asumsi di atas dan \( \tau \) merupakan waktu henti terhadap \( \mathfrak F \). Ambil \( t \in T \).

Jika \( \bs X \) merupakan martingal terhadap \( \mathfrak F \), maka \( \E(X_{t \wedge \tau}) = \E(X_0) \)
Jika \( \bs X \) merupakan submartingal terhadap \( \mathfrak F \), maka \( \E(X_{t \wedge \tau}) \ge \E(X_0) \)
Jika \( \bs X \) merupakan supermartingal terhadap \( \mathfrak F \), maka \( \E(X_{t \wedge \tau}) \le \E(X_0) \)

Penghentian Opsional dalam Waktu Diskret

Akibat sederhana dari teorema penghentian opsional adalah bahwa jika \( \bs X \) merupakan martingal dan \( \tau \) waktu henti terbatas, maka \( \E(X_\tau) = \E(X_0) \) (dengan pertidaksamaan yang sesuai jika \( \bs X \) merupakan submartingal atau supermartingal). Pembahasan berikutnya berpusat pada syarat lain yang memberikan hasil-hasil tersebut dalam waktu diskret. Misalkan \( \bs X = \{X_n: n \in \N\} \) memenuhi asumsi dasar di atas terhadap filtrasi \( \mathfrak F = \{\mathscr{F}_n: n \in \N\} \), dan \( \tau \) merupakan waktu henti terhadap \( \mathfrak F \).

Misalkan \( \left|X_n\right| \) terbatas seragam terhadap \( n \in \N \) dan \( \tau \) berhingga.

Jika \( \bs X \) merupakan martingal, maka \( \E(X_\tau) = \E(X_0) \).
Jika \( \bs X \) merupakan submartingal, maka \( \E(X_\tau) \ge \E(X_0) \).
Jika \( \bs X \) merupakan supermartingal, maka \( \E(X_\tau) \le \E(X_0) \).

Rincian:

Andaikan bahwa \( \bs X \) merupakan supermartingal. Bukti untuk submartingal serupa, dan hasil untuk martingal kemudian langsung mengikuti. Alat utamanya adalah bagi supermartingal yang dihentikan: \[ \E(X_{\tau \wedge n}) \le \E(X_0), \quad n \in \N \] Karena \( \tau \lt \infty \) dengan probabilitas 1, berlaku \( \tau \wedge n \to \tau \) ketika \( n \to \infty \), juga dengan probabilitas 1. Karena \( |X_n| \) terbatas terhadap \( n \in T \), teorema kekonvergenan terbatas memberikan \( \E(X_{\tau \wedge n}) \to \E(X_\tau) \) ketika \( n \to \infty \). Dengan membiarkan \( n \to \infty \) dalam persamaan yang ditampilkan, diperoleh \( \E(X_\tau) \le \E(X_0) \).

Misalkan \( \left|X_{n+1} - X_n\right| \) terbatas seragam terhadap \( n \in \N \) dan \( \E(\tau) \lt \infty \).

Jika \( \bs X \) merupakan martingal, maka \( \E(X_\tau) = \E(X_0) \).
Jika \( \bs X \) merupakan submartingal, maka \( \E(X_\tau) \ge \E(X_0) \).
Jika \( \bs X \) merupakan supermartingal, maka \( \E(X_\tau) \le \E(X_0) \).

Rincian:

Andaikan bahwa \( \bs X \) merupakan supermartingal. Bukti untuk submartingal serupa, dan hasil untuk martingal kemudian langsung mengikuti. Alat utamanya sekali lagi adalah sifat rata-rata dalam di atas bagi supermartingal yang dihentikan: \[ \E(X_{\tau \wedge n}) \le \E(X_0), \quad n \in \N \] Misalkan \( |X_{n+1} - X_n| \le c \), dengan \( c \in (0, \infty) \). Maka \[ |X_{\tau \wedge n} - X_0| = \left|\sum_{k=1}^{\tau \wedge n} (X_k - X_{k-1})\right| \le \sum_{k=1}^{\tau \wedge n} |X_k - X_{k-1}| \le c (\tau \wedge n) \le c \tau \] Oleh karena itu, \( |X_{\tau \wedge n}| \le c \tau + |X_0| \). Karena \( \E(\tau) \lt \infty \), kita mengetahui bahwa \( \tau \lt \infty \) dengan probabilitas 1, sehingga seperti sebelumnya, \( \tau \wedge n \to \tau \) ketika \( n \to \infty \). Selain itu, \(\E(c \tau + |X_0|) \lt \infty\), sehingga menurut teorema kekonvergenan terdominasi, \( \E(X_{\tau \wedge n}) \to \E(X_\tau) \) ketika \( n \to \infty \). Jadi, dengan kembali membiarkan \( n \to \infty \) dalam persamaan yang ditampilkan, diperoleh \( \E(X_\tau) \le \E(X_0) \).

Mari kembali ke penafsiran awal kita tentang martingal \( \bs{X} \) sebagai kekayaan seorang penjudi yang memainkan permainan adil. Penjudi dapat memilih berhenti pada waktu acak \( \tau \), tetapi \( \tau \) harus berupa waktu henti berdasarkan informasi penjudi yang dikodekan dalam filtrasi \( \mathfrak{F} \). Di bawah syarat teorema, tidak ada strategi semacam itu yang dapat membantu penjudi dalam hal nilai harapan.

Contoh dan Penerapan

Gerak Acak Sederhana

Misalkan \( \bs{V} = (V_1, V_2, \ldots) \) merupakan barisan peubah acak independen dan berdistribusi identik dengan \( \P(V_i = 1) = p \) serta \( \P(V_i = -1) = 1 - p \) untuk \( i \in \N_+ \), dengan \( p \in (0, 1) \). Misalkan \( \bs{X} = (X_0, X_1, X_2, \ldots)\) merupakan proses jumlah parsial yang terkait dengan \( \bs{V} \), sehingga \[ X_n = \sum_{i=1}^n V_i, \quad n \in \N \] Maka \( \bs{X} \) merupakan gerak acak sederhana dengan parameter \( p \). Dalam konteks perjudian, penjudi kita memainkan serangkaian permainan independen dan identik; pada setiap permainan, ia memenangkan €1 dengan probabilitas \( p \) dan kehilangan €1 dengan probabilitas \( 1 - p \). Jadi, \( X_n \) adalah total kemenangan bersih penjudi setelah \( n \) permainan. Dalam pendahuluan, kita menunjukkan bahwa \( \bs X \) merupakan martingal jika \( p = \frac{1}{2} \) (kasus adil), submartingal jika \( p \gt \frac{1}{2} \) (kasus menguntungkan), dan supermartingal jika \( p \lt \frac{1}{2} \) (kasus merugikan). Sekarang, untuk \( c \in \Z \), tetapkan \[ \tau_c = \inf\{n \in \N: X_n = c\} \] dengan, seperti biasa, \( \inf(\emptyset) = \infty \). Jadi, \( \tau_c \) adalah waktu pertama ketika kekayaan penjudi mencapai \( c \). Bagaimana jika penjudi terus bermain hingga kemenangan bersihnya mencapai suatu bilangan positif yang telah ditentukan (misalnya €\(1\,000\,000 \))? Apakah strategi tersebut dapat dijalankan?

Misalkan \( p = \frac{1}{2} \) dan \( c \in \N_+ \).

\( \P(\tau_c \lt \infty) = 1 \)
\( \E\left(X_{\tau_c}\right) = c \ne 0 = \E(X_0) \)
\( \E(\tau_c) = \infty \)

Rincian:

Bagian (a) dan (c) berlaku karena \( \bs X \) merupakan rantai Markov rekuren nol. Bagian (b) mengikuti dari (a) karena jelas bahwa \( X_{\tau_c} = c \) jika \( \tau_c \lt \infty \).

Perhatikan bahwa bagian (b) tidak bertentangan dengan teorema penghentian opsional karena bagian (c). Strategi menunggu hingga kemenangan bersih mencapai sasaran tertentu \( c \) tidak dapat dipertahankan. Sekarang, misalkan penjudi bermain hingga kemenangan bersihnya turun ke suatu bilangan negatif yang telah ditentukan (kerugian yang masih dapat ditoleransi) atau mencapai suatu bilangan positif yang telah ditentukan (sasaran yang ingin dicapai).

Misalkan kembali bahwa \( p = \frac{1}{2} \). Untuk \( a, \, b \in \N_+ \), tetapkan \( \tau = \tau_{-a} \wedge \tau_b \). Maka

\( \E(\tau) \lt \infty \)
\( \E(X_\tau) = 0 \)
\( \P(\tau_{-a} \lt \tau_b) = b / (a + b) \)

Rincian:

Kita membiarkan \( X_0 \) memiliki nilai sebarang dalam himpunan \( \{-a, -a + 1, \ldots, b - 1, b\} \), sehingga kita dapat menggunakan teknik rantai Markov. Tetapkan \( m(x) = \E(\tau \mid X_0 = x) \) untuk \( x \) dalam himpunan ini. Dengan mengondisikan pada keadaan pertama dan menggunakan sifat Markov, kita memperoleh \[ m(x) = 1 + \frac{1}{2} m(x - 1) + \frac{1}{2} m(x + 1), \quad x \in \{-a + 1, \ldots, b - 1\} \] dengan syarat batas \( m(-a) = m(b) = 0 \). Relasi rekurensi linear ini dapat diselesaikan secara eksplisit, tetapi yang kita perlukan hanyalah fakta bahwa solusinya berhingga.
Teorema penghentian opsional waktu diskret berlaku, sehingga \( \E(X_\tau) = \E(X_0) = 0 \).
Tetapkan \( q = \P(\tau_{-a} \lt \tau_b) \), sehingga \( 1 - q = \P(\tau_b \lt \tau_{-a}) \). Menurut definisi, \( X_\tau = -a \) jika \( \tau_{-a} \lt \tau_b \), dan \( X_\tau = b \) jika \( \tau_b \lt \tau_{-a} \). Jadi, dari bagian (b), \( q(-a) + (1 - q) b = 0 \), dan dengan demikian \( q = b / (a + b) \).

Jadi, berjudi hingga kemenangan bersih turun ke \( -a \) atau mencapai \( b \) merupakan strategi yang dapat dijalankan, tetapi sayangnya memiliki nilai harapan 0. Berikut contoh lain yang menunjukkan bahwa versi pertama teorema penghentian opsional dapat gagal jika waktu hentinya tidak terbatas.

Misalkan kembali bahwa \( p = \frac{1}{2} \). Ambil \( a, \, b \in \N_+ \) dengan \( a \lt b \). Maka \( \tau_a \lt \tau_b \lt \infty \), tetapi \[ b = \E\left(X_{\tau_b} \mid \mathscr{F}_{\tau_a} \right) \ne X_{\tau_a} = a \]

Rincian:

Karena \( X_0 = 0 \), proses \( \bs X \) harus mencapai \( a \) sebelum mencapai \( b \). Seperti sebelumnya, \( \tau_b \lt \infty \), tetapi \( \E(\tau_b) = \infty \) karena \( \bs X \) merupakan rantai Markov rekuren nol.

Hasil ini tidak bertentangan dengan teorema penghentian opsional karena waktu hentinya tidak terbatas.

Persamaan Wald

Persamaan Wald, yang dinamai menurut Abraham Wald, merupakan rumus bagi nilai harapan suatu jumlah dengan banyak suku acak, yang suku-sukunya berupa peubah acak independen dan berdistribusi identik. Kita telah menelaahnya sebelumnya dalam pembahasan tentang nilai harapan bersyarat dan sampel acak, tetapi teori martingal menghasilkan bukti yang sangat sederhana dan elegan.

Misalkan \( \bs X = (X_n: n \in \N_+) \) merupakan barisan peubah independen dan berdistribusi identik dengan \( \E(|X_1|) \lt \infty \) dan \( \E(X_1) = \mu \in \R \). Jika \( N \) merupakan waktu henti bagi \( \bs X \) dengan \( \E(N) \lt \infty \), maka \[ \E\left(\sum_{k=1}^N X_k\right) = \E(N) \mu \]

Rincian:

Misalkan \( \mathfrak F \) merupakan filtrasi alami \( \bs X \), lalu tetapkan \( Y_0=0 \) dan \[ Y_n = \sum_{k=1}^n (X_k - \mu), \quad n \in \N_+. \] Maka \( \bs Y=\{Y_n:n\in\N\} \) merupakan martingal. Untuk setiap \(n\), waktu henti \(N\wedge n\) terbatas, sehingga memberikan \(\E(Y_{N\wedge n})=0\). Untuk \(k\ge1\), kejadian \(\{N\ge k\}=\{N\gt k-1\}\) berada dalam \(\mathscr F_{k-1}\) dan karena itu independen dari \(X_k\). Maka \[ \begin{aligned} \E\left(|Y_N-Y_{N\wedge n}|\right) &\le \sum_{k=n+1}^{\infty}\E\left[|X_k-\mu|\bs{1}(N\ge k)\right] \\ &= \E(|X_1-\mu|)\sum_{k=n+1}^{\infty}\P(N\ge k) \\ &\longrightarrow 0. \end{aligned} \] karena \(\E(N)=\sum_{k=1}^{\infty}\P(N\ge k)\lt\infty\). Jadi \(Y_{N\wedge n}\to Y_N\) dalam \(L^1\) dan \(\E(Y_N)=0\). Dengan demikian, \[ \begin{aligned} 0 &= \E(Y_N) \\ &= \E\left[\sum_{k=1}^N (X_k - \mu)\right] \\ &= \E\left(\sum_{k=1}^N X_k\right) - \mu\E(N). \end{aligned} \]

Pola dalam Percobaan Multinomial

Pola dalam percobaan multinomial telah dipelajari dalam Bab 14 tentang proses pembaruan. Seperti yang sering terjadi, martingal memberikan penyelesaian yang lebih elegan. Misalkan \( \bs{L} = (L_1, L_2, \ldots) \) merupakan barisan peubah acak independen dan berdistribusi identik yang bernilai dalam himpunan berhingga \( S \), sehingga \( \bs{L} \) merupakan barisan percobaan multinomial. Misalkan \( f \) menyatakan fungsi kepadatan probabilitas bersama, sehingga untuk peubah percobaan generik \( L \), berlaku \( f(a) = \P(L = a) \) untuk \( a \in S \). Kita mengandaikan bahwa semua hasil dalam \( S \) benar-benar mungkin, sehingga \( f(a) \gt 0 \) untuk \( a \in S \).

Dalam pembahasan ini, kita menafsirkan \( S \) sebagai suatu alfabet, dan menulis barisan peubah dalam bentuk perangkaian, \(\bs{L} = L_1 L_2 \cdots\), alih-alih bentuk barisan standar. Dengan demikian, barisan tersebut merupakan untaian tak berhingga huruf-huruf dari alfabet \( S \). Kita tertarik pada kemunculan pertama suatu subuntaian huruf berhingga tertentu (yakni sebuah kata atau pola) dalam barisan tak berhingga tersebut. Definisi berikut akan menyederhanakan notasi.

Jika \( \bs a = a_1 a_2 \cdots a_k \) merupakan kata sepanjang \( k \in \N_+ \) dari alfabet \( S \), definisikan \[ f(\bs{a}) = \prod_{i=1}^k f(a_i) \] sehingga \( f(\bs a) \) merupakan probabilitas bahwa \( k \) percobaan berurutan menghasilkan kata \( \bs a \).

Jadi, tetapkan sebuah kata \( \bs a = a_1 a_2 \cdots a_k \) sepanjang \( k \in \N_+ \) dari alfabet \( S \), dan tinjau banyaknya percobaan \( N_{\bs a} \) hingga \( \bs a \) selesai terbentuk. Tujuan kita adalah menghitung \( \nu(\bs a) = \E\left(N_{\bs a}\right) \). Kita melakukannya dengan menyatakan masalah ini melalui serangkaian penjudi yang memainkan permainan adil, lalu menggunakan teorema penghentian opsional di atas. Misalkan seorang penjudi mempertaruhkan \( c \in (0, \infty) \) pada huruf \( a \in S \) dalam suatu percobaan. Penjudi memperoleh \( c / f(a) \) jika \( a \) muncul pada percobaan tersebut, dan memperoleh 0 jika tidak. Nilai harapan taruhan ini adalah \[ f(a) \frac{c}{f(a)} - c = 0 \] sehingga taruhan tersebut adil. Sekarang, tinjau seorang penjudi dengan kekayaan awal 1. Ketika mulai bermain, ia mempertaruhkan 1 pada \( a_1 \). Jika menang, ia mempertaruhkan seluruh kekayaannya \( 1 / f(a_1) \) pada \( a_2 \) dalam percobaan berikutnya. Ia melanjutkan dengan cara ini: selama menang, ia mempertaruhkan seluruh kekayaannya pada huruf berikutnya dari kata tersebut dalam percobaan berikutnya, hingga ia kalah atau menyelesaikan kata \( \bs a \). Terakhir, kita meninjau serangkaian penjudi independen yang memainkan strategi ini, dengan penjudi \( i \) mulai pada percobaan \( i \) untuk setiap \( i \in \N_+ \).

Untuk kata berhingga \( \bs a \), misalkan \( W_{N_{\bs a}} \) menyatakan total kekayaan semua penjudi ketika permainan dihentikan pada \( N_{\bs a} \). Maka \( W_{N_{\bs a}} \) deterministik dan \( \nu(\bs a)=W_{N_{\bs a}} \).

Rincian:

Tuliskan \( N=N_{\bs a} \). Misalkan \( W_n \) menyatakan total kekayaan semua penjudi setelah percobaan \( n \), dengan \( W_0=0 \), dan definisikan \( X_n=W_n-n \). Pengurangan \(n\) mencatat satu unit modal baru yang ditanamkan pada setiap percobaan. Karena setiap taruhan adil, \( \bs X=\{X_n:n\in\N\} \) merupakan martingal dengan rata-rata 0. Misalkan \( M_{\bs a} \) merupakan indeks blok saling lepas pertama sepanjang \( k \) yang membentuk \( \bs a \). Maka \[ \E(N)\le k\E(M_{\bs a})=\frac{k}{f(\bs a)}\lt\infty. \] Pada setiap saat paling banyak \( k \) penjudi masih aktif dan kekayaan setiap penjudi aktif paling besar \(1/f(\bs a)\). Karena itu, misalnya, \[ |X_{n+1}-X_n|\le 1+\frac{2k}{f(\bs a)}, \] sehingga berlaku dan \( \E(X_N)=0 \). Karena \(X_N=W_N-N\), diperoleh \( \E(W_N)=\E(N)=\nu(\bs a)\). Pada waktu \(N\), penjudi yang masih memiliki kekayaan tepat bersesuaian dengan prefiks \( \bs a \) yang juga merupakan sufiksnya; akibatnya \(W_N\) deterministik. Jadi \(W_N=\nu(\bs a)\).

Untuk \( \bs a \) yang diberikan, kita dapat menghitung total kemenangan secara tepat. Menurut definisi, percobaan \( N - k + 1, \ldots, N \) membentuk kata \( \bs a \) untuk pertama kalinya. Oleh karena itu, untuk \( i \le N - k \), penjudi \( i \) kalah pada suatu saat. Juga menurut definisi, penjudi \( N - k + 1 \) memenangkan semua taruhannya, menyelesaikan kata \( \bs a \), dan dengan demikian memperoleh \( 1 / f(\bs a) \). Kerumitannya adalah bahwa penjudi \( N - k + 2, \ldots, N \) mungkin telah memenangkan semua taruhan mereka ketika permainan berakhir, atau mungkin belum. Latihan berikut menggambarkan hal ini.

Misalkan \( \bs{L} \) merupakan barisan percobaan Bernoulli (sehingga \( S = \{0, 1\} \)) dengan probabilitas keberhasilan \( p \in (0, 1) \). Untuk setiap untaian berikut, tentukan nilai harapan banyaknya percobaan yang diperlukan untuk menyelesaikan untaian tersebut.

Rincian:

Tetapkan \( q = 1 - p \).

Untuk kata 001, penjudi \( N - 2 \) memenangkan \( \frac{1}{q^2 p} \) dari ketiga taruhannya. Penjudi \( N - 1 \) memasang dua taruhan, memenangkan yang pertama tetapi kalah pada yang kedua. Penjudi \( N \) kalah pada taruhan pertamanya (dan satu-satunya). Oleh karena itu, \( \nu(001) = \frac{1}{q^2 p} \)
Untuk kata 010, penjudi \( N - 2 \) memenangkan \( \frac{1}{q^2 p} \) dari ketiga taruhannya seperti sebelumnya. Penjudi \( N - 1 \) kalah pada taruhan pertamanya. Penjudi \( N \) memenangkan \( 1 / q \) pada taruhan pertamanya (dan satu-satunya). Jadi, \( \nu(010) = \frac{1}{q^2 p} + \frac{1}{q} \)

Perbedaan antara kedua kata tersebut adalah bahwa kata dalam bagian (b) memiliki suatu prefiks (untaian sejati pada awal kata) yang juga merupakan sufiks (untaian sejati pada akhir kata). Kata \( \bs a \) tidak memiliki prefiks semacam itu. Dengan demikian, kita secara alami sampai pada dikotomi berikut:

Misalkan \( \bs a \) merupakan kata berhingga dari alfabet \( S \). Jika tidak ada prefiks sejati \( \bs a \) yang juga merupakan sufiks, maka \( \bs a \) disebut sederhana. Jika tidak, \( \bs a \) disebut majemuk.

Berikut hasil utamanya, yang tentu sama dengan hasil ketika masalah ini diselesaikan menggunakan teori pembaruan.

Misalkan \( \bs a \) merupakan kata berhingga dalam alfabet \( S \).

Jika \( \bs a \) sederhana, maka \( \nu(\bs a) = 1 / f(\bs a) \).
Jika \( \bs a \) majemuk, maka \( \nu(\bs a) = 1 / f(\bs a) + \nu(\bs b) \), dengan \( \bs b \) merupakan kata terpanjang yang sekaligus menjadi prefiks dan sufiks \( \bs a \).

Rincian:

Semua unsur yang diperlukan telah tersedia dari pembahasan sebelumnya. Misalkan \( \bs a \) memiliki panjang \( k \in \N_+ \).

Jika \( \bs a \) sederhana, hanya pemain \( N - k + 1 \) yang menang, dan ia memenangkan \( 1 / f(\bs a) \).
Misalkan \( \bs a \) majemuk dan \( \bs b \) merupakan prefiks-sufiks sejati terpanjang. Seperti biasa, pemain \( N - k + 1 \) memenangkan \( 1 / f(\bs a) \). Kemenangan pemain \( N - k + 2, \ldots, N \) sama dengan kemenangan suatu barisan penjudi baru yang memainkan barisan percobaan baru dengan sasaran mencapai kata \( \bs b \).

Untuk kata majemuk, kita dapat menggunakan bagian (b) untuk mereduksi perhitungan menjadi kata-kata sederhana.

Tinjau percobaan Bernoulli dengan probabilitas keberhasilan \( p \in (0, 1) \). Tentukan nilai harapan banyaknya percobaan hingga setiap untaian berikut selesai terbentuk.

\( 1011011\)
\(1 1 \cdots 1 \) (sebanyak \( k \) kali)

Rincian:

Sekali lagi, tetapkan \( q = 1 - p \).

\( \nu(1011011) = \frac{1}{p^5 q^2} + \nu(1011) = \frac{1}{p^5 q^2} + \frac{1}{p^3 q} + \nu(1) = \frac{1}{p^5 q^2} + \frac{1}{p^3 q} + \frac{1}{p}\)
Misalkan \( \bs{1}_j \) menyatakan untaian yang terdiri atas \( j \) buah angka 1 untuk \( j \in \N_+ \). Jika \( k \ge 2 \), maka \( \nu(\bs{1}_k) = 1 / p^k + \nu(\bs{1}_{k-1}) \). Oleh karena itu, \[ \nu(\bs{1}_k) = \sum_{j=1}^k \frac{1}{p^j} \]

Ingat bahwa dadu pipih as-enam adalah dadu bersisi enam dengan sisi 1 dan 6 masing-masing berprobabilitas \(\frac{1}{4}\), sedangkan sisi 2, 3, 4, dan 5 masing-masing berprobabilitas \( \frac{1}{8} \). Dadu pipih as-enam terkadang digunakan penjudi untuk berbuat curang.

Misalkan sebuah dadu pipih as-enam dilempar berulang kali. Tentukan nilai harapan banyaknya lemparan hingga pola \( 6165616 \) muncul.

Rincian:

Berdasarkan teorema utama kita, \begin{align*} \nu(6165616) & = \frac{1}{f(6165616)} + \nu(616) = \frac{1}{f(6165616)} + \frac{1}{f(616)} + \nu(6) \\ & = \frac{1}{f(6165616)} + \frac{1}{f(616)} + \frac{1}{f(6)} = \frac{1}{(1/4)^6(1/8)} + \frac{1}{(1/4)^3} + \frac{1}{1/4} = 32\,836 \end{align*}

Misalkan seekor monyet mengetik secara acak pada papan ketik yang memiliki 26 tombol huruf kecil dan tombol spasi (jadi 27 tombol). Tentukan nilai harapan banyaknya penekanan tombol hingga monyet menghasilkan masing-masing frasa berikut:

it was the best of times
to be or not to be

Rincian:

\( 27^{24} \approx 2.258 \times 10^{34} \)
\( 27^5 + 27^{18} \approx 5.815 \times 10^{25} \)

Masalah Sekretaris

Masalah sekretaris telah dibahas dalam bab tentang model pencuplikan berhingga. Dalam pembahasan ini, kita akan menyelesaikan suatu variasi masalah tersebut menggunakan martingal. Misalkan terdapat \( n \in \N_+ \) kandidat untuk suatu pekerjaan, atau mungkin calon pasangan hidup. Para kandidat datang secara berurutan dalam urutan acak dan diwawancarai. Kita mengukur mutu setiap kandidat dengan suatu bilangan dalam interval \( [0, 1] \). Tujuan kita adalah memilih kandidat terbaik, tetapi setelah seorang kandidat ditolak, ia tidak dapat dipanggil kembali. Secara matematis, kita mengandaikan bahwa barisan peubah kandidat \( \bs X = (X_1, X_2, \ldots, X_n) \) independen dan masing-masing berdistribusi seragam pada interval \( [0, 1] \) (sehingga memiliki distribusi seragam standar). Tujuan kita adalah memilih waktu henti \( \tau \) terhadap \( \bs X \) yang memaksimumkan \( \E(X_\tau) \), yaitu nilai harapan kandidat yang dipilih. Barisan berikut akan berperan penting sebagai barisan ambang.

Definisikan barisan \( \bs a = (a_k: k \in \N) \) dengan \( a_0 = 0 \) dan \( a_{k+1} = \frac{1}{2}(1 + a_k^2) \) untuk \( k \in \N \). Maka

\( a_k \lt 1 \) untuk \( k \in \N \).
\( a_k \lt a_{k+1} \) untuk \( k \in \N \).
\( a_k \to 1 \) ketika \( k \to \infty \).
Jika \( X \) berdistribusi seragam pada \( [0, 1] \), maka \( \E(X \vee a_k) = a_{k+1} \) untuk \( k \in \N \).

Rincian:

Perhatikan bahwa \( a_1 = \frac{1}{2} \lt 1 \). Misalkan \( a_k \lt 1 \) untuk suatu \( k \in \N_+ \). Maka \(a_{k+1} = \frac{1}{2}(1 + a_k^2) \lt \frac{1}{2}(1 + 1) = 1 \)
Perhatikan bahwa \( 0 = a_0 \lt a_1 = \frac{1}{2} \). Misalkan \( a_k \gt a_{k-1} \) untuk suatu \( k \in \N_+ \). Maka \( a_{k+1} = \frac{1}{2}(1 + a_k^2) \gt \frac{1}{2}(1 + a_{k-1}^2) = a_k \).
Karena barisan tersebut menaik dan terbatas di atas, \( a_\infty = \lim_{k \to \infty} a_k \) ada. Dengan mengambil limit dalam relasi rekurensi, diperoleh \( a_\infty = \frac{1}{2}(1 + a_\infty^2) \), atau secara ekuivalen \( (a_\infty - 1)^2 = 0 \).
Untuk \( k \in \N \), \[ \E(X \vee a_k) = \int_0^1 (x \vee a_k) dx = \int_0^{a_k} a_k \, dx + \int_{a_k}^1 x \, dx = \frac{1}{2}(1 + a_k^2) = a_{k+1} \]

Karena \( a_0 = 0 \), berdasarkan bagian (a), semua suku barisan berada dalam \( [0, 1) \). Aproksimasi suku \(a_0\) sampai \(a_{10}\) adalah \[ (0, 0.5, 0.625, 0.695, 0.742, 0.775, 0.800, 0.820, 0.836, 0.850, 0.861, \ldots) \] Sifat (d) memberikan gambaran mengapa barisan tersebut penting bagi masalah sekretaris. Bagaimanapun, teorema berikut memberikan penyelesaiannya. Untuk menyederhanakan notasi, tetapkan \( \N_n = \{0, 1, \ldots, n\} \) dan \( \N_n^+ = \{1, 2, \ldots, n\} \).

Waktu henti \( \tau = \inf\left\{k \in \N_n^+: X_k \gt a_{n-k}\right\} \) optimal bagi masalah sekretaris dengan \( n \) kandidat. Nilai optimalnya adalah \( \E(X_\tau) = a_n \).

Rincian:

Misalkan \( \mathfrak F=\{\mathscr F_k:k\in\N_n\} \) merupakan filtrasi alami \( \bs X \), dengan \( \mathscr F_0=\{\emptyset,\Omega\} \) dan \( \mathscr F_k=\sigma(X_1,\ldots,X_k) \). Misalkan \( \rho \) merupakan waktu henti bernilai dalam \( \N_n^+ \). Definisikan \( \bs Y=\{Y_k:k\in\N_n\} \) dengan \( Y_0=a_n \) dan \( Y_k=X_{\rho\wedge k}\vee a_{n-k} \) untuk \( k\in\N_n^+ \). Kita akan menunjukkan bahwa \( \bs Y \) merupakan supermartingal terhadap \( \mathfrak F \). Pertama, pada kejadian \( \rho \le k - 1 \), \[ \E(Y_k \mid \mathscr{F}_{k-1}) = \E[(X_\rho \vee a_{n-k}) \mid \mathscr{F}_{k-1}] = X_\rho \vee a_{n-k} \le X_\rho \vee a_{n - k + 1} = Y_{k-1} \] dengan menggunakan fakta bahwa \( X_\rho \bs{1}(\rho \le k - 1) \) terukur terhadap \( \mathscr{F}_{k-1} \) dan bahwa barisan \( \bs a \) menaik. Pada kejadian \( \rho \gt k - 1 \), \[ \E(Y_k \mid \mathscr{F}_{k-1}) = \E(X_k \vee a_{n-k} \mid \mathscr{F}_{k-1}) = \E(X_k \vee a_{n-k}) = a_{n - k + 1} \le Y_{k - 1} \] dengan menggunakan fakta bahwa \( X_k \) dan \( \mathscr{F}_{k-1} \) independen, serta bagian (d) dari . Karena \( \bs Y \) merupakan supermartingal dan \( \rho \) terbatas, teorema penghentian opsional berlaku, dan kita memperoleh \[ \E(X_\rho) \le \E(X_\rho \vee a_{n - \rho}) = \E(Y_\rho) \le \E(Y_0) = a_n \] sehingga \( a_n \) merupakan batas atas bagi nilai harapan kandidat yang dipilih oleh waktu henti \( \rho \).

Selanjutnya, kita akan menunjukkan bahwa dalam kasus khusus \( \rho = \tau \), proses \( \bs Y \) merupakan martingal. Pada kejadian \( \tau \le k - 1 \), seperti sebelumnya kita memiliki \(\E(Y_k \mid \mathscr{F}_{k-1}) = X_\tau \vee a_{n-k}\). Namun, menurut definisi, \( X_\tau \ge a_{n - \tau} \ge a_{n - k + 1} \ge a_{n - k} \), sehingga pada kejadian ini, \[ \E(Y_k \mid \mathscr{F}_{k-1}) = X_\tau = X_\tau \vee a_{n - k + 1} = Y_{k-1} \] Pada kejadian \( \tau \gt k - 1 \), seperti sebelumnya kita memiliki \( \E(Y_k \mid \mathscr{F}_{k-1}) = a_{n-k+1}\). Namun, pada kejadian ini, \(Y_{k-1} = a_{n-k+1} \). Karena \( \bs Y \) merupakan martingal dan \( \tau \) terbatas, teorema penghentian opsional berlaku, dan kita memperoleh \[ \E(X_\tau) = \E(X_\tau \vee a_{n-\tau}) = \E(Y_\tau) = \E(Y_0) = a_n \]

Berikut sebuah contoh khusus:

Untuk \( n = 5 \), aturan keputusannya adalah sebagai berikut:

Pilih kandidat 1 jika \( X_1 \gt 0.742 \); jika tidak,
pilih kandidat 2 jika \( X_2 \gt 0.695 \); jika tidak,
pilih kandidat 3 jika \( X_3 \gt 0.625 \); jika tidak,
pilih kandidat 4 jika \( X_4 \gt 0.5 \); jika tidak,
pilih kandidat 5.

Nilai harapan kandidat yang kita pilih adalah 0.775.

Dalam versi awal masalah sekretaris, kita hanya dapat mengamati peringkat relatif para kandidat, dan tujuan kita adalah memaksimumkan probabilitas memilih kandidat terbaik. Untuk \( n = 5 \), strategi optimalnya adalah melewatkan dua kandidat pertama, lalu memilih kandidat pertama setelahnya yang lebih baik daripada semua kandidat sebelumnya, jika kandidat semacam itu ada. Jika tidak ada, tentu saja kita harus memilih kandidat 5. Probabilitas memilih kandidat terbaik adalah 0.433.