Matematika2

Teorema mengenai Limiting Probability dan Irreducible

Teorema mengenai Limiting ProbabilityDefinisi: πj(n) adalah probabilitas suatu rantai Markov {Xn} berada dalam status j pada step ke n. Maka, πj(n) = P[Xn = j]. Distribusi awal (intial) dari masing-masing status 0, 1, 2, .. dinyatakan sebagaiπj(0) = P[X0 = j], untuk j = 0, 1, 2, …. Suatu rantai Markov memiliki distribusi probabilitas stasionerπ = (π0, π1, π2, …, πn) apabila terpenuhi persamaanπ =πP asalkan setiap πi ≥ 0 dan ∑i πi = 1. Jika suatu rantai Markov homogen waktu (stasioner dari waktu ke aktu) yang irreducible, aperiodic, maka limit probabilitas (n) π j = limπ j , untuk j = 0, 1, … n→∞ selalu ada dan independen dari distribusi probabilitas status awal π(0) = (0)(0) (π0, π1,π2(0), ….). Jika seluruh status tidak positive recurrent (jadi seluruhnya recurrent null atau seluruhnya transient), maka πj = 0 untuk semua j dan tidak terdapat distribusi probabilitas stasioner. Teorema mengenai Irreducible Jika {Xn} suatu rantai Markov, maka tepat salah satu kondisi berikut ini terjadi 1) Semua status adalah positive recurrent 2) Semua status recurrent null 3) Semua status transient

Teorema mengenai Limiting Probability dan Irreducible

Teorema mengenai Limiting Probability Definisi: π j ( n ) adalah probabilitas suatu rantai Markov { X n } berad a dalam status j pada ste...

Baca selengkapnya »

Teorema mengenai Relasi Ekovalensi

Teorema mengenai Relasi Ekovalensi

(a) Relasi i ↔j merupakan relasi ekivalen, yaitu untuk setiap status i, berlaku i ↔ i jika i ↔ j , maka juga j ↔ i jika i ↔j dan j ↔k ma...

Baca selengkapnya »

Terminologi

Reachable State status j reachable dari status i apabila dalam rantai dapat terjadi transisi dari status i ke status j melalui sejumlah transisi berhingga; Terdapat n, 0 ≤ n < ∞, sehingga Pnij > 0 Irreducible Chain jika dalam suatu rantai Markov setiap status reachable dari setiap status lainnya, rantai tersebut adalah irreducible. Periodic State suatu status i disebut periodic dengan perioda d > 1, jika pnii > 0, hanya untuk n = d, 2d, 3d, …; sebaliknya jika pnii > 0 untuk n = 1, 2, 3, … maka status tersebut disebut aperiodic. Probability Of First Return Probabilitas kembali pertama kalinya ke status i terjadi dalam n transisi setelah meninggalkan i. fi(n) = P[Xn = i, Xk ≠ i untuk k = 1, 2, …, n-1 | X0 = i] (note: fi(0) didefinisikan = 1 untuk semua i). Probability of Ever Return probabilitas akan kembalinya ke status i setelah sebelumnya meninggalkan i. (n) fi = ∑∞ fi n=1 1 Berdasarkan Pij = P1 ij serta P0 ij = 1 untuk i= j dan P0 ij = 0 untuk i ≠ j (yaitu Fungsi Delta Kronecker). Transient State Suatu status disebut transient jika probabilitas fi <>i melalui sejumlah transisi terdapat kemungkinan tidak dapat kembali ke i. Recurrent State Suatu status disebut recurrent jika probabilitas fi = 1; yaitu bahwa setelah dari I melalui sejumlah transisi selalu ada kemungkinan untuk kembali ke i. Mean Recurrence Time of State Untuk suatu status recurrent, jumlah step rata-rata untuk kembali ke status i ∞ (n) mi =∑nfi n=1 Null Recurrenct State Suatu recurrent state disebut reccurent null jika mi = ∞ Positive Recurrent State Suatu recurrent state disebut positive reccurent atau recurrent nonnull jika mi < ∞ Communicate State Dua status, i dan j, dikatakan berkomunikasi jika i reachable dari j dan juga j reachable dari i; ditulis dengan notasi i ↔ j . Ergodic Rantai Markov disebut ergodic jika irreducible, aperiodic, dan seluruh status positive recurrent.

Terminologi

Reachable State s tatus j reachable dari status i apabila dalam rantai dapat terjadi transisi dari status i ke status j melalui sejumlah ...

Baca selengkapnya »

Transisi Multistep (n-langkah)

