Peluang - seberapa tinggi Anda bisa pergi?

10

Saya sebelumnya menanyakan pertanyaan bagaimana menghitung probabilitas dengan cepat dan akurat. Namun, ternyata itu terlalu mudah karena diberikan solusi bentuk tertutup! Ini versi yang lebih sulit.

Tugas ini adalah tentang menulis kode untuk menghitung probabilitas secara tepat dan cepat . Outputnya harus berupa probabilitas tepat yang ditulis sebagai pecahan dalam bentuk yang paling dikurangi. Itu seharusnya tidak pernah output 4/8melainkan 1/2.

Untuk beberapa bilangan bulat positif n, pertimbangkan string acak seragam panjang 1s dan -1s ndan menyebutnya A. Sekarang gabungkan ke Asalinan itu sendiri. Itu A[1] = A[n+1]jika pengindeksan dari 1, A[2] = A[n+2]dan sebagainya. Asekarang memiliki panjang 2n. Sekarang juga pertimbangkan string acak kedua panjang ndengan nnilai pertama -1, 0, atau 1 dengan probabilitas 1 / 4,1 / 2, masing-masing 1/4 dan menyebutnya B.

Sekarang pertimbangkan produk dalam Bdengan A[1+j,...,n+j]untuk yang berbeda j =0,1,2,....

Sebagai contoh, pertimbangkan n=3. Nilai yang mungkin untuk Adan Bbisa A = [-1,1,1,-1,...]dan B=[0,1,-1]. Dalam hal ini dua produk dalam yang pertama adalah 0dan 2.

Tugas

Untuk masing-masing j, dimulai dengan j=1, kode Anda harus menampilkan probabilitas bahwa semua j+1produk dalam pertama adalah nol untuk setiap n=j,...,50.

Menyalin tabel yang diproduksi oleh Martin Büttner untuk j=1kami memiliki hasil sampel berikut.

n   P(n)
1   1/2
2   3/8
3   7/32
4   89/512
5   269/2048
6   903/8192
7   3035/32768
8   169801/2097152

Skor

Skor Anda adalah jkode terbesar yang Anda selesaikan dalam 1 menit di komputer saya. Untuk menjelaskan sedikit, masing j- masing mendapat satu menit. Perhatikan bahwa kode pemrograman dinamis dalam pertanyaan terkait sebelumnya akan melakukan ini dengan mudah j=1.

Pemutus dasi

Jika dua entri mendapatkan jskor yang sama maka entri yang menang akan menjadi yang tertinggi ndalam satu menit pada mesin saya untuk itu j. Jika dua entri terbaik sama pada kriteria ini juga maka pemenangnya adalah jawaban yang dikirimkan terlebih dahulu.

Bahasa dan perpustakaan

Anda dapat menggunakan bahasa dan perpustakaan yang tersedia secara bebas yang Anda suka. Saya harus dapat menjalankan kode Anda jadi tolong sertakan penjelasan lengkap tentang cara menjalankan / kompilasi kode Anda di linux jika memungkinkan.

Mesin Saya Pengaturan waktu akan dijalankan pada mesin saya. Ini adalah instalasi ubuntu standar pada Prosesor Delapan Core AMD FX-8350. Ini juga berarti saya harus dapat menjalankan kode Anda.

Entri yang menang

  • j=2dalam Python oleh Mitch Schwartz.
  • j=2dalam Python oleh feersum. Saat ini entri tercepat.
Komunitas
sumber
Jika pertanyaannya tidak jelas, tolong beri tahu saya agar saya dapat memperbaikinya dengan cepat.
2
Sejauh ini, Anda adalah penanya pertanyaan favorit saya. Kemudian lagi, saya memiliki sesuatu untuk menghitung nilai dengan tepat dan cepat .
primo
@ primo Terima kasih! Apakah ini berarti kita dapat mengharapkan jawaban dalam RPython? :)
Bisakah Anda menempatkan perbedaan antara pertanyaan ini dan yang lainnya?
kirbyfan64sos
@ kirbyfan64sos Yang lain pada dasarnya adalah pertanyaan yang sama untuk `j = 1` saja.

Jawaban:

3

Python 2, j = 2

Saya mencoba menemukan semacam 'bentuk tertutup' untuk j = 2. Mungkin saya bisa membuat gambar MathJax tentang itu, meskipun itu akan sangat jelek dengan semua indeks mengutak-atik. Saya menulis kode yang tidak dioptimalkan ini hanya untuk menguji formula. Diperlukan sekitar 1 detik untuk menyelesaikannya. Hasilnya sesuai dengan kode Mitch Schwartz.

ch = lambda n, k: n>=k>=0 and fac[n]/fac[k]/fac[n-k]
W = lambda l, d: ch(2*l, l+d)
P = lambda n, p: n==0 or ch(n-1, p-1)
ir = lambda a,b: xrange(a,b+1)

N = 50
fac = [1]
for i in ir(1,4*N): fac += [i * fac[-1]]

