PENENTUAN PELUANG TRANSISI t LANGKAH DAN UJI ORDE DARI SUATU RANTAI MARKOV Ō(r) Studi kasus: Barisan basa nukleotida spesies Homo Sapiens
Diajukan sebagai syarat mengikuti sidang Sarjana Matematika Program Studi Matematika Institut Teknologi Bandung
disusun oleh:
Mohamad Amru Reza 10103023
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG 2007
PENENTUAN PELUANG TRANSISI t LANGKAH DAN UJI ORDE DARI SUATU RANTAI MARKOV Ō(r) Studi kasus: Barisan basa nukleotida spesies Homo Sapiens
Diajukan sebagai syarat mengikuti sidang Sarjana Matematika Program Studi Matematika Institut Teknologi Bandung
disusun oleh: Mohamad Amru Reza 10103023
Bandung, Juni 2007 Telah diperiksa dan disetujui oleh
Dr. Udjianna S. Pasaribu Dosen Pembimbing
PROGRAM STUDI MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT TEKNOLOGI BANDUNG
i
ABSTRAK Proses stokastik Markov banyak digunakan dalam berbagai bidang baik industri maupun
penelitian
seperti
pemasaran,
asuransi,
prakiraan
cuaca,
dan
bioinformatika. Hal-hal matematis yang menarik untuk dipelajari antara lain adalah orde dan penentuan besarnya, kekonvergenan dan kestasioneran, serta taksiran matriks peluang transisi t langkah, Pt. Dalam tugas akhir ini ada dua hal yang dilakukan. Pertama, menemukan prosedur untuk menghitung Pt pada matriks berorde-r, Ō(r), r bulat dan r > 1. Prosedurnya adalah dengan mendefinisikan matriks peluang transisi satu langkah, P yang berukuran nr x n dengan n menyatakan banyaknya keadaan dan r besarnya orde. Kedua, mengembangkan uji khi kuadrat sebagai uji kesesuaian (goodness of fit) dalam menentukan besar orde suatu rantai Markov. Sebagai pendukung penemuan ini, diambil data nyata, yaitu barisan basa nukleotida spesies Homo Sapiens yang telah banyak diteliti oleh para ahli di bidang genetik.
Kata kunci: Rantai Markov, Orde Rantai Markov (Ō(r)), Matriks Transisi t Langkah, Uji Khi Kuadrat.
ii
ABSTRACT Markov stochastic process has been widely used in both industries and researches, such as marketing, insurance, weather forecast, and bioinformatics. Mathematical problems that interesting to be studied are order, determination of the size of the order; convergence and stationary, and estimation of t-step transition probability matrix, Pt. In this final project, there are two purposes. First, to find a procedure to calculate Pt for r-order Markov chain, Ō(r), r integer and r > 1. It is conducted by defining a one-step transition probability matrix P which size is nr x n where n is the number of states and r is the size of the order. Second, to improve the ChiSquare test as goodness of fit test in determining the order of a Markov chain. Homo Sapiens nucleotide sequence, which has been observed by genetic experts, was collected as real data to support this invention.
Key words: Markov Chain, Order of Markov Chain (Ō(r)), t-Step Transition Matrix, Chi-Square Test.
iii
PRAKATA Puji dan syukur penulis panjatkan kehadirat Allah SWT yang telah memberikan rahmat dan hidayah-Nya sehingga penulis dapat menyelesaikan tugas akhir ini tepat pada waktunya. Tugas akhir yang berjudul ”Penentuan Peluang Transisi t Langkah dan Uji Orde dari Suatu Rantai Markov Ō(r)” ini bertujuan untuk mempelajari rantai Markov Ō(r), yaitu dengan menemukan prosedur perhitungan matriks peluang transisi serta menurunkan statistik uji untuk menguji besarnya orde. Dengan demikian, penulis berharap hasil dari tugas akhir ini akan membawa masalah-masalah baru di bidang matematika dan statistika khususnya statistika inferensi, proses stokastik, dan pemodelan matematika sehingga akan muncul penelitian-penelitian baru yang lebih bermanfaat. Selain itu, tugas akhir ini juga disusun untuk memenuhi salah satu syarat dalam menyelesaikan pendidikan tahap sarjana Program Studi Matematika Institut Teknologi Bandung. Dalam penyusunan tugas akhir ini, penulis memperoleh banyak bantuan serta bimbingan dari berbagai pihak. Oleh karena itu, penulis menyampaikan terima kasih kepada: 1.
Dr. Udjianna S. Pasaribu, selaku dosen pembimbing yang telah memberikan banyak masukan dan komentar yang sangat berharga, serta atas kesediaan beliau dalam meluangkan waktu ditengah kesibukan yang padat selama penyusunan tugas akhir ini. Terima kasih atas segala nasihat dan kesempatan yang telah diberikan kepada penulis.
2.
Ir. Sri Purwanti M., M.Sc, dari STEI ITB yang pada mulanya menjadi dosen pembimbing kedua tapi berhubung waktu dan kesibukan lain yang mendesak sehingga tidak dapat menemani penulis hingga tugas akhir ini selesai. Penulis sangat berterima kasih atas segala masukan dan dukungan moral yang telah diberikan.
iv
3.
Dr. Dumaria R. Tampubolon yang telah berkenan dalam meluangkan waktu untuk menjadi dosen penguji dalam seminar I dan II. Terima kasih atas masukan yang telah diberikan sehingga tugas akhir ini menjadi lebih baik.
4.
Dr. Achmad Muchlis yang telah berkenan menjadi dosen penguji dalam seminar II. Terima kasih atas waktu dan saran-sarannya dalam memperbaiki tugas akhir ini.
5.
Dr. Khreshna I. Syuhada yang telah memberikan jurnal-jurnal dan paper yang sangat bermanfaat dalam proses penyusunan tugas akhir ini. Terima kasih atas semua bantuan, nasihat, dan masukan yang telah diberikan kepada penulis.
6.
Dr. Adi Pancoro dari SITH ITB yang telah memberikan dan merekomendasikan data basa nukleotida spesies Homo Sapiens sehingga penulis dapat menyelesaikan studi kasus dalam tugas akhir ini.
7.
Dr. Rinovia M. Simanjuntak selaku dosen wali yang telah membimbing penulis selama empat tahun menempuh perkuliahan di Program Studi Matematika ITB.
8.
Orang tua serta adik penulis tercinta yang selalu mendoakan penulis sehingga berhasil meraih cita-cita menjadi seorang sarjana matematika. Besar harapan penulis untuk dapat membahagiakan kalian semua.
9.
Teman bimbingan setia penulis, Anggun dan Lido serta Mas Haryono. Terima kasih atas segala bantuan yang diberikan sehingga penulis dapat menyelesaikan tugas akhir ini. Bagaimanapun kita memulai tugas akhir (maupun tesis) ini bersama, karenanya mari kita rampungkan bersama pula.
10.
Teman-teman yang bersedia berdiskusi mengenai tugas akhir ini, Madona atas penjelasannya mengenai teorema aljabar yang berhubungan dengan rantai Markov, Teh Rini atas masukannya dalam beberapa penulisan matematis, dan Teh Utri yang dengan sukarela selalu siap menjawab pertanyaan penulis.
11.
Kawan-kawan matematika 2003 khususnya iQs beserta Inon dan Cima yang telah memberikan masukan dalam penyusunan prakata ini; Ani, Cica,
v
dan Dita teman satu kelompok di kuliah selama 4 semester terakhir ini; Willy, Vonny, dan Cica serta Agus Purnomo yang telah memberi masukan dalam penerjemahan abstrak pada saat-saat terakhir; Hendrik, Erdi, dan Erma yang telah memberikan bantuan dalam pencetakan tugas akhir ini, Barick atas bantuannya dalam mencari jurnal dan paper, serta tidak lupa Angga Dinan atas warisan buku-bukunya yang sangat membantu penulis dalam setiap perkuliahan. 12.
Ibu Diah atas segala bantuan yang tidak akan pernah penulis lupakan. Terima kasih atas segala nasihat dan dukungan yang telah diberikan.
Penulis menyadari bahwa masih terdapat kekurangan dalam tugas akhir ini. Oleh karena itu, penulis sangat mengharapkan kritik dan saran dalam penyempurnaan tulisan ini di masa yang akan datang. Semoga tulisan ini dapat bermanfaat bagi rekan sejawat maupun para pembaca.
Bandung, Juni 2007
Mohamad Amru Reza
vi
DAFTAR ISI Lembar Pengesahan ................................................................................................i Abstrak ....................................................................................................................ii Abstract...................................................................................................................iii Prakata.....................................................................................................................iv Daftar Isi................................................................................................................vii BAB I: PENDAHULUAN 1.1 Latar Belakang .................................................................................................. 1 1.2 Rumusan Masalah .............................................................................................3 1.3 Tujuan ...............................................................................................................3 1.4 Manfaat ............................................................................................................. 4 1.5 Sumber Data dan Teknik Penelitian..................................................................4 1.6 Sistematika Penulisan .......................................................................................4 BAB II: TEORI DASAR 2.1 Proses Stokastik Rantai Markov ......................................................................6 2.2 Sifat-Sifat Pada Rantai Markov ........................................................................ 9 2.3 Orde Rantai Markov Ō(r) dan Sifat-Sifatnya...................................................20 BAB III: STATISTIK INFERENSI PADA RANTAI MARKOV 3.1 Pendahuluan.....................................................................................................28 3.2 Estimasi Kemungkinan Maksimum Untuk P...................................................29 3.3 Studi Deskriptif Ō(r)........................................................................................38 3.4 Uji Kesesuaian Suatu Rantai Markov..............................................................40 BAB IV: STUDI KASUS 4.1 Pendahuluan.....................................................................................................47 4.2 Pengolahan dan Analisis Data..........................................................................47
vii
BAB V: KESIMPULAN DAN SARAN 4.1 Kesimpulan.......................................................................................................51 4.2 Saran.................................................................................................................52 Daftar Pustaka........................................................................................................53 Lampiran................................................................................................................54
viii
