Nilai Worm dan Apple yang Diharapkan

8

Sebuah apel terletak di titik dari pentagon , dan cacing terletak dua simpul jauh, di . Setiap hari cacing merangkak dengan probabilitas yang sama dengan salah satu dari dua simpul yang berdekatan. Jadi setelah satu hari cacing berada di vertex atau , masing-masing dengan probabilitas . Setelah dua hari, worm mungkin kembali ke lagi, karena tidak memiliki memori dari posisi sebelumnya. Ketika mencapai titik , ia berhenti untuk makan.A B C D E C B D 1 / 2 C AAABCDECBD1/2CA

(a) Apa arti dari jumlah hari sampai makan malam?

(B) Misalkan p menjadi probabilitas bahwa jumlah hari adalah atau lebih. Apa yang dikatakan Markov tentang Ketimpangan tentang ?p100p

Untuk (a), misalkan adalah variabel acak yang ditentukan oleh jumlah hari sampai makan malam. Jadi P (X = 0) = 0 \\ P (X = 1) = 0 \\ P (X = 2) = \ frac {1} {\ binom {5} {2}} \\ \ vdotsX

P(X=0)=0P(X=1)=0P(X=2)=1(52)

Apa yang akan menjadi distribusi umum?

Untuk (b), jika kita tahu (a), maka kita tahu bahwa

P(X100)E(X)100
probguy3434
sumber
2
Bisakah Anda menjelaskan set persamaan pertama Anda? Mereka tampaknya tidak memperhitungkan kemungkinan cacing berbalik arah, juga tidak tampak benar. Lagi pula, jauh lebih kecil dari peluang jalur yang memiliki probabilitas Perhatikan bahwa inti dari pertanyaan ini adalah bahwa mungkin lebih sulit untuk mendapatkan distribusi penuh daripada menghitung ekspektasinya; dan Ketidaksetaraan Markov memungkinkan Anda menyimpulkan informasi yang berguna dari harapan saja. ABC(1/2)(1/2)=1/4.1/(52)=1/10ABC(1/2)(1/2)=1/4.
whuber

Jawaban:

6

Dalam jawaban yang sangat baik dari Glen_b , ia menunjukkan bahwa Anda dapat menghitung nilai yang diharapkan secara analitis menggunakan sistem persamaan linear sederhana. Dengan mengikuti metode analitik ini, Anda dapat menentukan bahwa jumlah gerakan yang diharapkan ke apel adalah enam. Jawaban sempurna lainnya oleh whuber menunjukkan bagaimana memperoleh fungsi massa probabilitas untuk proses setelah sejumlah gerakan tertentu, dan metode ini juga dapat digunakan untuk mendapatkan solusi analitik untuk nilai yang diharapkan. Jika Anda ingin melihat beberapa wawasan lebih lanjut tentang masalah ini, Anda harus membaca beberapa makalah tentang jalan acak melingkar (lihat misalnya, Stephens 1963 )

Untuk memberikan pandangan alternatif tentang masalah, saya akan menunjukkan kepada Anda bagaimana Anda bisa mendapatkan hasil yang sama menggunakan metode brute force dengan hanya menghitung rantai Markov menggunakan komputasi statistik. Metode ini lebih rendah daripada pemeriksaan analitis dalam banyak hal, tetapi memiliki keunggulan yang memungkinkan Anda untuk menangani masalah tanpa memerlukan wawasan matematika utama.


Metode komputasi brute force: Mengambil status dalam urutan , transisi rantai Markov Anda sesuai dengan matriks transisi berikut:A,B,C,D,E

P=[100001201200012012000120121200120]

Keadaan pertama adalah keadaan menyerap mana cacing berada di apel. Biarkan menjadi jumlah bergerak sampai cacing sampai ke apel dari negara . Maka untuk semua probabilitas bahwa worm ada di apel setelah jumlah gerakan ini adalah dan jumlah gerakan yang diharapkan untuk mendapatkan apel dari kondisi ini adalah:ATCCnNP(TCn)={Pn}C,A

E(TC)=n=0P(TC>n)=n=0(1{Pn}C,A).

Istilah dalam jumlah berkurang secara eksponensial untuk besar sehingga kita dapat menghitung nilai yang diharapkan untuk tingkat akurasi yang diinginkan dengan memotong jumlah pada jumlah istilah yang terbatas. (Peluruhan eksponensial dari ketentuan memastikan bahwa kami dapat membatasi ukuran ketentuan yang dihapus agar berada di bawah level yang diinginkan.) Dalam praktiknya, mudah untuk mengambil sejumlah besar istilah hingga ukuran istilah yang tersisa sangat kecil.n


