PERMAINAN DENGAN PENGHENTIAN OPTIMAL SUATU JALAN ACAK
Oleh : EVA RACHMANIA SAIDAH G54101049
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
RINGKASAN EVA RACHMANIA. Permainan dengan Penghentian Optimal Suatu Jalan Acak. Dibimbing oleh I G. PUTU PURNABA dan I WAYAN MANGKU. Diketahui sebuah permainan yang terdiri atas dua pemain, memiliki bentuk jalan acak simetrik. Pada permainan ini, proses jalan acak simetrik pemain I direpresentasikan oleh
x n dan pemain II oleh y n .
Peubah acak tersebut adalah proses jalan acak simetrik yang berada dalam himpunan state E = {0,1,..., K } . Diasumsikan peluang berpindah pada setiap state adalah sebesar p = 0.5 . Namun khusus pada state 0 dan K , selain memiliki peluang berpindah sebesar 0.5 menuju state 1 dan K − 1 atau sebaliknya, juga memiliki peluang untuk tidak berpindah (absorbed) sebesar 0.5. Permainan akan dimulai ketika pemain berada pada sembarang state awal, yaitu a dan b , dimana 1 ≤ a < b ≤ K − 1 . Setelah itu kedua pemain akan berhenti pada waktu Markov τ dan σ yang menjadi strategi penghentiannya. Setiap pemain hanya mengetahui nilai dari K, a dan b , tetapi tidak mengetahui tentang tindakan yang diambil oleh pemain lainnya. Adapun peraturan permainannya adalah sebagai berikut : jika xτ > yσ maka pemain II membayar pemain I sebesar $1 ; jika xτ < y σ maka pemain I yang membayar kepada pemain II sebesar $1 ; dan jika xτ = yσ pemainan adalah seri.
maka hasil dari
Keinginan dari setiap pemain adalah untuk dapat memaksimumkan nilai harapan imbalan permainan tersebut terhadap strategi penghentian yang dilakukan oleh pemain lainnya. Untuk itu, setiap pemain perlu menerapkan suatu strategi penghentian yang optimal dalam menghadapi strategi penghentian pemain lainnya. Kemudian dari strategi yang diterapkan oleh kedua pemain tersebut akan ditentukan keadaan keseimbangan dan nilai dari permainan tersebut.
PERMAINAN DENGAN PENGHENTIAN OPTIMAL SUATU JALAN ACAK
Skripsi
Sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains Pada Fakultas Matematika dan Ilmu Pengetahuan Alam
Oleh : EVA RACHMANIA SAIDAH G54101049
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2006
Judul : Permainan dengan Penghentian Optimal Suatu Jalan Acak Nama : Eva Rachmania Saidah Nrp : G54101049
Tangga l Lulus :.................................
RIWAYAT HIDUP
Penulis dilahirkan di Bogor pada tanggal 5 Mei 1983 yang merupakan anak ke-3 dari tiga bersaudara dari pasangan H.Dudung Murodz Ghani dan Siti Chotidjah. Pada tahun 1988 penulis memulai pendidikan formalnya di TK AL-IRSYAD Bogor dan dilanjutkan di SDN Polisi I Bogor (1989-1995). Kemudian penulis melanjutkan pendidikannya ke SLTP Negeri 2 Bogor (1995-1998) dan diteruskan ke SMU Negeri 1 Bogor (1998-2001). Penulis diterima di Institut Pertanian Bogor melalui jalur UMPTN pada program studi Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama kuliah penulis pernah aktif dalam kepengurusan DKM Al-Ghiffari dan beberapa kali masuk kedalam kepanitiaan di GUMATIKA maupun di BEM FMIPA.
PRAKATA Assalamualaikum Warahmatullahi Wabarakatuh. Puji syukur kehadirat Allah SWT penulis ucapkan atas limpahan nikmat yang tiada hentinya, serta atas rahmat dan ridho-Nya sehingga penulis dapat menyelesaikan skripsi ini. Pada kesempatan ini, penulis pun ingin mengucapkan terimakasih kepada pihak-pihak yang telah sangat membantu dalam penulisan skripsi ini, yaitu: 1. Kepada Bapak Putu Purnaba selaku pembimbing I dan Bapak I Wayan Mangku selaku pembimbing II, yang telah memb erikan nasehat, arahan, serta bimbingannya. 2. Untuk kedua orangtua yang sangat luar biasa, Papa dan Mama yang telah membesarkan penulis dengan seluruh cinta, doa, kesabaran dan semua nasehatnya untuk mengarungi kehidupan. 3. Untuk kedua kakak penulis , Nuniek dan Irfan yang menjadi teladan bagi penulis, serta seluruh keluarga besar atas dukungannya. 4. Untuk teman-teman Math’38 yang telah mewarnai hari-hari penulis dengan keceriaan dan kebersamaan, terutama Nanik, Nia, Feidy, Saidah, Endah, Seny dan Niken. Terima kasih pula pada Meriyaldi, Yana dan Andri atas kesediaannya menjadi pembahas, serta Linda yang selalu bersedia berdiskusi dengan penulis. 5. Untuk seluruh kakak angkatan 37, 36 dan 35 yang telah membagi pengalamannya baik dalam hal pelajaran kuliah maupun pengalaman hidup, khususnya teh Pipit’37. Serta adik angkatan 39 dan 40 atas kebersamaannya. 6. Untuk seluruh staf TU, Bu Ade, Mas Bono, Bu Marissi dan Mas Deni yang telah membantu dalam akademik penulis. Kepada Bu Susi atas dorongan dan nasehatnya dalam menempuh tugas akhir serta Mas Yono yang selalu membantu penulis dalam mencari dosen. Selain itu, penulis pun sangat mengucapkan terimakasih kepada seluruh dosen Matematika IPB yang telah mendidik, membimbing serta menurunkan ilmu pengetahuan yang sangat berguna pada penulis. Semoga penulis dapat memanfaatkan seluruh didikan dan ilmu yang telah diberikan sebaik mungkin. Amin. Wasalam
Eva Rachmania
DAFTAR ISI
DAFTAR ISI........................................................................................................vi DAFTAR GRAFIK............................................................................................vii DAFRAR LAMPIRAN......................................................................................vii PENDAHULUAN............................................................................................... 1 Latar Belakang............................................................................................. 1 Tujuan.......................................................................................................... 1 LANDASAN TEORI........................................................................................... 1 Ruang Contoh, Kejadian dan Peluang.......................................................... 1 Peubah Acak................................................................................................. 2 Jalan Acak.................................................................................................... 2 Rantai Markov.............................................................................................. 2 Klasifikasi State ........................................................................................... 3 Supremum dan Infimum............................................................................... 3 Waktu Markov.............................................................................................. 3 PEMBAHASAN.................................................................................................. 4 Strategi pemain.............................................................................................. 4 Fungsi imbalan pemain 1. Fungsi imbalan pemain I....................................................................... 5 2. Fungsi imbalan pemain II...................................................................... 6 Keadaan keseimbangan.................................................................................. 6 Contoh kasus................................................................................................... 8 SIMPULAN......................................................................................................... 10 DAFTAR PUSTAKA.......................................................................................... 11
DAFTAR GRAFIK
Grafik 1....................................................................................................................4 Grafik 2....................................................................................................................7 Grafik 3....................................................................................................................8
DAFTAR LAMPIRAN
Lampiran 1.............................................................................................................12 Lampiran 2.............................................................................................................13 Lampiran 3.............................................................................................................14 Lampiran 4.............................................................................................................17
PENDAHULUAN Latar Belakang Ada banyak permasalahan dalam kehidupan sehari-hari yang termasuk ke dalam bentuk proses stokastik. Proses stokastik itu sendiri merupakan salah satu bentuk permasalahan yang terkait dengan aturan-aturan peluang, dimana keadaan yang akan terjadi pada waktu yang akan datang tidak dapat diketahui secara pasti. Salah satu bentuk permasalahan dari suatu proses stokastik adalah jalan acak (random walk). Jalan acak umumnya digunakan untuk memodelkan situasi yang tidak pasti (gambling situations) , misalnya seperti model pembentukan harga di pasar bursa atau dapat digunakan untuk menganalisis sistem antrian (queueing system) dan sistem kebangkrutan (ruin system). Dalam tulisan ini, dikaji suatu permainan dengan bentuk khusus jalan acak simetrik (symmetric random walks). Permainan jalan acak ini dimainkan oleh 2 orang pemain dalam suatu himpunan state E={0,1,…,K}. Diketahui bahwa pemain I memulai permainan pada suatu
state a dan pemain II pada state b, dengan syarat state a
LANDASAN TEORI Ruang Contoh, Kejadian dan Peluang Definisi 1 ( Percobaan Acak) Dalam suatu percobaan seringkali dilakukan pengulangan, yang harus dilakukan dalam kondisi yang sama. Walaupun kita dapat mengetahui semua kemungkinan hasil yang akan muncul, tetapi hasil pada percobaan berikutnya tidak dapat diduga dengan tepat. Percobaan semacam ini, yang dapat diulang dalam kondisi yang sama, disebut percobaan acak. [Hogg dan Craig, 1995] Definisi 2 (Ruang Contoh dan Kejadian) Himpunan dari semua kemungkinan hasil dari suatu percobaan acak disebut ruang contoh, dinotasikan dengan Ω . Suatu kejadian A adalah himpunan bagian dari ruang contoh Ω . [Grimmett dan Stirzaker, 1992]
Definisi 3 (Medan −σ ) Medan −σ adalah suatu himpunan F yang anggotanya terdiri atas himpunan bagian ruang contoh Ω , serta memenuhi kondisi berikut : 1. φ ∈ F . ∞
2. Jika A1, A2 ,... ∈ F maka U Ai ∈ F . i −1
3. Jika A ∈ F maka A ∈ F . [Grimmett dan Stirzaker, 1992] c
Definisi 4 (Ukuran Peluang) Suatu ukuran peluang ? pada ( Ω ,F )
adalah
suatu fungsi ? : F → [0,1] yang memenuhi : 1. ? (φ ) = 0, ? (Ω ) = 1.
2. Jika Α1 , Α2 ,... ∈ F adalah himpunanhimpunan yang saling lepas, yaitu Α i ∩ Α j = φ untuk setiap pasangan i ≠ j , maka
∞ ∞ ? U Αi = ∑ ? ( Αi ). i =1 i=1 Pasangan ( Ω ,F ,P) disebut ruang peluang. [Grimmett dan Stirzaker, 1992] Definisi 5 (Kejadian Saling Bebas) Kejadian Α dan Β dikatakan saling bebas jika ? (ΑI Β) = ? (Α )? (Β). Secara umum himpunan kejadian {Αi , i ∈ I } dikatakan saling bebas jika ? I Αi = ∏ ? ( Αi ), i∈J i∈J untuk setiap himpunan bagian berhingga J dari I. [Grimmett dan Stirzaker, 1992]
Peubah Acak Definisi 6 (Peubah Acak) Suatu peubah acak Χ adalah suatu fungsi Χ : Ω → R dengan sifat bahwa untuk setiap x ∈ R , {w ∈ Ω; Χ(w) ≤ x}∈ F. [Grimmett dan Stirzaker, 1992] Definisi 7 (Peubah Acak Diskret) Peubah acak Χ dikatakan diskret jika nilainya hanya pada himpunan bagian yang tercacah {x1, x2 ,....} dari R . [Grimmett dan Stirzaker, 1992]
Jalan Acak Definisi 8 (Ruang State) Misalkan S = { x1 , x 2 ,..., xn } ⊂ R , untuk n ∈ N adalah nilai dari barisan peubah acak, maka S disebut ruang state. [Grimmett dan Stirzaker, 1992] Definisi 9 (Proses Stokastik) Proses Stokastik {Χ(t ), t ∈ T } adalah suatu himpunan dari peubah acak yang memetakan suatu ruang contoh Ω ke suatu ruang state S. [Ross, 2000] Jadi, untuk setiap t pada gugus (himpunan) indeks T , Χ(t ) adalah suatu peubah acak. Indeks t sering di interpretasikan sebagai waktu
dan Χ(t ) disebut sebagai state (keadaan) dari suatu proses pada waktu t. Ruang state S mungkin berupa : (i) S = Ζ (himpunan bilangan bulat, atau himpunan bagiannya). (ii) S = R (himpunan bilangan nyata, atau himpunan bagiannya). Suatu proses stokastik Χ disebut proses stokastik dengan waktu diskret jika himpunan indeks T adalah himpunan tercacah, sedangkan Χ disebut proses stokastik dengan waktu kontinu jika T adalah suatu interval. Definisi 10 (Jalan Acak) Jalan acak sederhana adalah suatu rantai Markov dengan state (ruang state) adalah himpunan bilangan bulat dan mempunyai peluang transisi p i , i +1 = p = 1 − p i , i −1 ; i = 0, ±1, ±2 ,... dengan 0 < p < 1 . Dengan kata lain, pada tiap transisi perpindahan akan bergerak satu langkah ke kanan dengan peluang p atau bergerak satu langkah ke kiri dengan peluang 1-p. [Ross, 2000] Suatu proses jalan acak yang memiliki peluang 1 transisi p = disebut jalan acak simetrik. 2
Rantai Markov Definisi 11 (Rantai Markov dengan Waktu Diskret) Proses Stokastik { X n , n = 0,1, 2,...} , dengan ruang state {0,1,2,…}, disebut Rantai Markov dengan waktu diskret jika untuk setiap n = {0,1,2,...} berlaku
P( X n+1 = j X n = i, X n−1 = in−1,...,X1 = i1, X 0 = i0) = P ( X n +1 = j X n = i ) . untuk semua kemungkinan i0 , i1 ,..., in −1 , i, j ∈ {0,1,2,...} .
nilai
(1) dari
[Ross, 2000] Persamaan (1) menyatakan bahwa dalam suatu rantai Markov, peluang dari Xn+1 bernilai j hanya tergantung pada Xn , apapun yang terjadi sebelumnya. Hal ini disebut dengan sifat Markov.
Definisi 12 ( Rantai Markov Homogen) Rantai Markov Xn disebut homogen jika P Xn+1 = j X n = i = P X1 = j X0 = i = pi , j ,
(
) (
)
[Ross, 2000] Supremum dan Infimum
untuk semua n dengan i, j ∈ {0,1,2,...} . [Ross, 2000]
Definisi 16 (Batas Atas dan Batas Bawah) (i) Bilangan a ∈ R disebut batas atas dari himpunan A, jika x ≤ a , ∀x ∈ A .
p i, j = pij ,
(ii) Bilangan b ∈ R disebut batas bawah dari himpunn A, jika x ≥ b, ∀x ∈ A .
Jadi pada rantai Markov homogen disebut peluang transisi satu tergantung dari waktu n. Nilai
step,
tidak
menyatakan peluang perpindahan dari state i ke state j. Karena nilai peluang adalah tak negatif dan karena proses tersebut harus mengalami transisi ke suatu state, maka (i) pij ≥ 0 , untuk semua i, j ∈ {0,1,2,...} , (ii) ∑∞j =0 pij = 1 , untuk semua i ∈ {0,1,2,...} . Misalkan P adalah matriks peluang transisi satustep p ij , maka matriks P berbentuk :
state akhir i0
i0 p0, 0 i1 p1, 0 P = state awal i2 p2, 0 M M
i2
K
p0,1
p0,2
p1,1
p1, 2
p2,1
p2, 2
M
M
K K K M
i1
[Golberg, 1976]
p ij di atas
Definisi 17 ( Supremum & Infimum) Misalkan himpunan A ≠ φ . Bilangan a ∈ R disebut Supremum (batas atas terkecil) dari A dan ditulis a = Sup( A) , jika : (i) a adalah batas atas A. (ii) Jika c < a , maka c bukan batas atas A. 1.
2.
Bilangan b ∈ R disebut Infimum (batas bawah terbesar) dari A dan ditulis b = Inf ( A) , jika:
(i) b adalah batas bawah A. (ii) Jika d > b , maka d bukan batas bawah A. [Golberg, 1976]
Waktu Markov Klasifikasi State Definisi 13 ( State Terakses) Suatu state j disebut terakses (accessible) dari state i, jika ada minimal sebuah bilangan bulat k=0 sehingga
p i(,kj) > 0 .
Definisi 18 (Filtrasi) Filtrasi adalah himpunan F={F t : t ≥ 0 } dari submedan-σ dari F jika F s ⊆ F t untuk setiap s≤t . [Grimmett dan Stirzaker, 1992]
[Ross, 2000] Definisi 14 (State Berkomunikasi) Dua state i dan j disebut berkomunikasi (communicate) , jika state i dapat diakses dari state j dan state j dapat diakses dari state i. [Ross, 2000] Definisi 15 (State Penyerap) Suatu state i disebut state penyerap (absorbing state) jika
p ii = 1 .
Definisi 19 (Stopping time) Peubah acak T yang mengambil nilai dari {0,1,2,.....} ∪ {∞} disebut dengan stopping time ( yang terkait dengan filtrasi F ) jika {T=n} ∈ F n untuk setiap n ≥ 0 . [Grimmett dan Stirzaker, 1992] Stopping time terkadang disebut dengan waktu Markov.
PEMBAHASAN
Diketahui sebuah permainan dengan bentuk jalan acak bebas simetrik . Permainan ini terdiri atas dua pemain, dimana proses jalan acak dari kedua pemain masing-masing direpresentasikan oleh xn dan yn . Peubah acak xn dan yn adalah proses jalan acak simetrik yang berada dalam himpunan state E = {0,1,..., K } . Diasumsikan peluang berpindah pada setiap state p i ,i +1 = p = 1 − p i ,i −1 ; i = 0 ,1,..., K adalah sebesar p = 0.5 . Namun khusus pada state 0 dan K , selain memiliki peluang berpindah sebesar 0.5 menuju state 1 dan K − 1 atau sebaliknya. Pada state ini juga memiliki peluang untuk tidak berpindah (absorbed) sebesar 0.5. 0.5
0.5
yaitu −1 dan K + 1 untuk menyatakan penyerapan yang terjadi pada state 0 dan K . Dengan kata lain, state −1 dan K + 1 adalah state penyerap (absorbing state) dalam permainan ini. Ini berarti, permainan akan dengan sendirinya berakhir ketika salah satu dari kedua pemain mencapai state tersebut untuk pertama kalinya. Dimana jika pemain terserap di state −1 maka pemain tersebut berarti mengalami kekalahan dan sebaliknya jika pemain tersebut berhasil terserap di state K + 1 maka pemain tersebut akan mencapai kemenangan. Karena state −1 dan K + 1 adalah state penyerap maka p −1, −1 = 1 = p K +1, K +1 , sedangkan pada state lainnya peluang untuk bertransisi +1 dan -1 adalah sebesar p = 0.5 ,
p i ,i +1 = p = 1 − p i , i −1
atau
0.5 0
K-1
1
0.5
0.5
K 0.5
untuk
setiap
i = 0,1,..., K . Maka bentuk matriks peluang transisi satu langkah dari permainan ini adalah sebagai berikut :
Gambar 1. −1 0
Permainan ini akan dimulai ketika kedua pemain telah berada pada sembarang state a dan b , dimana 1 ≤ a < b ≤ K − 1 . Kemu dian pemain I mengamati jalan acak xn sedangkan pemain II mengamati jalan acak yn . Setelah itu kedua pemain akan memutuskan berhenti pada waktu Markov τ dan σ yang merupakan strategi penghentian mereka. Diasumsikan setiap pemain mengetahui nilai K, a dan b , akan tetapi mereka tidak mempunyai informasi mengenai tindakan pemain lain. Adapun peraturan permainan adalah sebagai berikut : • jika xτ > yσ maka pemain II membayar pemain I sebesar $1 ; • jika xτ < y σ maka pemain I yang membayar kepada pemain II sebesar $1 ; dan • jika xτ = yσ maka hasil dari pemainan adalah seri. Setiap pemain menginginkan agar dapat memaksimalkan nilai harapan dari hasil permainannya. Oleh karena pada state 0 dan K diketahui memiliki peluang terserap (absorbed) sebesar 0.5 , maka diasumsikan suatu state khayalan
−1 0 1
1 0.5 0 2 0 3 0 P= 4 0 M M K −1 0 K 0 K +1 0
1
2
LL
3 4
K −1
K K +1
0 0 0
LL LL LL
0 0 0
0 0 0
0 0.5 0 0.5 0 0 0 0.5 0 0.5
LL LL
0 0
0 0
0 M 0
0 M 0
0 0.5 0 M M M 0 0 0
LL O O
0 M 0
0 M 0.5
0 0
0 0
0 0
LL LL
0.5 0
0 0
0 0 0 0 0 0.5 0 0 0.5 0 0.5 0
0 0
0 0
0 0 0 0 0 0 M 0 0.5 1
Dari matriks tersebut diketahui bahwa state −1 dan K + 1 dapat di akses dari setiap state {0,1,..., K} , tetapi tidak sebaliknya. Maka kelas dari rantai Markov ini adalah {− 1} , {0,1,..., K} , dan { K + 1} . Strategi Pemain Setiap pemain menginginkan agar dapat memaksimumkan nilai imbalan yang diperolehnya dalam permainan. Untuk itu, kedua pemain perlu menerapkan suatu strategi
penghentian yang optimal dalam menghadapi strategi pemain lainnya. Jika dimisalkan vektor s = (s −1, s0 ,..., sK +1 )
dan t = (t − 1, t0 ,..., tK +1) adalah vektor peluang dari strategi penghentian kedua pemain, yaitu τ dan σ , dimana si = P{ xτ = i} menyatakan nilai peluang ketika pemain I berhenti pada saat titik ke- i ; dan ti = P{ yσ = i} menyatakan nilai peluang ketika pemain II berhenti pada saat titik ke- i dengan i = −1,0 ,1,.., K + 1 . Maka vektor si dan ti disebut vektor peluang penghentian dari τ dan σ .
strategi
dan
1 ; i = 1; b b −1 ; i = 2r, b(b + 2) 1 ≤ r ≤ min{K - b - 1, b}; 2 ; i = 2r + 1, ti = b(b + 2) 1 ≤ r ≤ min{K - b - 1, b - 1}; (b +1) max2b − K, (1− b) +b −1 (b +1) ; i = K; b(b + 2) selainnya 0; untuk i ∈ E.
(4) [ Mazalov dan Kochetov,1998]
Teorema 1.
s = (s −1, s0 ,..., sK +1 ) dan t = (t − 1, t0 ,..., tK +1) merupakan vektor peluang dari strategi penghentian τ dan σ yang optimal, jika dan hanya jika kedua kondisi berikut terpenuhi : Sebuah
vektor
K +1
K +1
i = −1
i = −1
∑ is i = a; ∑ s i = 1;
s i ≥ 0 ; i = − 1 , 0 ,..., K + 1 .
(1) dan K +1
K +1
i= − 1
i= − 1
Terlihat jelas bahwa (3) dan (4) memenuhi kondisi (1) dan (2). (lihat Lampiran 1 dan 2).
Fungsi Imbalan 1.
Fungsi imbalan pemain I. Fungsi imbalan bagi pemain I berdasarkan aturan permainan adalah
{
H(τ ,σ) = E I{0≤yσ <xτ ≤K} − I{0≤xτ
0} + I {xτ =K +1, yσ >0 } − I {xτ = −1, yσ >0} − I { yσ =K +1, xτ < K}
∑ it i = b ; ∑ t i = 1;
(5)
t i ≥ 0 ; i = − 1 , 0 ,..., K + 1 .
(2) Bukti : Lihat Mazalov , 1987. Berdasarkan Teorema 1, maka untuk meyelesaikan masalah dari permainan jalan acak simetrik tersebut, cukup dengan mencari strategi *
}
*
penghentian optimal ( s , t ) yang memenuhi kondisi (1) dan (2). Dengan asumsi bahwa b + 1 < K ≤ 2b , maka nilai K terbatas dan dipengaruhi oleh state awal yang diambil oleh pemain II. Strategi *
*
penghentian optimal dari s dan t yang memenuhi Teorema 1 adalah sebagai berikut :
b − a +1 ; b+2 a +1 ; si = b(b + 2) max{2b − K +1,0} ; (a +1) b(b + 2) 0;
K xτ −1 K+1 H(τ ,σ ) = E− ∑ti I{xτ ≤0} + ∑ ti − ∑ti +t−1 −t K+1I{0<xτ
K −1 + ∑ ti I{xτ ≥ K} . i = −1
i = -1; i = 2r, 1 ≤ r ≤ min{K - b - 1,b};
(6) Ke mudian dari nilai harapan persamaan (6) dapat dituliskan menjadi fungsi seperti berikut:
i = K; selainnya untuk i ∈ E
yaitu, nilai harapan jika pemain I menang dari pemain II dikurangi dengan nilai harapan jika pemain I kalah dari pemain II. Ketika strategi σ sudah ditentukan maka fungsi imbalan (5) dapat ditulis seperti berikut :
(3)
(
)
K +1 ∑ ti − t−1 − t0 − i=− ; I{xτ ≤0} 1 xτ xτ −1 K +1 f ( x, t) = ∑ ti + t xτ − txτ − ∑ ti − ∑ ti ; I{0<xτ
∑ ti = 1 , t i ≥ 0 , i = −1,0 ,1,.., K + 1 ,
i =−1
maka
−1 + t−1 + t0; x = −1,0 ; x f1( x) = f ( x, t) = 2 ∑ ti − t x −1; x = 1,..., K − 1; i= −1K−1 ∑ti ; x = K , K + 1; i =−1
dimana f1 ( x) menyatakan fungsi imbalan dari pemain I. Kemudian berdasarkan strategi (4) yang merupakan vektor peluang dari strategi σ dan asumsi bahwa b + 1 < K ≤ 2b , maka fungsi imbalan pemain I adalah −1; x = -1,0; 1−b x = 1; ; b −1+ (b +1)(x +1) ; x = 2,3,… ,2(K- b) -1; b(b + 2) f1( x) = (b +1)(K − b) +1 x = 2(K - b),…, K -1; −1+ 2 b(b + 2) ; −1+ (b +1)(K +1) ; x = K, K + 1. b(b + 2) (7) Perhitungan (7) ada pada Lampiran 3. 2. Fungsi imbalan pemain II. Kebalikan dari pemain I, fungsi imbalan pemain II berdasarkan aturan permainan adalah nilai harapan jika pemain II menang dari pemain I dikurangi dengan nilai harapan jika pemain II kalah dari pemain I. Melalui penurunan yang sama pada persamaan (6) , maka didapatkan fungsi imbalan pemain II sebagai berikut : − 1 + s−1 + s0 ; x f 2 ( x) = f ( x , s ) = 2 ∑ s i − s x − 1; i = − 1K −1 ∑ si ; i= − 1
x = − 1 ,0 ; x = 1,..., K − 1; x = K , K + 1;
K +1
dengan s=(s-1 ,s0 ,s1 ,……,sK+1 ), ∑ si = 1 ,s i i =−1
i = −1,0 ,1,.., K + 1 .
= 0
,
Berdasarkan strategi (3) yang merupakan vektor peluang dari strategi τ dan asumsi bahwa b + 1 < K ≤ 2b , maka fungsi imbalan pemain II adalah x = -1,0; a +1 − ; b+ 2 (a +1)(x −1) + b(b − 2a) x = 1,2,… ; ,2(K - b - 1) + 1; b(b + 2) f2(x) = 2(a +1)(K −b −1) + b(b − 2a) ;x = 2(K - b -1) + 1, … b(b + 2) , K - 1; (a +1)(K −1) + b(b − 2a) x = K, K + 1. ; b(b + 2) (8) Perhitungan (8) ada pada Lampiran (4).
Keadaan Keseimbangan Dalam permainan ini, setiap pemain mengharapkan dapat memaksimumkan nilai imbalannya atau meminimumkan nilai imbalan pemain lainnya dengan strategi penghentian optimal yang diterapkan oleh masing-masing pemain. Keadaan keseimbangan dalam permainan ini adalah situasi jika maksimum nilai fungsi imbalan pemain I sama dengan minimum nilai fungsi imbalan pemain II. Oleh karena itu, keadaan keseimbangan pada permainan dapat diperoleh jika strategi penghentian optimal τ * dan σ * yang dipilih oleh kedua pemain tersebut memenuhi :
(
)
(
)
supt H τ ,σ * =infs H τ * , σ =H* , (9) dimana
sup H (τ , σ * ) = sup E f 1 ( xτ ) = v1 ( a); τ
τ
inf H (τ * ,σ ) = − sup E f2 ( xσ ) = −v 2 (b); σ
σ
sehingga ketika v1 ( a) = − v2 ( b) = H * maka
(τ * ,σ * )
(10)
merupakan
keseimbangan dari permainan dan H nilai dari permainan tersebut.
keadaan *
adalah
fungsi imbalan pemain I pada saat K = 2 b . Garis lurus tersebut memiliki persamaan y = −1 + ( x + 1)(b + 1) (b( b + 2)) . Oleh karena itu, solusi dari penghentian optimal bagi pemain I ketika pemain II menerapkan suatu strategi σ * adalah pada saat fungsi imbalan pemain I bernilai ( x + 1)( b + 1) v1 ( x ) = −1 + (11) b( b + 2) dan saat pemain I memutuskan berhenti pada x = a maka persamaan (11) menjadi seperti berikut ( a + 1)( b + 1) v1 ( a) = − 1+ . b(b + 2)
Berdasarkan persamaan (9), keadaan keseimbangan diperoleh ketika nilai maksimum dari nilai imbalan pemain I saat pemain II melakukan strategi tertentu (σ * ) , bernilai sama dengan nilai minimum dari nilai imbalan pemain II saat pemain I melakukan strategi tertentu (τ * ) . Fungsi imbalan pemain I pada Gambar 2 dimisalkan y = f1 ( x ) . Untuk nilai K yang diasumsikan berada pada selang b + 1 < K < 2b , fungsi imbalan pemain I digambarkan dengan garis putus-putus pada Gambar 2. Sedangkan garis lurus yang menghubungkan titik ( x = −1; y = − 1) dengan titik
( x = K ; y = −1 + (b + 1)( K + 1) (b(b + 2))) adalah
y
x
2(K-b) -1
0
1
2
2(K-b-1)+1
K-1
K
K+1
Gambar 2. Grafik fungsi f1 ( x) , dengan b + 1 < K ≤ 2b . Pada Gambar 3, fungsi imbalan pemain II yang dimisalkan y = f 2 ( x) , digambarkan dengan garis putus-putus untuk nilai K yang berada pada selang b + 1 < K < 2b . Sedangkan untuk nilai K = 2 b digambarkan dengan sebuah garis lurus yang menghubungkan titik ( x = 1; y = (b − 2a) b(b + 2)) dengan titik
Oleh karena itu, solusi penghentian optima l bagi pemain II ketika pemain I menerapkan
( x = K ; y = ( a + 1)( K − 1) + b(b − 2a) ( b(b + 2))) . Garis lurus tersebut memiliki persamaan y = [( a + 1)( x − 1) + b( b − 2a)] [b(b + 2)] pada selang [1; K ] .
untuk berhenti pada x = b maka persamaan (12) menjadi (b − a)( b + 1) − 1 v 2 (b) = . b(b + 2)
suatu strategi τ * adalah pada saat fungsi imbalan pemain II bernilai ( a + 1)( x − 1) + b(b − 2a) v 2 (x ) = (12) b(b + 2) untuk x ∈[1; K ] . Saat pemain II memutuskan
y
x
1 -1
0
2
2(K-b-1)+1
K-1
K
K+1
Gambar 3. Grafik fungsi f 2 ( x) , dengan b + 1 < K ≤ 2b .
v1 ( a) dan nilai − v2 ( b) memenuhi persamaan (10), sehingga nilai permainan dari strategi optimal (3) dan (4) dengan asumsi b + 1 < K ≤ 2b adalah
dari pemain I bernilai v1 ( x) dan fungsi imbalan
(b − a)( b + 1) − 1 . b(b + 2) Ini berarti, keadaan keseimbangan pada permainan ini akan terjadi saat fungsi imbalan
dan −v 2 ( x) dengan state penghentian kedua pemain sama dengan state awalnya. Dengan kata lain, pada saat permainan berhenti posisi kedua pemain kembali berada pada posisi awal.
Terlihat bahwa nilai
H* =−
pemain
II
v2 ( x ) .
Sedangkan
nilai *
keseimbangan dari permainan , yaitu H , akan tercapai apabila fungsi imbalan bernilai v1 ( x)
Contoh Kasus
1. Jika dimisalkan pemain I memulai permainan dari state a = 4 sedangkan pemain II dari state b = 6 , maka bagaimanakah nilai dari fungsi imbalan kedua pemain untuk nilai K yang berbeda dan berapakah nilai dari permainan pada saat situasi keseimbangan?
Jawab : Nilai dari fungsi imbalan kedua pemain di setiap state untuk nilai K yang berbeda dapat dilihat melalui Tabel 1 berikut ini :
a> Untuk K = 10
Tabel 1. Fungsi imbalan pemain I dan II dengan nilai K yang berbeda
Grafik Fungsi Imbalan Pemain I dan II 0.8
x
f1(x)
K=12 f2(x)
f1(x)
0.6
f2(x)
y (nilai imbalan)
K=10
0.4 0.2 0 -0.2 -1 0 1 2 3 4 5 6 7 8 9 1 0 1 1
-1
-1
-0.625
-1
-0.625
0
-1
-0.625
-1
-0.625
1
-0.70833
-0.25
-0.70833
-0.25
2
-0.5625
-0.14583
-0.5625
-0.14583
3
-0.41667
-0.04167
-0.41667
-0.04167
Pemain I
4
-0.27083
0.0625
-0.27083
0.0625
b> Untuk K = 2b = 12
5
-0.125
0.166667
-0.125
0.166667
Grafik Fungsi Imbalan Pemain I dan II
6
0.020833
0.270833
0.020833
0.270833
7
0.166667
0.375
0.166667
0.375
8
0.208333
0.375
0.3125
0.479167
9
0.208333
0.375
0.458333
0.583333
10
0.604167
0.6875
0.604167
0.6875
11
0.604167
0.6875
0.75
0.791667
1 0.8 0.6 0.4 0.2 0 -0.2 -1 0 1 2 3 4 5 6 7 8 9 1 0 1 1 12 13 -0.4 -0.6 -0.8 -1
12
0.895833
0.895833
13
0.895833
0.895833
-0.4 -0.6 -0.8 -1
y (nilai imbalan)
x (state penghentian)
x (state penghentian) Pemain I
Sedangkan perbandingan nilai fungsi imbalan kedua pemain tersebut untuk nilai K yang berbeda dapat di lihat melalui grafik berikut ini :
.
Pemain II
Pemain II
Keadaan keseimbangan dalam permainan ini jika dilihat dari tabel adalah ketika nilai fungsi imbalan pemain I kalah sebesar 0.270833 dan pemain II menang sebesar 0.270833. Sehingga nilai keseimbangan dari permainan ini adalah 0.270833.
SIMPULAN Pada permainan dengan bentuk jalan acak bebas simetrik pada suatu himpunan E = {0,1,..., K} , dimana pada state 0 dan K memiliki peluang untuk tetap berada pada state tersebut (terserap) sebesar 0.5, maka perlu dimisalkan suatu state khayalan untuk menyatakan terjadinya proses penyerapan, yaitu state -1 dan K+1. Diketahui bahwa untuk dapat memaksimumkan nilai harapan dari hasil permainan atau yang biasa disebut dengan imbalan pemain, maka pemain memerlukan strategi penghentian yang optimal. Strategi penghentian yang optimal berdasarkan Teorema 1 adalah ketika pemain I menghentikan permainan hanya pada state genap saja, sedangkan pemain II dapat menghentikan permainan baik di state genap maupun ganjil. Kemudian dari strategi tersebut dapat diperoleh fungsi imbalan pemain. Fungsi imbalan bagi kedua pemain akan semakin
optimal apabila nilai dari state K yang diasumsikan berada pada selang b + 1 < K ≤ 2b , bernilai K = 2 b . Keadaan keseimbangan dari permainan ini adalah sepasang strategi penghentian optimal yang diterapkan oleh kedua pemain sehingga batas maksimum nilai fungsi imbalan pemain I memiliki nilai yang sama dengan batas minimum nilai fungsi imbalan pemain II. Oleh karena itu, keadaan keseimbangan ini akan tercapai jika dengan strategi yang optimal dari kedua pemain, salah satu pemain menang dan pemain lainnya kalah dengan nilai fungsi imbalan yang sama. Keadaan ini akan tercapai apabila pada saat permainan berhenti kedua pemain berada kembali pada state awalnya , yaitu a dan b. Sehingga nilai dari permainan ini adalah (b − a)( b + 1) − 1 H* =− . b(b + 2)
DAFTAR PUSTAKA
Goldberg, R. R. 1976. Methods of Real Analysis. Ed.ke-2. John Wiley & Sons. New York. Grimmett, G. R. dan D. R. Stirzaker. 1992. Probability and Random Processes. Ed. ke -2. Clarendon Press. Oxford. Hogg, R. V. dan A. T. Craig. 1995. Introduction to Mathematical Statistics. Ed. ke-5. Prentice Hall, Englewood Cliffs. New Jersey.
Mazalov, V. V. 1987. Game Stopping Times. Nauka. Novosibirsk. (in Russian) Mazalov, V. V. dan E. A. Kochetov. 1998. A Game With Optimal Stopping of Random Walks. SIAM JOURNALS Theory of Probability & 1ts Applications. Vol. 42, No. 4, pp. 697-701. Ross, S. M. 2000. Introduction to Probability Models. Ed. Ke -7. Academic Press. San Diego.
Lampiran Lampiran 1. Bukti bahwa K +1
K +1
i = −1
i = −1
(3)
memenuhi
Teorema
1
kondisi
(1),
maka
haruslah
∑ is i = a; ∑ s i = 1; s i ≥ 0 ; i = − 1 , 0 ,..., K + 1 .
Untuk r berada pada selang 1 ≤ r ≤ K − b − 1 , perhitungannya adalah sebagai berikut : Ø
K +1
∑ is i = a;
i = −1
K +1
∑ isi = ( −1).s −1 + 0.s0 + 1.s1 + 2.s 2 + ... + 2( K − b − 1). s2( K −b −1) + ... + ( K − 1). s K −1 + K .s K + ( K + 1).s K +1
i =−1
a +1 b − a +1 (a + 1)( 2b − K + 1) = − + K. + (2 + 4 + ... + 2( K − b − 1)). b(b + 2) b+2 b(b + 2) a +1 ( a + 1)( 2b − K + 1) b − a + 1 ( K − b − 1) + K. = − .( 2. 2 + [( K − b − 1) − 1]. 2). + b + 2 2 b ( b + 2 ) b(b + 2) − b(b − a + 1) + ( K − b − 1)( K − b)( a + 1) + K (a + 1)( 2b − K + 1) = b(b + 2) =
− (b 2 − ab + b) + (a + 1)[( K − b − 1)( K − b) + K ( 2b − K + 1) ] b(b + 2)
=
( −b 2 + ab − b) + (a + 1) K 2 − Kb − bK + b 2 − K + b + 2Kb − K 2 + K b( b + 2)
=
( −b 2 + ab − b) + (a + 1) b2 + b b(b + 2)
=
− b2 + ab − b + ab2 + ab + b2 + b b( b + 2)
=
ab2 + 2ab a.b(b + 2) = = a. b(b + 2) b( b + 2)
Ø
[ [
]
]
K +1
∑ s i = 1;
i = −1
K +1
∑ s i = s −1 + s 0 + s1 + s2 + .... + s2 ( K −b )−1 + ... + s K −1 + s K + s K +1
i =−1
= s −1 + ( s 2 + s 4 + ... + s 2 (K −b )− 2 ) + ( s3 + s 5 + ... + s2 ( K −b ) −1 ) + s K =
b − a +1 ( a + 1) ( a + 1)( 2b − K + 1) + + ⋅ ( K − b − 1) + (b + 2 ) b ( b + 2 ) b( b + 2)
=
b (b − a + 1) + (a + 1)( K − b − 1) + ( a + 1)( 2b − K + 1) b ( b + 2)
b 2 + 2b b (b + 2 ) b (b + 2 ) = = 1. b (b + 2 ) Jadi terbukti bahwa (3) memenuhi kondisi ke -(1) pada Teorema 1, untuk r berada pada selang 1 ≤ r ≤ K − b −1 . =
Lampiran 2. Bukti bahwa K +1
K +1
i= − 1
i= − 1
(4)
memenuhi
Teorema
1
kondisi
(2),
maka
haruslah
∑ it i = b ; ∑ t i = 1; t i ≥ 0 ; i = − 1 , 0 ,..., K + 1 .
Untuk r berada pada selang 1 ≤ r ≤ K − b − 1 , perhitungannya adalah sebagai berikut : Ø
K +1
∑ it i = b ;
i= − 1
K +1
∑ it i = ( − 1 ).t − 1 + 0 .t 0 + 1 .t 1 + 2 .t 2 + 3 .t 3 + ... + 2 ( K − b − 1). t 2 ( K − b − 1) + ... + ( K − 1). t K − 1 + K .t K + ( K + 1). t K + 1
i= − 1
= t1 + ( 2 .t 2 + 4 .t 4 + ... + ( 2 ( K − b ) − 2 ). t ( 2 ( K − b ) − 2 ) ) + ( 3 .t 3 + 5 .t 5 + ... + ( 2 ( K − b ) − 1). t ( 2 ( K − b ) − 1 ) ) + K .t K =
1 b −1 + ( 2 + 4 + ... + ( 2 ( K − b ) − 2 )) b b(b + 2)
2 + ( 3 + 5 + ... + ( 2 ( K − b ) − 1)) b(b + 2)
( b + 1)( 2 b − K ) + b − 1 + K b(b + 2) =
1 ( K − b − 1) b − 1 (K − b − 1) 2 + + ( 2 .2 + [( K − b − 1) − 1]. 2 ) ( 2 . 3 + [( K − b − 1) − 1 ]. 2 ) b 2 b ( b + 2 ) 2 b ( b + 2 )
( b + 1)( 2 b − K ) + b − 1 + K b(b + 2) =
1 b −1 + ( K − b − 1)( K − b ) b b(b + 2)
2 K (b + 1)( 2 b − K ) + K ( b − 1) + ( K − b − 1 )( K − b + 1) b(b + 2) + b (b + 2 ) ( b + 2 ) + ( K − b − 1 )( K − b )( b − 1 ) + 2 ( K − b − 1)( K − b + 1) + K (b + 1)( 2 b − K ) + K ( b − 1) = b (b + 2 ) =
( b + 2 ) + ( K − b − 1 )[( K − b )( b − 1) + 2 ( K − b + 1) ] + K ( b + 1)( 2 b − K ) + K ( b − 1) b(b + 2)
= =
[
( b + 2 ) + ( K − b − 1 ) Kb − b
]
+ k − b + 2 + K ( b + 1 )( 2 b − K ) + K (b − 1 ) b (b + 2 ) ( b + 2 ) + ( K − b − 1 )[K ( b + 1) − ( b + 2 )( b − 1) ] + K ( b + 1)( 2 b − K ) + K ( b − 1) 2
b (b + 2) ( b + 2 ) + K ( b + 1)( K − b − 1) − (b + 2 )( b − 1)( K − b − 1) + K (b + 1)( 2 b − K ) + K ( b − 1) = b(b + 2) = =
( b + 2 ) [1 − (b − 1 )( K − b − 1) ]+ K ( b + 1) [( K − b − 1) + ( 2 b − K ) ] + K ( b − 1 ) b(b + 2)
[
( b + 2 ) 1 − Kb + K + b
[
]
2
]
− 1 + K ( b + 1) [b − 1] + K ( b − 1) b (b + 2 )
=
( b + 2 ) K (1 − b ) + b 2 + K ( b − 1) [( b + 1 ) + 1 ] b (b + 2 )
=
K (1 − b )( b + 2 ) + b ( b + 2 ) + K ( b − 1)( b + 2 ) b (b + 2 )
=
2
K (b + 2 )[(1 − b ) + ( b − 1) ] + b 2 ( b + 2 ) b(b + 2)
= 0+
b 2 (b + 2) = b. b(b + 2)
Ø
K +1
∑ t i = 1;
i= − 1
K +1
∑ t i = t −1 + t0 + t1 + t 2 + .... + t 2 ( K −b) −1 + ... + t K −1 + t K + t K +1
i =−1
= t 1 + (t 2 + t 4 + ... + t 2( K −b) −2 ) + (t 3 + t 5 + ... + t 2( K −b )−1 ) + t K =
2 (b + 1)(2b − K ) + (b −1) 1 (b −1) + ⋅ ( K − b − 1) + ⋅ (K − b −1) + b b(b + 2) b ( b + 2 ) b(b + 2)
=
(b + 2) + (b −1)(K − b −1) + 2( K − b −1) + (b + 1)(2b − K ) + b −1 b(b + 2)
b 2 + 2b b(b + 2 ) b(b + 2 ) = = 1. b(b + 2 ) =
Jadi terbukti bahwa (4) memenuhi kondisi ke -(2) pada Teorema 1, untuk r berada pada selang 1 ≤ r ≤ K − b −1 .
Lampiran 3. (Perhitungan persamaan (7)). •
Untuk x = −1,0;
f 1 ( x ) = − 1 + t −1 + t 0 = −1+ 0 + 0 = −1.
•
Untuk x = 1 x
f 1 ( x ) = 2 ∑ t −1 − t x − 1 i = −1 1
= 2 ∑ t − 1 − t1 − 1 i = −1
= 2 ( t − 1 + t 0 + t1 ) − t1 − 1 = 2 ( 0 + 0 + t1) − t1 − 1 = 2 t1 − t1 − 1 = t1 − 1 1 −1 b 1−b = . b =
•
Untuk x = 2,3,..., 2( K − b) − 1 x
f1( x) = 2 ∑ t i − t x − 1 i = −1
= 2 (t −1 + t 0 + t1 + t 2 + ... + t x ) − t x − 1 = 2 (0 + 0 + t1 + t 2 + ... + t x ) − t x − 1 = 2 t1 + 2( t 2 + t 4 + ... + t x− 1 ) + 2 (t 3 + t 5 + ... + t x ) − t x − 1 b −1 1 x −1 2 x −1 2 = 2 + 2 ⋅ + 2 ⋅ − −1 2 2 b( b + 2) b b (b + 2 ) b (b + 2 ) 2 (b + 2 ) + ( b − 1)( x − 1) + 2 ( x − 1) − 2 = −1 + b( b + 2) = −1 +
2 b + 4 + ( x − 1)[( b − 1) + 2 ] − 2 b (b + 2 )
= −1 +
2 b + 2 + ( x − 1)( b + 1) b ( b + 2)
2( b + 1) + ( x − 1)( b + 1) b (b + 2 ) ( b + 1)[ 2 + ( x − 1)] = − 1+ b ( b + 2) ( b + 1)( x + 1) = − 1+ . b (b + 2 ) = − 1+
•
Untuk x = 2( K − b),..., K − 1 x
f1( x) = 2 ∑ t i − tx − 1 i = −1
x− 1
K +1 x −1 x = ∑ t i − ∑ t i = ∑ t i − 1 − ∑ t i i = −1 i = x +1 i = −1 i = −1
=
2 ( K −b ) −1
∑
i = −1
ti − 1 +
2( K − b)
∑
i = −1
ti
= (t −1 + t 0 + t1 + ... + t 2 ( K −b ) −1 ) − 1 + (t −1 + t 0 + t 1 + ... + t 2 ( K −b ) −1 + t 2 ( K −b ) ) = ( 0 + 0 + t 1 + ... + t 2 ( K − b ) −1 ) − 1 + ( 0 + 0 + t1 + ... + t 2 ( K −b ) −1 + 0 ) = −1 + 2 t1 + 2( t 2 + t 4 + ... + t 2 ( K −b ) − 2 ) + 2( t 3 + t 5 + ... + t 2 ( K −b ) −1 ) b − 1 2(K − b) − 1 − 1 2 2(K − b) − 1 − 1 1 + 2 = −1 + 2 + 2 ⋅ ⋅ 2 2 b b (b + 2 ) b (b + 2 ) 2 (b + 2 ) + 2(( b − 1)(( K − b ) − 1) ) + 4 (( K − b ) − 1 ) = −1 + b (b + 2 )
= −1 +
2 b + 4 + ( K − b − 1 )[ 2 (b − 1 ) + 4 ] b (b + 2 )
2 b + 4 + ( K − b − 1)[ 2 b − 2 + 4 ] b ( b + 2) 2 b + 4 + ( K − b − 1)( 2 b + 4 ) − 2 ( K − b − 1 ) = − 1+ b (b + 2 ) ( 2 b + 4 )[1 + ( K − b − 1)] − 2 ( K − b − 1) = − 1+ b (b + 2 ) = − 1+
( 2 b + 2 + 2 )( K − b ) − 2 ( K − b ) + 2 b (b + 2 ) 2 b + 4 + ( K − b − 1 )[ 2 ( b − 1 ) + 4 ] = −1 + b (b + 2 ) 2 b + 4 + ( K − b − 1 )[ 2 b − 2 + 4 ] = −1 + b (b + 2 ) 2 ( b + 1 )( K − b ) + 2 = −1 + b (b + 2 ) 2 [( b + 1 )( K − b ) + 1 ] = −1 + b (b + 2 ) ( b + 1 )( K − b ) + 1 = −1 + 2 . b (b + 2 ) = − 1+
•
Untuk x = K , K + 1 K −1
K +1
i =−1
i= −1
f 1 ( x ) = ∑ t i = ∑ t i − t K − t K +1 = 1 − tK − tK +1 = 1−
( b + 1 )( 2 b − K ) + b − 1 −0 b(b + 2)
( b + 1 )( 2 b − K ) − (b + 1 ) + 2 b b( b + 2) ( b + 1 )[( 2 b − K ) − 1 ] + 2 b = 1− b (b + 2 ) = 1−
( b + 1 )( − K − 1) + 2 b ( b + 1 ) + 2 b b (b + 2 ) b (b + 2 ) − (b + 1 )( − K − 1) − 2 b (b + 1) − 2 b = b (b + 2 ) = 1−
=
b 2 + 2 b + ( b + 1 )( K + 1 ) − 2 b 2 − 2 b − 2 b b ( b + 2)
=
− b 2 − 2b + (b + 1)( K + 1) b (b + 2 )
=
− b (b + 2 ) + (b + 1)( K + 1) b (b + 2 )
= −1 +
( b + 1)( K + 1) . b( b + 2)
Lampiran 4. (Perhitungan persamaan(8)) •
Untuk x = −1,0;
f 2 ( x ) = − 1 + s −1 + s 0 b − a +1 +0 b+2 − (b + 2 ) + b − a + 1 = b+2 − a −1 = . b +2 = − 1+
•
Untuk x = 2,3,..., 2( K − b − 1) + 1 x
f 2 ( x ) = 2 ∑ si − s x − 1 i = −1
= 2 ( s−1 + s0 + s1 + s 2 + ... + s x ) − s x − 1 = 2 s −1 + 0 + 2( s1 + s2 + ... + s x ) − 0 − 1 = 2 s −1 + 2 ( s2 + s 4 + ... + s x −1 ) + 2( s 3 + s5 + ... + s x ) − 1 b − a + 1 a + 1 x −1 = 2 ⋅ + 0 − 1 + 2 b + 2 b (b + 2 ) 2 = −1 +
2 (b )( b − a + 1) + (a + 1)( x − 1) b ( b + 2)
= −1 +
2 b 2 − 2 ab + 2 b + ( a + 1)( x − 1) b (b + 2 )
=
− b 2 − 2b + 2b 2 − 2 ab + 2b + ( a + 1)( x − 1) b (b + 2 )
b 2 − 2 ab + ( a + 1)( x − 1) b (b + 2 ) ( a + 1)( x − 1) + b( b − 2a ) = . b (b + 2 ) =
•
Untuk x = 2( K − b − 1) + 1,..., K − 1 x
f 2 ( x ) = 2 ∑ si − s x − 1 i = −1
K +1 x −1 x = ∑ si − ∑ si = ∑ si − 1 − ∑ si i = −1 i = x +1 i = −1 i = − 1 x −1
=
2 ( K −b −1)
∑
i = −1
si − 1 +
2 ( K − b −1) +1
∑
i = −1
si
= ( s −1 + s 0 + s 1 + ... + s 2 ( K − b − 1) ) − 1 + ( s − 1 + s 0 + s1 + ... + s 2 ( K − b − 1) + s 2 ( K − b − 1) + 1 ) = s − 1 + ( 0 + s1 + ... + s 2 ( K − b −1) ) − 1 + s −1 + ( 0 + s 1 + ... + s 2 ( K − b − 1) + s 2 ( K − b − 1) + 1 ) = − 1 + 2 s − 1 + 2 ( s 2 + s 4 + ... + s 2 (K − b −1 ) ) + 2 ( s1 + s 3 + ... + t 2 ( K − b −1) + 1 ) − s 2 ( K − b − 1)+ 1 a+1 2( K − b − 1) + 1 − 1 b − a +1 + 0 + 0 = −1 + 2 + 2 ⋅ 2 b+2 b (b + 2 ) 2 ( b)( b − a + 1) + (( a + 1)[ 2( K − b − 1)] ) = −1 + b (b + 2 ) =
− b (b + 2 ) + 2 b 2 − 2ab + 2b + 2 ( a + 1)( K − b − 1) b (b + 2 )
=
− b 2 − 2b + 2b 2 − 2 ab + 2b + 2 ( a + 1)( K − b − 1) b (b + 2 )
b 2 − 2 ab + 2 ( a + 1)( K − b − 1) b ( b + 2) 2( a + 1)( K − b − 1) + b (b − 2 a ) = . b( b + 2) =
Untuk x = K , K + 1
•
K −1
K +1
i= −1
i =−1
f 2 ( x ) = ∑ s i = ∑ s i − s K − s K +1 = 1 − s K − s K +1 ( a + 1)( 2 b − K + 1) = 1− −0 b(b + 2) b (b + 2 ) − ( a + 1)( 2 b − K + 1) = b (b + 2 ) =
b 2 + 2b − 2 ab + aK − a − 2 b + K − 1 b (b + 2 )
b 2 − 2 ab + aK − a + K − 1 b (b + 2 ) b (b − 2 a ) + a ( K − 1 ) + ( K − 1 ) = b (b + 2 ) ( a + 1)( K − 1) + b ( b − 2 a ) = . b (b + 2 ) =
