Berapa probabilitas bahwa dari 25 angka acak antara 1 dan 100, angka tertinggi muncul lebih dari satu kali?

Dalam banyak game online, ketika pemain menyelesaikan tugas yang sulit, kadang-kadang diberikan hadiah khusus yang dapat digunakan oleh semua orang yang menyelesaikan tugas itu. ini biasanya mount (metode transportasi) atau item batil lainnya (item yang tidak meningkatkan kinerja karakter dan terutama digunakan untuk penyesuaian penampilan).

Ketika hadiah seperti itu diberikan, cara paling umum untuk menentukan siapa yang mendapatkan hadiah adalah melalui angka acak. Gim biasanya memiliki perintah khusus yang menghasilkan angka acak (kemungkinan pseudorandom, bukan crypto secure random) antara 1 dan 100 (kadang-kadang pemain dapat memilih spread lain, tetapi 100 adalah yang paling umum). Setiap pemain menggunakan perintah ini, semua pemain dapat melihat siapa yang menggulung apa, dan item diberikan kepada orang yang menggulung tertinggi. Sebagian besar game bahkan memiliki sistem built-in di mana pemain hanya menekan tombol dan setelah semua orang menekan tombol mereka, permainan melakukan sisanya secara otomatis.

Terkadang, beberapa pemain menghasilkan angka tinggi yang sama dan tidak ada yang mengalahkan mereka. ini biasanya diselesaikan oleh para pemain yang memperbarui nomor mereka, sampai ada angka tertinggi yang unik.

Pertanyaan saya adalah sebagai berikut: Asumsikan generator angka acak yang dapat menghasilkan angka antara 1 dan 100 dengan probabilitas yang sama. Asumsikan bahwa Anda memiliki grup yang terdiri dari 25 pemain yang masing-masing menghasilkan 1 angka dengan generator angka acak (masing-masing dengan seed sendiri). Anda akan memiliki 25 angka antara 1 dan 100, tanpa batasan berapa banyak pemain yang menggulirkan nomor tertentu dan tidak ada hubungan di antara angka-angka tersebut. Berapa peluang angka tertinggi yang dihasilkan dihasilkan oleh lebih dari 1 pemain? Dengan kata lain, apa kemungkinan dasi?

probability random-generation Nzall
sumber

World of Warcraft eh?

Behacad