Memprogram ini dalam R: Anda dapat memprogram ini sebagai fungsi dalam Rmenggunakan kode di bawah ini. Kode ini telah di-vektor-kan untuk menghasilkan array kekuatan matriks transisi untuk urutan gerakan yang terbatas. Kami juga menghasilkan sebidang probabilitas bahwa apel belum tercapai, menunjukkan bahwa ini menurun secara eksponensial.

#Create function to give n-step transition matrix for n = 1,...,N
#N is the last value of n
PROB <- function(N) { P <- matrix(c(1, 0, 0, 0, 0, 
                                    1/2, 0, 1/2, 0, 0, 
                                    0, 1/2, 0, 1/2, 0,
                                    0, 0, 1/2, 0, 1/2,
                                    1/2, 0, 0, 1/2, 0),
                                  nrow = 5, ncol = 5, 
                                  byrow = TRUE);
                      PPP <- array(0, dim = c(5,5,N));
                      PPP[,,1] <- P;
                      for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; } 
                      PPP }

#Calculate probabilities of reaching apple for n = 1,...,100
N  <- 100;
DF <- data.frame(Probability = PROB(N)[3,1,], Moves = 1:N);

#Plot probability of not having reached apple
library(ggplot2);
FIGURE <- ggplot(DF, aes(x = Moves, y = 1-Probability)) +
          geom_point() +
          scale_y_log10(breaks = scales::trans_breaks("log10", function(x) 10^x),
                        labels = scales::trans_format("log10", 
                                 scales::math_format(10^.x))) +
          ggtitle('Probability that worm has not reached apple') +
          xlab('Number of Moves') + ylab('Probability');
FIGURE;

#Calculate expected number of moves to get to apple
#Calculation truncates the infinite sum at N = 100
#We add one to represent the term for n = 0
EXP <- 1 + sum(1-DF$Probability);
EXP;

[1] 6

Seperti yang dapat Anda lihat dari perhitungan ini, jumlah gerakan yang diharapkan untuk mencapai apel adalah enam. Perhitungan ini sangat cepat menggunakan kode vektor di atas untuk rantai Markov.

masukkan deskripsi gambar di sini

Ben - Pasang kembali Monica
sumber
5

Hanya ingin mengilustrasikan cara sederhana untuk melihat bagian (a) tanpa melalui semua rantai rutin Markov. Ada dua kelas negara yang perlu dikhawatirkan: menjadi satu langkah dan dua langkah lagi (C dan D identik dalam hal langkah yang diharapkan hingga mencapai A, dan B dan E identik). Biarkan " " mewakili jumlah langkah yang diambil dari vertex dan seterusnya.SBB

E(SC)=1+12[E(SB)+E(SD)]=1+12[E(SB)+E(SC)]

Demikian pula menulis persamaan untuk ekspektasi untuk .E(SB)

Gantikan yang kedua menjadi yang pertama (dan untuk kenyamanan tuliskan untuk ) dan Anda mendapatkan solusi untuk dalam beberapa baris.E ( S C ) ccE(SC)c

Glen_b -Reinstate Monica
sumber
3
+1. Saya juga suka itu dengan mengganti harapan dengan fungsi-fungsi yang menghasilkan probabilitas Anda mendapatkan persamaan yang sama, sama mudahnya diselesaikan, menunjukkan bahwa pgf untuk keadaan awal sama dengan dan yang mengarah ke formula sederhana untuk setiap probabilitas. Lebih baik: biarkan menjadi jumlah langkah yang dimulai dariTentukan dan adalah danMengganti yang terakhir ke dalam hasil sebelumnya untuk Dengan demikian, adalaht2/(42tt2),Xyy{A,B}.fn=2nPr(XA=n)gn=2nPr(XB=n).fn=fn1+gn1gn1=fn2.fn=fn1+fn2n3.fnn2ndAngka Fibonacci.
whuber
@whuber: Anda harus mengubah komentar Anda menjadi jawaban lengkap - ini sangat bagus.
Ben - Pasang kembali Monica,
1
Saya setuju, ada baiknya memposting sebagai jawaban, bahkan dalam bentuk singkat ini.
Glen_b -Reinstate Monica
3

Masalah

Rantai Markov ini memiliki tiga status, dibedakan dengan apakah cacing berjarak atau spasi dari Misalkan menjadi variabel acak yang memberikan berapa langkah cacing akan dilakukan untuk mencapai dari keadaan Mereka fungsi pembangkit probabilitas adalah cara aljabar nyaman untuk mengkodekan probabilitas variabel-variabel ini. Hal ini tidak perlu khawatir tentang isu-isu analitik seperti konvergensi: hanya melihat mereka sebagai seri kekuasaan formal di simbol diberikan oleh0, 1,2C.XiCi{0,1,2}.t

fi(t)=Pr(Xi=0)+Pr(Xi=1)t1+Pr(Xi=2)t2++Pr(Xi=n)tn+

Karena itu sepele bahwa Kita perlu menemukanPr(X0=0)=1,f0(t)=1.f2.

