Teka-teki tersembunyi dalam teka-teki pemotongan tongkat klasik – Beragampengetahuan

Oleh: Blog Bogumił Kamiński

Repost dari:

Hari ini saya posting saya, saya ingin fokus pada topik yang kurang teknis
(setidaknya dimulai dengan 😄).

Kami akan membahas pemecahan teka-teki klasik berikut ini:

Anda diberi tongkat sepanjang 1 meter. Seseorang memotongnya n lokasi.
Posisi pemotongan dipilih secara acak dan seragam.
Hasil dari proses yang Anda dapatkan n+1 bagian-bagian. Berapa probabilitasnya?
bahwa dimungkinkan untuk membuat poligon menggunakan mereka?

Ada banyak pendekatan yang bisa digunakan untuk memecahkan teka-teki ini.
Saya ingin membahas sesuatu yang hanya menggunakan probabilitas dasar
teori dan tidak memerlukan trik apapun.

Selanjutnya, kami akan memvalidasi solusi menggunakan Julia 1.9.0-rc1. Larutan
yang akan membawa kita ke teka-teki lain, yang menurut saya penting untuk dipahami
oleh pengguna pembuat nomor acak di Julia.

Kita mulai dengan pengamatan bahwa jika kita diberikan n+1 itu ruas garis
dimungkinkan untuk membuat poligon menggunakan mereka jika dan hanya jika masing-masing memiliki kurang dari
lebih dari 50% dari total panjang batang asli.

Ekspresikan posisi titik potong batang di X(i) Karena i sedang berjalan
dari 1 TIBA n. Kami mengukur posisi dari sisi kiri palang.

Kapan kondisi di atas tidak terpenuhi? Kami memiliki dua kasus (saya abaikan
peristiwa probabilitas nol untuk menyederhanakan notasi):

1. semua X(i) lebih besar 0.5 (maka paragraf pertama terlalu panjang), atau
2. untuk beberapa X(i) itu kurang 0.5 dan tidak ada lagi X(j) seperti itu
   0 < X(j) - X(i) < 0.5 (maka segmen dimulai pada titik X(i) terlalu panjang).
   Kita punya n kasus seperti itu.

Komentar penting kedua adalah n+1 peristiwa dianggap diskrit.
Alasannya, tidak boleh ada dua garis yang lebih panjang 0.5
serentak.

Oleh karena itu, probabilitas bahwa setiap segmen lebih panjang dari 0.5 adalah total
tentang probabilitas peristiwa individu.

Jadi kemungkinan itu semua X(i) lebih besar 0.5? Itu relatif
mudah. Kita punya n peristiwa independen, masing-masing dengan probabilitas 0.5 jadi total
probabilitas adalah 1/2^n.

Dan berapa probabilitasnya? X(i) kurang dari 0.5 dan tidak ada lagi
X(j) seperti itu 0 < X(j) - X(i) < 0.5? lagi kita punya n acara mandiri
(satu untuk posisi X(i) Dan n-1 untuk lokasi X(j) Karena j Selain daripada i)
dan masing-masing peristiwa ini memiliki 0.5 probabilitas, jadi sekali lagi kita memiliki probabilitas itu
Menjadi 1/2^n.

Secara total, kami mendapatkan probabilitas bahwa setidaknya satu segmen lebih panjang
0.5 Menjadi (n+1)/2^njadi kemungkinan kita membuat poligon adalah 1-(n+1)/2^n.

Mari kita tulis simulasi sederhana di Julia untuk menguji hasil kita. Pertama tulis fungsi itu
menerima n titik dari [0, 1] interval dan periksa apakah mereka memotong bilah menjadi beberapa segmen
dari mana seseorang dapat membuat poligon:

check(x) = maximum(diff(sort!([0.0; x; 1.0]))) < 0.5

Pertama tambahkan mulai (0.0) dan diakhiri (1.0) titik batang. Selanjutnya, kami mengurutkan poin yang dilewati
dalam urutan menaik di tempat menggunakan sort!. Dengan berlari diff bekerja, kami menghitung panjangnya
segmen batang yang dibuat dan periksa apakah yang terpanjang kurang dari 0.5.