for n in ir(2, N):
    s = 0
    for i in ir(0,n+1):
     for j in ir(0,min(i,n+1-i)):
      for k in ir(0,n+i%2-i-j):
       t=(2-(k==0))*W(n+i%2-i-j,k)*W(i-(j+i%2),k)*W(j,k)**2*P(i,j+i%2)*P(n+1-i,j+1-i%2)
       s+=t
    denp = 3 * n - 1
    while denp and not s&1: denp -= 1; s>>=1
    print n, '%d/%d'%(s,1<<denp)

Pertimbangkan urutan di mana anggota ke-i adalah ejika A [i] == A [i + 1] atau njika A [i]! = A [i + 1]. idalam program ini adalah jumlah ns. Jika igenap, urutannya harus dimulai dan diakhiri dengan e. Jika iganjil, urutannya harus dimulai dan diakhiri dengan n. Urutan selanjutnya diklasifikasikan berdasarkan jumlah run berturut-turut es atau ns. Ada j+1 dari satu dan jlainnya.

Ketika ide random walk diperpanjang untuk 3 dimensi, ada masalah disayangkan bahwa ada 4 kemungkinan arah untuk berjalan di (satu untuk masing-masing ee, en, ne, atau nn) yang berarti mereka tidak bergantung linear. Jadi kindeks merangkum jumlah langkah yang diambil di salah satu arah (1, 1, 1). Kemudian akan ada jumlah langkah yang tepat yang harus diambil di 3 arah lainnya untuk membatalkannya.

P (n, p) memberikan jumlah partisi n objek yang terurut menjadi p bagian. W (l, d) memberikan sejumlah cara untuk berjalan acak llangkah - langkah untuk menempuh jarak yang tepat d. Seperti sebelumnya ada 1 kesempatan untuk bergerak ke kiri, 1 peluang untuk bergerak ke kanan dan 2 untuk tetap di tempat.

feersum
sumber
Terima kasih! Gambar formula akan sangat bagus.
Terima kasih atas penjelasannya. Anda membuatnya terlihat sederhana! Saya baru saja melihat komentar Anda bahwa Anda dapat membuat solusi untuk j=3. Itu akan luar biasa!
3

Python, j = 2

Pendekatan pemrograman dinamis j = 1dalam jawaban saya untuk pertanyaan sebelumnya tidak perlu banyak modifikasi untuk bekerja lebih tinggi j, tetapi menjadi lambat dengan cepat. Tabel untuk referensi:

n   p(n)

2   3/8
3   11/64
4   71/512
5   323/4096
6   501/8192
7   2927/65536
8   76519/2097152
9   490655/16777216
10  207313/8388608

Dan kodenya:

from time import*
from fractions import*
from collections import*

def main():
    N_MAX=50

    T=time()

    n=2
    Y=defaultdict(lambda:0)
    numer=0

    for a1 in [1]:
        for b1 in (1,0):
            for a2 in (1,-1):
                for b2 in (1,0,0,-1):
                    if not a1*b1+a2*b2 and not a2*b1+a1*b2:
                        numer+=1
                    Y[(a1,a2,b1,b2,a1*b1+a2*b2,a2*b1,0)]+=1

    thresh=N_MAX-1

    while time() <= T+60:
        print('%d %s'%(n,Fraction(numer,8**n/4)))

        if thresh<2:
            print('reached N_MAX with %.2f seconds remaining'%(T+60-time()))
            return

        n+=1
        X=Y
        Y=defaultdict(lambda:0)
        numer=0

        for a1,a2,b1,b2,s,t,u in X:
            if not ( abs(s)<thresh and abs(t)<thresh+1 and abs(u)<thresh+2 ):
                continue

            c=X[(a1,a2,b1,b2,s,t,u)]

            # 1,1

            if not s+1 and not t+b2+a1 and not u+b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s+1,t+b2,u+b1)]+=c

            # -1,1

            if not s-1 and not t-b2+a1 and not u-b1+a1*b2+a2: numer+=c
            Y[(a1,a2,b2,1,s-1,t-b2,u-b1)]+=c

            # 1,-1

            if not s-1 and not t+b2-a1 and not u+b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s-1,t+b2,u+b1)]+=c

            # -1,-1

            if not s+1 and not t-b2-a1 and not u-b1+a1*b2-a2: numer+=c
            Y[(a1,a2,b2,-1,s+1,t-b2,u-b1)]+=c

            # 1,0

            c+=c

            if not s and not t+b2 and not u+b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t+b2,u+b1)]+=c

            # -1,0

            if not s and not t-b2 and not u-b1+a1*b2: numer+=c
            Y[(a1,a2,b2,0,s,t-b2,u-b1)]+=c

        thresh-=1

main()

Di sini kita melacak dua elemen pertama A, dua elemen terakhir dari B(di mana b2adalah elemen terakhir), dan produk-produk batin (A[:n], B), (A[1:n], B[:-1])dan (A[2:n], B[:-2]).

Mitch Schwartz
sumber
.... mencapai N_MAX dengan 21,20 detik tersisa