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 Chi-

Square 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