Berdasarkan probabilitas satu langkah di atas, maka dapat dibentuk probabilitas n-langkah (n-step) yang menyatakan probabilitas transisi dari status i ke status j setelah melalui n langkah transisi. Pnij = P[Xn = j | X0 = i], dengan n, i, j = 0, 1, 2, … Untuk rantai Markov dengan probabilitas stasioner maka Pnij = P[Xn+m = j | Xm = i], dengan n, m ≥ 0 Sehingga diperoleh1 ∞ n+m nm Pij =∑ Pik Pkj untuk semua n, m, i, j ≥ 0 k=0 Atau secara khusus, ∞ nn−1 Pij =∑ Pik Pkj k=0 Dalam notasi matriks, P(n) adalah matriks transisi untuk multistep, maka dapat diperoleh persamaan dalam matriks P sbb P(n) = P(n-1)P= P(n-2)PP =… = Pn yaitu bahwa P(n) adalah pangkat n dari matriks P.

Transisi Multistep (n-langkah)

Berdasarkan probabilitas satu langkah di atas, maka dapat dibentuk probabilitas n-langkah (n-step) yang menyatakan probabilitas transisi da...

Baca selengkapnya »

Proses Rantai Markov

Proses stokastik {X(t), t ∈ T} merupakan suatu Proses Markov jika untuk <div> </div> setiap n+1, dengan indeks t1< t2 < …< tn < tn+1 dan harga-harga status {x1, x2, <div style="text-align: justify;"> </div> …, xn+1}, terjadi persamaan: P[X (tn+1) = xn+1| X (t1) = x1, X (t2) = x2 ,..., X (tn ) = xn ] = <div style="text-align: justify;"> </div> P[X (t ) = x | X (t ) = x ]<div style="text-align: justify;"> </div> n+1 n+1 nn <div style="text-align: justify;"> </div> Persamaan tsb. secara narasi dapat dikatakan proses selanjutnya hanya bergantung pada status saat ini, bukan pada “sejarah” dari proses tersebut. Dalam proses Markov status-status proses yang terjadi selama ini dicerminkan oleh status saat ini. <div style="text-align: justify;"> </div> Sebagaimana terminologi di awal, suatu proses Markov disebut Rantai Markov jika ruang status diskret. Untuk waktu diskret, rantai Markov dapat digambarkan sebagai diagram transisi status.

Proses Rantai Markov

Proses stokastik { X ( t ), t ∈ T } merupakan suatu Proses Markov jika untuk setiap n +1, dengan indeks t 1 t 2 t n t n +1 dan harga-harg...

Baca selengkapnya »

Interpolation Search

Interpolation Search

Teknik ini dilakukan pada data yang sudah terurut berdasarkan kunci tertentu Teknik searching ini dilakukan dengan perkiraan letak data. Con...

Baca selengkapnya »

Binary Search

Binary Search

Data yang ada harus diurutkan terlebih dahulu berdasarkan suatu urutan tertentu yang dijadikan kunci pencarian. Adalah teknik pencarian data...

Baca selengkapnya »

Sequential Search

Sequential Search

Adalah suatu teknik pencarian data dalam array ( 1 dimensi ) yang akan menelusuri semua elemen-elemen array dari awal sampai akhir, dimana d...

Baca selengkapnya »

Array

<ul style="text-align: justify;"><li>Array adalah suatu tipe data terstuktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya bisa statis ataupun dinamis dan diberi suatu nama tertentu.</li><li>Elemen-elemen array tersusun secara berderet dan sekuensial di dalam memori sehingga memiliki alamat yang besebelahan/berdampingan.</li><li>Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-dimensi.</li><li>Elemen-elemen array bertipe data sama tapi bisa bernilai sama atau berbeda-beda.</li><li>Elemen-elemen array dapat diakses oleh program menggunakan suatu indeks tertentu</li><li>Pengaksesan elemen array dapat dilakukan berurutan atau random berdasarkan indeks tertentu secara langsung.</li><li>Pengisian dan pengambilan nilai pada indeks tertentu dapat dilakukan dengan mengeset nilai atau menampilkan nilai pada indeks yang dimaksud.</li><li>Dalam C, tidak terdapat error handling terhadap batasan nilai indeks, apakah indeks tersebut berada di dalam indeks array yang sudah didefinisikan atau belum. Hal ini merupakan tanggung jawab programmer. Sehingga jika programmer mengakses indeks yang salah, maka nilai yang dihasilkan akan berbeda atau rusak karena mengakses alamat memori yang tidak sesuai.</li></ul>

Array

Array adalah suatu tipe data terstuktur yang berupa sejumlah data sejenis (bertipe data sama) yang jumlahnya bisa statis ataupun dinamis dan...

Baca selengkapnya »

Matematika2

Teorema mengenai Limiting Probability dan Irreducible

Teorema mengenai Relasi Ekovalensi

Terminologi

Transisi Multistep (n-langkah)

Proses Rantai Markov

Interpolation Search

Binary Search

Sequential Search

Array

Entri Populer

Arsip Blog

Komentar