GRAF ALIRAN SINYAL PADA SISTEM PERSAMAAN CHAPMAN- KOLMOGOROV Puji Nugraheni Jurusan Pendidikan Matematika FKIP Universitas Muhammadiyah Purworejo Jalan KH. A. Dahlan 3 Purworejo e-mail:
[email protected]
Abstrak Tujuan dari penulisan ini adalah mengetahui konstruksi bentuk graf aliran sinyal pada sistem persamaan Chapman-Kolmogorov. Persamaan ChapmanKolmogorov dapat dikonstruksikan ke dalam bentuk graf aliran sinyal. Cara mengkonstruksi graf aliran sinyal yang diperoleh dari sistem persamaan Chapman Kolmogorov dengan metode Langsung adalah menyatakan sistem persamaan Chapman Kolmogorov ke dalam bentuk persamaan matriks. Kata Kunci: persamaan Chapman Kolmogorov, graf aliran sinyal peluangnya memenuhi sifat Markov
Pendahuluan Salah satu contoh bentuk proses stokastik
adalah
Rantai
Markov.
berikut ini.
P( X n+1 = xn +1 X 0 = x0 , X 1 = x1 ,..., X n = xn )
yang
= P( X n +1 = xn+1 X n = xn ) untuk n = 0, 1, 2, ... dan untuk setiap
kemunculannya berdasarkan peluang
kedudukan x0 , x1 ,..., xn , xn+1 . Ini me-
tertentu yang hanya tergantung pada
nunjukkan peluang kedudukan pada
kedudukan
saat n + 1 bergantung pada saat n .
Rantai Markov memuat rangkaian kejadian
atau
kedudukan
sebelumnya.
Rantai
Markov dibagi menjadi dua macam yaitu Rantai Markov waktu diskrit dan Rantai Markov waktu kontinu.
Pada
rantai
terdapat
kedudukan awal, maka rantai Markov dengan X n , n ≥ 0 dilengkapi dengan
Dalam makalah ini yang akan dibahas adalah Rantai Markov waktu diskrit.
Markov
distribusi
awal
π 0 ( x) = P{X 0 = x}
Rantai Markov waktu diskrit adalah
untuk setiap x ∈ S . Distribusi awal
proses
π 0 ( x) menyatakan peluang bahwa
stokastik
yang
distribusi
pada saat proses dimulai, rantai 8
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
Markov
pada
x.
kedudukan
Distribusi awal π 0 ( x) dari rantai Markov dengan ruang kedudukan
S = {0, 1, 2, ..., n} dapat dipandang sebagai vektor baris berukuran n + 1 ,
distribusi awal π 0 , maka:
P( X n = y ) = ∑ π 0 ( x) P n ( x, y ), y ∈ S ...(2) x
Dari persamaan (1) dan (2) maka untuk n → ∞ didapatkan:
w j = lim P( X n = y ) n →∞
yaitu:
π 0 ( x) = (π 0 (0), π 0 (1), π 0 (2),...,π 0 (n) ) . Misalkan Markov
Xn,n ≥ 0 yang
= lim ∑ π 0 ( x) P n ( x, y ) n →∞
= ∑ π 0 ( x) limP n ( x, y )
adalah rantai
mempunyai
= ∑ π 0 ( x)π ( y ) = π ( y )∑ π 0 ( x) x
kedudukan S dan fungsi transisi P .
= π ( y ) = lim P ( x, y )
dan
∑ π ( x)P( x, y) = π ( y), y ∈ S
jika
maka π
Jika
disebut distribusi stasioner. Misalkan
π
n →∞
n →∞
maka didapatkan w j = ∑ wi P( x, y ) , i
j = 0.1,2,K, n .
untuk
x
stasioner
n →∞
lim P n ( x, y ) = w j = lim P n −1 ( x, y ) ,
⎛ ⎞ ⎜ ∑ π ( x) = 1⎟ ⎝ x∈S ⎠
distribusi
ada
dan
lim P n ( x, y ) = π ( y ) , y ∈ S ........... (1) n→∞
w j = ∑ wi P( x, y )
distribusi
dari
Xn
Persamaan
dapat
diubah
matriks
menjadi
i
kedalam
w = wP .
maka tanpa memperhatikan distribusi awalnya,
x
n
Jika π ( x), x ∈ S , adalah bilangan non
satu
n →∞
x
ruang
negatif yang jumlahnya sama dengan
x
bentuk
Selanjutnya,
w = wP
disebut dengan persamaan Chapman Kolmogorov.
mendekati π untuk n → ∞ . Untuk kasus
seperti
ini,
π
dikatakan
distribusi dengan kedudukan tetap
Pembahasan
Konstruksi bentuk graf Aliran
(steady state distribution).
Sinyal pada persamaan Chapman-
Jika π adalah distribusi stasioner dan
Kolmogorov mengacu pada kon-
jika persamaan (1) berlaku, dengan
struksi bentuk graf Aliran Sinyal pada
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
9
w = (w1
sistem linear. Berikut ini uraian dalam
dengan
mengkonstruksi graf Aliran Sinyal
⎡ p11 ⎢p ⎢ 21 dan P = ⎢ p31 ⎢ ⎢ M ⎢⎣ p n1
pada
persamaan
Kolmogorov. persamaan dari
Chapman
Diberikan Chapman
suatu
rantai
sistem
Kolmogorov Markov
yang
w3 K wn )
w2
p12 p 22 p 32
p13 K p 23 K p 33 K
M pn2
M p n3 K
p1n ⎤ p 2 n ⎥⎥ p3n ⎥ ⎥ M ⎥ p nn ⎥⎦
dinyatakan dalam persamaan matriks Persamaan
sebagai berikut.
w = wP
(w1
w2
w3
dapat
dijabarkan
sebagai berikut.
..................... (3) ⎡ p11 ⎢p ⎢ 21 K wn ) = ⎢ p31 ⎢ ⎢ M ⎢⎣ p n1
(3)
p12 p 22 p32
p13 K p 23 K p33 K
M pn 2
M pn3 K
p1n ⎤ p 2 n ⎥⎥ p3n ⎥ (w1 ⎥ M ⎥ p nn ⎥⎦
w2
w3 K wn )
(4) Dengan demikian, persamaan (4)
Persamaan (6) adalah sistem persamaan dengan n persamaan dalam
dapat dinyatakan sebagai berikut.
n bilangan tak diketahui. Oleh karena
w1 = p11 w1 + p12 w2 + p13 w3 + K + p1n wn itu, persamaan (6) mempunyai w2 = p 21 w1 + p 22 w2 + p 23 w3 + K + p 2 n wn pemecahan lebih dari satu. w3 = p31 w1 + p32 w2 + p33 w3 + K + p3n wn Selanjutnya, karena merupakan rantai M M M M M wn = p n1 w1 + p n 2 w2 + p n 3 w3 + K + p nn wn Markov maka pemecahan dari
(5)
persamaan (6) harus memenuhi:
Bentuk persamaan (5) adalah
w1 + w2 + w3 + L + wn = 1 ........ (7)
n
Menurut aturan Cramer, jika AX=B
persamaan sehingga dapat ditulis
adalah sistem persamaan yang terdiri
menjadi sebagai berikut.
dari n persamaan linear dalam n
w( I − P) = 0 ............................ (6)
bilangan yang tak diketahui sehingga
sistem
10
persamaan
dengan
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
det( A) ≠ 0 , maka sistem persamaan
didapatkan
tersebut mempunyai pemecahan
berikut.
det( A1 ) x1 = , det( A)
w( I − P ) ∗j = V j
x1 =
det( A2 ) x1 = ,…, det( A)
persamaan
sebagai
..................... (8)
di mana ( I − P ) ∗j adalah matriks yang
det( An ) det( A)
didapatkan
dari
I −P
matriks
dengan mengganti entri-entri dari di mana A j adalah matriks yang didapatkan
dengan
suatu kolom ke-j dengan 1 dan V j
menggantikan
adalah vektor baris dengan semua
entri-entri dalam kolom ke-j dari A
entrinya nol, kecuali pada entri ke-
dengan entri-entri dalam matriks B.
jnya adalah 1. Jadi,
Jadi, dari persamaan (6) dan (7) maka w = (w1
w3 K wn )( I − P) ∗j
w2
⎛ 1 − p11 ⎜ ⎜ − p 21 ⎜ M ⎜ ⎜ − p( j −1)1 =⎜ ⎜ − p j1 ⎜ − p( j +1)1 ⎜ ⎜ M ⎜ −p n1 ⎝
− p12 1 − p 22
L L
− p1 j −1 − p 2 j −1
M
M
M − pn 2
M
1 1 M 1
− p1 j +1 − p 2 j +1
− p1n ⎞ ⎟ − p2n ⎟ ⎟ M ⎟ − p ( j −1) n ⎟ − p jn ⎟⎟ − p j +1n ⎟ ⎟ M ⎟ 1 − p nn ⎟⎠
L L
M
− p( j −1) 2 L 1 − p j −1 j −1 − p j −1 j +1 L − p j 2 L − p j ( j −1) 1 − p j ( j +1) L − p( j +1) 2 L − p j +1 j −1 1 1 − p j +1 j +1 L L
− p n ( j −1)
M 1
M
− p n ( j +1)
L
Bentuk ( I − P ) ∗j + I pada persamaan (9) dapat dijabarkan sebagai berikut. ( I − P ) ∗j + I = ⎛ 1 − p11 ⎜ ⎜ − p 21 ⎜ M ⎜ ⎜ − p ( j −1)1 ⎜ −p j1 ⎜ ⎜ − p ( j +1)1 ⎜ ⎜ M ⎜ −p n1 ⎝
− p12 1 − p 22 M − p ( j −1) 2 − p j2 − p ( j +1) 2 M − pn2
L L
− p1 j −1 − p 2 j −1
1 1 M 1 1
− p1 j +1 − p 2 j +1
M M − p j −1 j +1 L 1 − p j −1 j −1 − p j ( j +1) L − p j ( j −1) L − p j +1 j −1 1 1 − p j +1 j +1 M M M L − p n ( j −1) 1 − p n ( j +1)
L L L L L L
− p1n ⎞ ⎛ 1 ⎟ ⎜ − p2n ⎟ ⎜ 0 ⎟ ⎜0 M ⎟ ⎜ − p ( j −1) n ⎟ ⎜ 0 + − p jn ⎟⎟ ⎜ 0 ⎜ − p j +1n ⎟ ⎜ 0 ⎟ ⎜ M ⎟ ⎜M 1 − p nn ⎟⎠ ⎜⎝ 0
0⎞ ⎟ 0⎟ 0⎟ ⎟ 0⎟ 0 ⎟⎟ 0 0 0 0 1 K 0⎟ ⎟ M⎟ M M M M M 0 0 0 0 0 K 1 ⎟⎠
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
0 0 0 0 0
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
K L K K K
11
⎛ 2 − p11 ⎜ ⎜ − p 21 ⎜ M ⎜ ⎜ − p( j −1)1 =⎜ ⎜ − p j1 ⎜ − p ( j +1)1 ⎜ ⎜ M ⎜ −p n1 ⎝
− p12 2 − p 22 M
L L
− p1 j −1 − p 2 j −1 M
− p ( j −1) 2 − p j2 − p ( j +1) 2 M − pn2
L 2 − p j −1 j −1 L − p j ( j −1) L − p j +1 j −1 M L − p n ( j −1)
− p1 j +1 − p 2 j +1
1 1 M
L L
M
− p j −1 j +1 2 − p j ( j +1) 1 2 − p j +1 j +1 M M 1 − p n ( j +1)
1
L L L L
− p1n ⎞ ⎟ − p2n ⎟ ⎟ M ⎟ − p ( j −1) n ⎟ ⎟ − p jn ⎟ − p j +1n ⎟ ⎟ M ⎟ 2 − p nn ⎟⎠
atau dapat diubah kedalam bentuk: ( 2 I − P ) ∗j ......................................... (10) Akibat persamaan (10), maka persamaan (9) menjadi sebagai berikut.
[
wT = − V j
]
⎡v ⎤ (2 I − P) ∗j ) ⎢ 0T ⎥ ⎣w ⎦
........................ (11)
Persamaan (11) dapat dijabarkan sebagai berikut. ⎡ w1 ⎤ ⎡ 0 ⎢w ⎥ ⎢0 ⎢ 2 ⎥ ⎢ ⎢ M ⎥ ⎢M ⎢ ⎥ ⎢ ⎢ w j −1 ⎥ = ⎢ 0 ⎢ w j ⎥ ⎢− 1 ⎢ ⎥ ⎢ ⎢ w j +1 ⎥ ⎢ 0 ⎢ M ⎥ ⎢M ⎢ ⎥ ⎢ ⎢⎣ wn ⎥⎦ ⎢⎣ 0
⎡ 2 − p11 ⎢ −p 21 ⎢ ⎢ M ⎢ ⎢ − p ( j −1)1 ⎢ − p j1 ⎢ ⎢ − p ( j +1)1 ⎢ M ⎢ ⎢⎣ − p n1
− p12 2 − p 22 M
L L
− p ( j −1) 2 − p j2 − p ( j +1) 2 M
L 2 − p ( j −1)( j −1) L − p j ( j −1) L − p ( j +1)( j −1) M L − p n ( j −1)
− pn2
− p1( j −1) − p 2 ( j −1) M
1 1 M
− p1 j +1) − p 2 ( j +1) M
1 − p ( j −1)( j +1) 2 − p j ( j +1) 1 2 − p ( j +1)( j +1) M M 1
− p n ( j +1)
L L L L L L
⎡ v0 ⎤ ⎤⎤ ⎢ ⎥ ⎥ ⎥ ⎢ w1 ⎥ ⎥⎥ ⎢ w ⎥ ⎥⎥ ⎢ 2 ⎥ ⎥⎥ M ⎥ − p ( j −1) n ⎥ ⎥ ⎢ ⎢w ⎥ − p jn ⎥ ⎥ ⎢ j −1 ⎥ ⎥⎥ s − p ( j +1) n ⎥ ⎥ ⎢ j ⎥ ⎥ ⎢ ⎥ ⎥ ⎢ w j +1 ⎥ M ⎥⎥ ⎢ M ⎥ 2 − p nn ⎥⎦ ⎥⎦ ⎢ ⎥ ⎣ wn ⎦ − p1n − p 2n M
sehingga diperoleh: w1 = (2 − p11 ) w1 − p12 w2 − K − p1( j −1) w j −1 + w j − p1( j +1) w j +1 − K − p1n wn w2 = − p 21 w1 + (2 − p 22 ) w2 − K − p 2 ( j −1) w j −1 + w j − p 2 ( j +1) w j +1 − K − p 2 n wn
M
M
M
M
M
M
M
w j −1 = − p ( j −1)1 w1 − p ( j −1) 2 w2 − K + (2 − p ( j −1)( j −1) ) w j −1 + w j − p ( j −1)( j +1) w j +1 − K − p ( j −1) n wn
w j = −v0 − p j1 w1 − p j 2 w2 − K p j ( j −1) w j −1 + 2w j − p j ( j +1) w j +1 − K − p jn wn w j +1 = − p ( j +1) w1 − p ( j +1) 2 w2 − K − p ( j +1)( j −1) w j −1 + w j + ( 2 − p ( j +1)( j +1) ) w j +1 − K − p ( j +1) n wn
12
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
M
M
M
M
M
M
wn = − p n1 w1 − p n 2 w2 − K − p n ( j −1) w j −1 + w j − p n ( j +1) w j +1 − K + (2 − p nn ) wn (12) Maka
sistem
persamaan
Chapman Kolmogorov dapat dinyatakan dalam bentuk graf Aliran Sinyal untuk peubah w1 ,w 2 , w3 ,..., wn sebagai berikut. Gambar 3. Graf Aliran Sinyal untuk peubah w j −1
Gambar 1. Graf Aliran Sinyal untuk peubah w1
Gambar 2. Graf Aliran Sinyal untuk peubah w2
Gambar 4. Graf Aliran Sinyal untuk peubah w j
Gambar 5. Graf Aliran Sinyal untuk peubah w j +1
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
13
w1 , w2 ,K, w j −1 , w j , w j +1 ,K, wn yaitu busur ( w j , w1 ), ( w j , w2 ),K, ( w j , w j −1 ), ( w j , w j ), ( w j , w j +1 ),K, ( w j , wn ) Gambar 6. Graf Aliran Sinyal untuk peubah wn Berdasarkan Sinyal
gambar
untuk
graf
setiap
seperti pada gambar berikut.
Aliran peubah
w1 , w2 ,K, w j −1 , w j , w j +1 ,K, wn , maka dihasilkan pola graf Aliran Sinyal untuk peubah w1 , w2 ,K, w j −1 , w j , w j +1 ,K, wn sebagai berikut. 1. Terdapat 1 busur yang menghubungkan
simpul
simpul peubah w j
v0
dengan
yaitu busur
Gambar 8. Busur ( w j , w1 ), ( w j , w2 ),K, ( w j , w j −1 ), ( w j , w j ), ( w j , w j +1 ),K, ( w j , wn ) Ilustrasi pada gambar 8. dapat dinyatakan secara umum dalam
(v0 , w j ) dengan bobot -1 yang
bentuk sebagai berikut.
ditunjukkan sebagai berikut.
Gambar 9. Busur ( w j , wi )
Gambar 7. Busur (v0 , w j ) dengan bobot -1 w j = peubah ke-j, untuk j = 1,2,K, n 2. Terdapat n busur yang menghubungkan simpul peubah dengan
14
simpul
wj
w j = peubah ke-j, untuk j = 1,2,K, n
wi = peubah ke-i, untuk j = 1,2,K, n 3. Terdapat n − 1 busur yang menghubungkan
simpul
peubah
peubah
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
w1 , w2 ,K, w j −1 , w j +1 ,K, wn dengan
− p ji = bobot pada busur ( w j , wi )
simpul peubah w j
yaitu busur
untuk i = 1,2,K, j − 1, j + 1,K, n
( w1 , w j ), ( w2 , w j ),K,
(w j −1 , w j ),
( w j +1 , w j ),K, ( wn , w j ) seperti pada gambar berikut.
4. Terdapat sikel yang terdiri atas 2 simpul yaitu simpul peubah wk dan wi yang saling terhubung satu sama lain dengan setiap simpulnya terdapat busur gelang seperti yang ditunjukkan pada gambar berikut.
Gambar 10. Busur ( w1 , w j ), ( w2 , w j ),K, ( w j −1 , w j ), ( w j +1 , w j ), K , ( w j , wn )
Gambar 12. Ilustrasi sikel peubah wk dan wi Penjabaran lebih lanjut pada sikel yang memuat simpul wk dan wi
Ilustrasi pada gambar 10. dapat
berdasarkan gambar 12 ditunjukkan
dinyatakan secara umum sebagai
sebagai berikut.
berikut.
untuk k = 1
Gambar 11. Busur ( wi , w j ) w j = peubah ke-j, untuk j = 1,2,K, n
dengan i = 2, K, j − 1, j + 1,K, n
wi =peubah ke-i, untuk i = 1,2,K,
untuk k = 2
j − 1, j + 1,K, n
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
15
Daftar Pustaka
Chatrand, G.1985. Introduction Graph Theory.New York: Dover Publication, Inc dengan i = 3,K, j − 1, j + 1,K, n untuk k = j − 1
Chen, Wai Kai.1976.Applied Graph Theory Graphs and Electrical Networks.New York: NorthHolland Publishing Company. Harary, F.1969. Graph Theory. Massachussets: Addison – Wesley Publishing Company Inc. Hoel, Paul G., Port, Sidney C. & Stone,Charles J.1972. Introduction to Stochastic Processes. Boston: Houghton Mifflin Company.
dengan i = j + 2,K, n untuk k = n − 1
Mardiyono, S.1996. Matematika Diskret. Yogyakarta: FMIPA IKIP Yogyakarta
dengan i = n Gambar 13. Ilustrasi penjabaran sikel dengan 2 simpul wk dan wi Penutup
Berdasarkan pola graf Aliran Sinyal untuk peubah pada sistem linear maka dihasilkan konstruksi
Narsingh, Deo.1997. Graph Theory with Applications to Enginering and Computer.New Delhi: Prentice Hall of India. Sutarno, Heri., Priatna, Nanang. & Nurjanah.2003. Matematika Diskrit. Bandung: UPI Press. Wilson, Robin J & Beineke, Lowell W.1979. Application of Graph Theory. London: Academic Press.
keseluruhan graf Aliran Sinyal pada sistem
persamaan
Chapman
Kolmogorov. 16
Puji Nugraheni: Graf Aliran Sinyal pada Persamaan Chapman-Kolmogorov