ya, seragam acak, seperti yang dinyatakan dalam pertanyaan (angka antara 1 dan 100 inklusif memiliki probabilitas yang sama.

Nzall

Pertanyaan bagus, tapi ini menurut saya cara yang buruk untuk memilih pemenang. Cukup daftarkan pemain dengan beberapa cara (Anda bisa mengatakan, "nama secara alfabet" atau mengocoknya dan menunjukkan kepada semua orang daftar itu, atau mengurutkan beberapa cara lain), dan pilih nomor acak antara 1 dan 25. Angka yang sesuai dengan kemenangan pemain.

Tim S.

Noobs, gunakan DKP!

Davor

Saran: diberikan sampel acak dari , kita perlu menghitung menggunakan apa yang kita ketahui dari teori statistik pesanan.

X_{1}, \dots, X_{25}

$X_1,\dots,X_{25}$

U {1, \dots, 100}

$\textrm{U}\{1,\dots,100\}$

P (X_{(24)} < X_{(25)})

$P(X_{(24)}<X_{(25)})$

Zen

Jawaban:

Membiarkan

$x$ menjadi ujung atas rentang Anda, dalam kasus Anda. $x=100$
$n$ menjadi jumlah total undian, dalam kasus Anda. $n=25$

Untuk setiap angka , jumlah urutan angka dengan setiap angka dalam urutan adalah . Dari urutan ini, angka yang mengandung no s adalah , dan nomor yang berisi adalah . Oleh karena itu jumlah urutan dengan dua atau lebih s adalah Jumlah total urutan angka dengan jumlah tertinggi berisi di setidaknya dua s yaitu $y\le x$ $n$ $\le y$ $y^n$ $y$ $(y-1)^n$ $y$ $n(y-1)^{n-1}$ $y$

y^{n} - (y - 1)^{n} - n (y - 1)^{n - 1}

$y^n - (y-1)^n - n(y-1)^{n-1}$

n

$n$

y

$y$

y

$y$

\begin{aligned} \sum_{y = 1}^{x} (y^{n} - (y - 1)^{n} - n (y - 1)^{n - 1}) & = \sum_{y = 1}^{x} y^{n} - \sum_{y = 1}^{x} (y - 1)^{n} - \sum_{y = 1}^{x} n (y - 1)^{n - 1} \\ = x^{n} - n \sum_{y = 1}^{x} (y - 1)^{n - 1} \\ = x^{n} - n \sum_{y = 1}^{x - 1} y^{n - 1} \end{aligned}

$\begin{align} \sum_{y=1}^x \left(y^n - (y-1)^n - n(y-1)^{n-1}\right) &= \sum_{y=1}^x y^n - \sum_{y=1}^x(y-1)^n - \sum_{y=1}^xn(y-1)^{n-1}\\ &= x^n - n\sum_{y=1}^x(y-1)^{n-1}\\ &= x^n - n\sum_{y=1}^{x-1}y^{n-1}\\ \end{align}$

Jumlah total urutan hanya . Semua urutan sama-sama berpeluang besar sehingga kemungkinannya adalah $x^n$

\frac{x^{n} - n \sum_{y = 1}^{y = x - 1} y^{n - 1}}{x^{n}}

$\frac{x^n - n\sum_{y=1}^{y=x-1}y^{n-1}}{x^n}$

Dengan saya membuat probabilitas 0,120004212454. $x=100,n=25$

Saya telah menguji ini menggunakan program Python berikut, yang menghitung urutan yang cocok secara manual (untuk rendah ), mensimulasikan dan menghitung menggunakan rumus di atas. $x,n$

import itertools
import numpy.random as np

def countinlist(x, n):
    count = 0
    total = 0
    for perm in itertools.product(range(1, x+1), repeat=n):
        total += 1
        if perm.count(max(perm)) > 1:
            count += 1

    print "Counting: x", x, "n", n, "total", total, "count", count

def simulate(x,n,N):
    count = 0
    for i in range(N):
        perm = np.randint(x, size=n)
        m = max(perm)
        if sum(perm==m) > 1:
            count += 1
    print "Simulation: x", x, "n", n, "total", N, "count", count, "prob", count/float(N)

x=100
n=25
N = 1000000 # number of trials in simulation

#countinlist(x,n) # only call this for reasonably small x and n!!!!
simulate(x,n,N)
formula = x**n - n*sum([i**(n-1) for i in range(x)])
print "Formula count", formula, "out of", x**n, "probability", float(formula) / x**n

Program ini di-output

Simulation: x 100 n 25 total 1000000 count 120071 prob 0.120071
Formula count 12000421245360277498241319178764675560017783666750 out of 100000000000000000000000000000000000000000000000000 probability 0.120004212454

TooTone
sumber

+1 Simulasi singkat dalam R kompatibel dengan hasil ini. Setelah simulasi tahun , saya mendapat perkiraan .

200000

$200000$

0.11957

$0.11957$

COOLSerdash

@COOLSerdash Terima kasih banyak. Saya menguji formula saya dengan mencantumkan semua permutasi sebelum memposting (saya akan mendaftar program python sebentar lagi), pada nilai-nilai kecil dan , tetapi saya tidak berpikir untuk mensimulasikan pertanyaan aktual yang diajukan.

x

$x$

n

$n$

TooTone

Saya disimulasikan menggunakan perl dan mendapat 0,005 sangat konsisten. pastebin.com/gb7JMLt6

agweber

@agweber Terima kasih telah menulis dan menjalankan simulasi Anda. Saya bukan programmer Perl jadi saya tidak bisa mengomentari rincian program Anda meskipun pada tingkat tinggi kelihatannya terdengar. Apakah Anda menguji kode simulasi Anda dengan probabilitas yang diketahui, yang mudah dibuat hanya dengan menghitung untuk rendah dan ? Misalkan , probabilitas tepatnya adalah . Saya juga menambah program Python saya dengan kode simulasi, yang setuju dengan probabilitas tepat untuk rendah , dan probabilitas dari rumus yang saya peroleh. Saya ingin tahu apa sumber pertentangan antara kode kami.

x

$x$

n

$n$

x = 20, n = 5

$x=20,n=5$

15600 / 160000 = 0.0975

$15600/160000=0.0975$

x, n

$x,n$

TooTone

Sebuah Mathematica simulasi dengan iterasi diproduksi yang mungkin benar melalui empat digit pertama.

10^{7}

$10^7$

0.119983,

$0.119983,$ n = 10^7; Total[Boole[Equal @@ (#[[Ordering[#, -2]]])] & /@ x = RandomInteger[{1, 100}, {n, 25}]] / n

Kodenya

Saya akan mempertimbangkan untuk menemukan kemungkinan memiliki pemenang yang unik terlebih dahulu

Probabilitas memiliki pemenang yang unik dan jumlahnya adalah sama dengan karena ada 25 pilihan untuk pemenang, dan sisanya dapat memiliki angka mulai dari 1 hingga $x$ $\frac{{25\choose1} (x-1)^{24}}{{100}^{25} }$ $y-1$

Pemenang dapat menang dengan nomornya sama dengan 2 hingga 100 sehingga total probabilitasnya adalah

\begin{aligned} \sum_{i = 2}^{100} \frac{25 (i - 1)^{24}}{100^{25}} \\ = & 25 \sum_{i = 1}^{99} \frac{i^{24}}{100^{25}} \\ = & - \frac{1}{4} + 25 \sum_{i = 1}^{100} \frac{i^{24}}{100^{25}} \\ \approx & - \frac{1}{4} + 25 \frac{\frac{1}{24 + 1} 100^{24 + 1} + \frac{1}{2} 100^{24} + \frac{24}{2} \frac{1}{6} 100^{23}}{100^{25}} \\ = & 0.88 \end{aligned}

$\begin{align} &\sum_{i=2}^{100} \frac {25(i-1)^{24}}{{100}^{25}}\\ =& 25\sum_{i=1}^{99} \frac{i^{24}}{{100}^{25}}\\ =& -{1 \over 4}+25\sum_{i=1}^{100} \frac{i^{24}}{{100}^{25}}\\\approx&-{1 \over 4}+25 {{1\over24+1}{100}^{24+1}+{{1\over2}{100}^{24}+{{{24\over2} {1\over6}}{100}^{23} }}\over{100}^{25}}\\ =&0.88 \end{align}$

Di sini saya menggunakan perkiraan hingga Untuk referensi: https://en.wikipedia.org/wiki/Faulhaber 's_formula $100^{23}$

Oleh karena itu probabilitas memiliki dasi adalah $1-0.88=0.12$

gary
sumber

-3

Tampaknya pertanyaan yang sangat mirip dengan paradoks Ulang Tahun ( http://en.wikipedia.org/wiki/Birthday_problem ), satu-satunya perbedaan adalah bahwa dalam hal ini Anda tidak ingin mencocokkan angka apa pun tetapi hanya angka tertinggi. Langkah pertama dalam perhitungan menghitung probabilitas bahwa tidak ada angka acak yang tumpang tindih ( ). (lihat tautan di atas) dan kemudian probabilitas bahwa beberapa dari 25 angka tumpang tindih adalah mana p adalah probabilitas yang sudah Anda hitung. Dalam hal ini probabilitas 25 angka tidak tumpang tindih dengan maksimum diberikan oleh: maka probabilitas yang Anda cari adalah $p$ $1-p$ $p=1*(1-1/100)*(1-1/100)......*(1-1/10)=(1-1/100)^{24}$ $P=1-p=1-(1-1/100)^{24} = 0.214$

Michel G
sumber

apakah ini berarti bahwa probabilitasnya adalah 21,4%? tampaknya cukup tinggi, tetapi sekali lagi, paradoks ulang tahun memiliki jawaban mengejutkan yang serupa. Terima kasih.

Nzall

-1 Seperti berdiri, jawaban ini tidak benar. Jawaban yang benar diberikan oleh @TooTone.

COOLSerdash