Sekarang kita siap untuk menulis sebuah fungsi yang menjalankan simulasi ini berulang kali
(1 juta dalam contoh saya) untuk memperkirakan probabilitasnya:

runtest(n) = count(_ -> check(rand(n)), 1:10^6) / 10^6

Mari kita jalankan simulasi untuk beberapa nilai n dan bandingkan hasilnya dengan hasil analitis:

julia> using Random

julia> Random.seed!(1234);

julia> [(n=n, theory=1-(n+1)/2^n, simulation=runtest(n)) for n in 1:10]
10-element Vector{NamedTuple{(:n, :theory, :simulation), Tuple{Int64, Float64, Float64}}}:
 (n = 1, theory = 0.0, simulation = 0.0)
 (n = 2, theory = 0.25, simulation = 0.250275)
 (n = 3, theory = 0.5, simulation = 0.500066)
 (n = 4, theory = 0.6875, simulation = 0.687842)
 (n = 5, theory = 0.8125, simulation = 0.812825)
 (n = 6, theory = 0.890625, simulation = 0.890247)
 (n = 7, theory = 0.9375, simulation = 0.9374)
 (n = 8, theory = 0.96484375, simulation = 0.964881)
 (n = 9, theory = 0.98046875, simulation = 0.980502)
 (n = 10, theory = 0.9892578125, simulation = 0.989465)

Hasilnya terlihat konsisten.

Mari kita menilai kecepatan kode kita:

julia> @time [(n=n, theory=1-(n+1)/2^n, simulation=runtest(n)) for n in 1:10];
 10.075038 seconds (100.03 M allocations: 4.621 GiB, 10.55% gc time, 0.69% compilation time)

Kita dapat membuatnya lebih cepat dengan menghindari alokasi yang tidak perlu:

function runtest_faster(n)
    x = zeros(n+2)
    x[end] = 1.0
    v = @view x[2:end-1]
    return count(1:10^6) do _
        rand!(v)
        sort!(v)
        m = 0.0
        xa = first(x)
        @inbounds for i in 2:n+2
            xb = x[i]
            m = max(m, xb - xa)
            xa = xb
        end
        return m < 0.5
    end / 10^6
end

Pertama mari kita periksa hasilnya:

julia> Random.seed!(1234);

julia> [(n=n, theory=1-(n+1)/2^n, simulation=runtest_faster(n)) for n in 1:10]
10-element Vector{NamedTuple{(:n, :theory, :simulation), Tuple{Int64, Float64, Float64}}}:
 (n = 1, theory = 0.0, simulation = 0.0)
 (n = 2, theory = 0.25, simulation = 0.250275)
 (n = 3, theory = 0.5, simulation = 0.500066)
 (n = 4, theory = 0.6875, simulation = 0.687842)
 (n = 5, theory = 0.8125, simulation = 0.812825)
 (n = 6, theory = 0.890625, simulation = 0.890247)
 (n = 7, theory = 0.9375, simulation = 0.9374)
 (n = 8, theory = 0.96484375, simulation = 0.964919)
 (n = 9, theory = 0.98046875, simulation = 0.980717)
 (n = 10, theory = 0.9892578125, simulation = 0.989311)

Yang menarik terserah n=7 kami mendapatkan hasil yang identik, tetapi awalnya berbeda
Karena n=8. Kami akan segera menyelidikinya.

Namun, pertama-tama kami memeriksa waktu:

julia> @time [(n=n, theory=1-(n+1)/2^n, simulation=runtest_faster(n)) for n in 1:10];
  1.792463 seconds (22.75 k allocations: 1.533 MiB, 2.80% compilation time)

Seperti yang bisa kita lihat, jumlah alokasi telah menurun secara signifikan.

Lihatlah kode ini:

julia> Random.seed!(1234); rand(7)
7-element Vector{Float64}:
 0.32597672886359486
 0.5490511363155669
 0.21858665481883066
 0.8942454282009883
 0.35311164439921205
 0.39425536741585077
 0.9531246272848422