Analisis dan solusi

Dari negara worm memiliki kesempatan yang sama dari pindah kembali ke keadaan atau mencapai . Akuntansi untuk mengambil satu langkah ini menambahkan ke semua kekuatan , sama dengan mengalikan pgf dengan , memberi1,1/22C1tt

f1=12t(f2+f0).

Demikian pula, dari kondisi cacing memiliki peluang yang sama untuk tetap dalam kondisi atau mencapai kondisi mana221,

f2=12t(f2+f1).

Tampilan menunjukkan pekerjaan kita akan dipermudah dengan memperkenalkan variabel memberit/2x=t/2,

f1(x)=x(f2(x)+f0(x));f2(x)=x(f2(x)+f1(x)).

Mengganti yang pertama menjadi yang kedua dan mengingat memberif0=1

(*)f2(x)=x(f2(x)+x(f2(x)+1))

yang memiliki solusi unik

(**)f2(x)=x21xx2.

Saya menyoroti persamaan untuk menekankan kesederhanaan dasarnya dan persamaan formalnya dengan persamaan yang akan kami peroleh dengan menganalisis hanya nilai yang diharapkan pada dasarnya, untuk jumlah pekerjaan yang sama yang dibutuhkan untuk menemukan nomor yang satu ini, kami mendapatkan seluruh distribusi.()E[Xi]:

Implikasi dan penyederhanaan

Secara ekuivalen, ketika dituliskan istilah demi istilah dan kekuatan dicocokkan, ini menyatakan bahwa untuk()tn4,

2nPr(X2=n)=2n1Pr(X2=n1)+2n2Pr(X2=n2).

Ini adalah pengulangan untuk deretan angka Fibonacci yang terkenal

(Fn)=(1,1,2,3,5,8,13,21,34,55,89,144,)

(diindeks dari ). Solusi yang cocok adalah urutan ini digeser oleh dua tempat (karena tidak ada kemungkinan atau dan mudah untuk memeriksa bahwa ).n=0()X2=0X2=122Pr(X2=2)=1=23Pr(X2=3)

Karena itu

Pr(X2=n)=2n2Fn2.

Lebih spesifik,

f2(t)=22F0t2+23F1t3+24F2t4+=14t2+18t3+216t4+332t5+564t6+8128t7+13256t8+.

Harapan mudah ditemukan dengan mengevaluasi turunan dan mengganti karena (membedakan kekuatan istilah dengan istilah) ini memberikan rumusX2ft=1,t

f(1)=Pr(X2=0)(0)+Pr(X2=1)(1)10++Pr(X2=n)(n)1n1+

yang, sebagai jumlah dari probabilitas kali nilai-nilai justru definisi dari Mengambil turunan menggunakan menghasilkan formula sederhana untuk ekspektasi.X2,E[X2].()


Beberapa komentar singkat

Dengan memperluas sebagai fraksi parsial, dapat ditulis sebagai jumlah dari dua deret geometri. Ini segera menunjukkan probabilitas akan menurun secara eksponensial. Ini juga menghasilkan formulir tertutup untuk probabilitas ekor Dengan menggunakan itu, kita dapat dengan cepat menghitung bahwa sedikit kurang dari()f2Pr(X2=n)Pr(X2>n).Pr(X2100)109.

Akhirnya, rumus-rumus ini melibatkan Rasio Emas Angka ini adalah panjang akor pentagon reguler (sisi unit), menghasilkan hubungan yang mencolok antara rantai Markov kombinatorial murni pada pentagon (yang "tidak tahu" tentang geometri Euclidean) dan geometri pentagon reguler di Pesawat Euclidean.ϕ=(1+5)/2.

whuber
sumber
1

Untuk jumlah rata-rata hari sampai makan malam, syarat pada langkah yang diambil pada hari pertama. Biarkan menjadi jumlah hari sampai cacing mendapatkan apel. Biarkan menjadi langkah pertama.XF

Lalu kita punya

E[X]=E[X|F=B] [P(F=B)]+E[X|F=D] P[F=D]

Jika langkah pertama adalah ke maka salah satu cacing mendapatkan apel pada hari 2 dengan probabilitas satu-setengah, atau kembali ke vertex dengan probabilitas satu-setengah dan itu dimulai kembali. Kita bisa menulis ini sebagaiB,C

E[X|F=B]=2(12)+(2+E[X])(12)=2+E[X]2

Jika langkah pertama adalah ke maka dengan simetri ini sama dengan berada di titik kecuali worm telah mengambil satu langkah sehinggaCD,C

E[X|F=D]=1+E[X]

Menyatukan semuanya, kita dapatkan

E[X]=(2+E[X]2)(12)+(1+E[X])(12)

Pemecahan untuk hasilE[X]

E[X]=6
soakley
sumber
1
Ini sepertinya merekapitulasi jawaban @ Glen_b.
whuber