julia> Random.seed!(1234); rand!(zeros(7))
7-element Vector{Float64}:
 0.32597672886359486
 0.5490511363155669
 0.21858665481883066
 0.8942454282009883
 0.35311164439921205
 0.39425536741585077
 0.9531246272848422

julia> Random.seed!(1234); rand!(view(zeros(7), :))
7-element view(::Vector{Float64}, :) with eltype Float64:
 0.32597672886359486
 0.5490511363155669
 0.21858665481883066
 0.8942454282009883
 0.35311164439921205
 0.39425536741585077
 0.9531246272848422

Semua terlihat bagus. Hasilnya identik. Sekarang tambah panjang vektor satu per satu:

julia> Random.seed!(1234); rand(8)
8-element Vector{Float64}:
 0.5798621201341324
 0.4112941179498505
 0.9721360824554687
 0.014908849285099945
 0.520354993723718
 0.6395615996802734
 0.8396219340580711
 0.967142768915383

julia> Random.seed!(1234); rand!(zeros(8))
8-element Vector{Float64}:
 0.5798621201341324
 0.4112941179498505
 0.9721360824554687
 0.014908849285099945
 0.520354993723718
 0.6395615996802734
 0.8396219340580711
 0.967142768915383

julia> Random.seed!(1234); rand!(view(zeros(8), :))
8-element view(::Vector{Float64}, :) with eltype Float64:
 0.32597672886359486
 0.5490511363155669
 0.21858665481883066
 0.8942454282009883
 0.35311164439921205
 0.39425536741585077
 0.9531246272848422
 0.7955469475347194

Apa yang terjadi disini? Kami baru saja memenangkan kuis yang saya janjikan
yang tersembunyi di teka-teki asli kami.

Ternyata generator nomor acak default
di Julia menggunakan metode lain untuk menghasilkan angka acak Array
lebih untuk umum AbstractArray dalam beberapa kasus.

Kode yang relevan untuk kasus kita adalah sebagai berikut.
Yang digunakan oleh Julia untuk Vector{Float64}:

function rand!(rng::Union{TaskLocalRNG, Xoshiro},
               dst::Array{Float64},
               ::SamplerTrivial{CloseOpen01{Float64}})
    GC.@preserve dst xoshiro_bulk(rng,
                                  convert(Ptr{UInt8},
                                  pointer(dst)),
                                  length(dst)*8,
                                  Float64,
                                  xoshiroWidth(),
                                  _bits2float)
    dst
end

dan kode yang digunakan untuk tampilan:

function rand!(rng::AbstractRNG, A::AbstractArray{T}, sp::Sampler) where T
    for i in eachindex(A)
        x = rand(rng, sp)
        @inbounds A[i] = x
    end
    A
end

Oleh karena itu, yang perlu Anda ingat adalah jika Anda mengubah
kode rand di dalam rand! untuk meningkatkan kinerja yang dihasilkan
Perhitungan Anda mungkin berbeda.

Saya harap Anda menikmati teka-teki. Jika Anda bertanya-tanya apakah solusi analitis
mungkin lebih sederhana jawabannya adalah ya. Kita bisa lolos dari yang spesial
kasus dalam derivasi kami dengan mengikuti pengamatan. Alih-alih menganalisis
memotong bar n tempat di mana Anda dapat membayangkan bahwa Anda memotong lingkaran n+1
lokasi. Kemudian kami menemukan bahwa semua titik potong tidak dapat dibedakan,
dan apa yang perlu kita periksa apakah ada celah 0.5 panjang kata yang diberikan
titik pandang searah jarum jam dari itu. Probabilitas jarak tersebut adalah 1/2^n
seperti apa yang kita miliki n titik tidak bisa terletak di area yang panjangnya 0.5. Sisanya
argumen dalam turunannya sama dengan di atas.

Juga, seperti biasa, kami memiliki pelajaran lari (semoga bermanfaat).
simulasi acak di Julia (terutama jika Anda ingin dapat direproduksi):
rand Dan rand! tidak dijamin untuk menghasilkan urutan angka acak yang sama.

Terkait