Рассмотрите вероятностную модель: бросается правильная шестигранная кость два раза. Сформулируйте и докажите наиболее общий способ вычисления вероятности того, что в сумме выпадет простое число, и обсудите расширение на k бросков
Общий подход и доказательство. 1) Для двух бросков. Пусть X,YX,YX,Y — независимые равномерные на {1,…,6}\{1,\dots,6\}{1,…,6}. Тогда вероятность суммы S=X+YS=X+YS=X+Y равна свертке: P(S=s)=∑x=16P(X=x)P(Y=s−x)=136#{(x,y)∈{1,…,6}2:x+y=s}.
P(S=s)=\sum_{x=1}^6 P(X=x)P(Y=s-x)=\frac{1}{36}\#\{(x,y)\in\{1,\dots,6\}^2:x+y=s\}. P(S=s)=x=1∑6P(X=x)P(Y=s−x)=361#{(x,y)∈{1,…,6}2:x+y=s}.
Число упорядоченных пар с суммой sss равно 1,2,3,4,5,6,5,4,3,2,1при s=2,3,…,12.
1,2,3,4,5,6,5,4,3,2,1\quad\text{при }s=2,3,\dots,12. 1,2,3,4,5,6,5,4,3,2,1приs=2,3,…,12.
Простые суммы в диапазоне 2…122\ldots122…12 — это 2,3,5,7,112,3,5,7,112,3,5,7,11. Соответствующие числа исходов 1,2,4,6,21,2,4,6,21,2,4,6,2, итого 1+2+4+6+2=151+2+4+6+2=151+2+4+6+2=15. Следовательно P(S простое)=1536=512.
P(S\ \text{простое})=\frac{15}{36}=\frac{5}{12}. P(Sпростое)=3615=125. 2) Наиболее общий способ (k бросков). Пусть X1,…,XkX_1,\dots,X_kX1,…,Xk независимы, равномерны на {1,…,6}\{1,\dots,6\}{1,…,6}, и Sk=∑i=1kXiS_k=\sum_{i=1}^k X_iSk=∑i=1kXi. Тогда P(Sk=s)=Nk(s)6k,
P(S_k=s)=\frac{N_k(s)}{6^k}, P(Sk=s)=6kNk(s),
где Nk(s)N_k(s)Nk(s) — число решений в целых для x1+⋯+xk=s,1≤xi≤6.
x_1+\dots+x_k=s,\qquad 1\le x_i\le6. x1+⋯+xk=s,1≤xi≤6.
Его можно выразить формулой включений-исключений: Nk(s)=∑j=0⌊(s−k)/6⌋(−1)j(kj)(s−6j−1k−1).
N_k(s)=\sum_{j=0}^{\lfloor (s-k)/6\rfloor}(-1)^j\binom{k}{j}\binom{s-6j-1}{k-1}. Nk(s)=j=0∑⌊(s−k)/6⌋(−1)j(jk)(k−1s−6j−1).
Тогда для любого множества сумм AAA (например, множества простых чисел) имеем P(Sk∈A)=∑s1A(s)Nk(s)6k.
P(S_k\in A)=\sum_{s} \mathbf{1}_{A}(s)\frac{N_k(s)}{6^k}. P(Sk∈A)=s∑1A(s)6kNk(s).
Альтернативно, можно взять производящую функцию Gk(t)=(t+⋯+t66)k,
G_k(t)=\Big(\frac{t+\dots+t^6}{6}\Big)^k, Gk(t)=(6t+⋯+t6)k,
и извлекать коэффициенты [ts]Gk(t)=P(Sk=s) [t^s]G_k(t)=P(S_k=s)[ts]Gk(t)=P(Sk=s). 3) Асимптотика при больших kkk. Пусть μ=E[Xi]=3.5\mu=E[X_i]=3.5μ=E[Xi]=3.5, σ2=Var(Xi)=35/12\sigma^2=\mathrm{Var}(X_i)=35/12σ2=Var(Xi)=35/12. По локальной центральной предельной теореме P(Sk=s)≈12πkσ2exp(−(s−kμ)22kσ2).
P(S_k=s)\approx\frac{1}{\sqrt{2\pi k\sigma^2}}\exp\Big(-\frac{(s-k\mu)^2}{2k\sigma^2}\Big). P(Sk=s)≈2πkσ21exp(−2kσ2(s−kμ)2).
Используя теорему о распределении простых (плотность простых около xxx примерно 1/lnx1/\ln x1/lnx), можно аппроксимировать P(Sk простое)≈∫k6k1lnx 12πkσ2exp(−(x−kμ)22kσ2) dx.
P(S_k\ \text{простое})\approx\int_{k}^{6k}\frac{1}{\ln x}\,\frac{1}{\sqrt{2\pi k\sigma^2}} \exp\Big(-\frac{(x-k\mu)^2}{2k\sigma^2}\Big)\,dx. P(Skпростое)≈∫k6klnx12πkσ21exp(−2kσ2(x−kμ)2)dx.
При больших kkk подинтегральный множитель 1/lnx1/\ln x1/lnx меняется медленно и примерно равен 1/ln(3.5k)1/\ln(3.5k)1/ln(3.5k), поэтому интеграл даёт P(Sk простое)∼1ln(3.5k)(при k→∞),
P(S_k\ \text{простое})\sim\frac{1}{\ln(3.5k)}\quad\text{(при }k\to\infty\text{)}, P(Skпростое)∼ln(3.5k)1(приk→∞),
то есть вероятность убывает порядка 1/lnk1/\ln k1/lnk. Краткое резюме: - Для двух бросков формула свертки даёт P=15/36=5/12P=15/36=5/12P=15/36=5/12. - Для kkk бросков общая формула через число решений Nk(s)N_k(s)Nk(s) или через производящую функцию (t+⋯+t66)k(\frac{t+\dots+t^6}{6})^k(6t+⋯+t6)k. - Для больших kkk по локальной ЦПТ и теореме о простых P(Sk простое)P(S_k\ \text{простое})P(Skпростое) примерно равно 1/ln(3.5k)1/\ln(3.5k)1/ln(3.5k).
1) Для двух бросков. Пусть X,YX,YX,Y — независимые равномерные на {1,…,6}\{1,\dots,6\}{1,…,6}. Тогда вероятность суммы S=X+YS=X+YS=X+Y равна свертке:
P(S=s)=∑x=16P(X=x)P(Y=s−x)=136#{(x,y)∈{1,…,6}2:x+y=s}. P(S=s)=\sum_{x=1}^6 P(X=x)P(Y=s-x)=\frac{1}{36}\#\{(x,y)\in\{1,\dots,6\}^2:x+y=s\}.
P(S=s)=x=1∑6 P(X=x)P(Y=s−x)=361 #{(x,y)∈{1,…,6}2:x+y=s}. Число упорядоченных пар с суммой sss равно
1,2,3,4,5,6,5,4,3,2,1при s=2,3,…,12. 1,2,3,4,5,6,5,4,3,2,1\quad\text{при }s=2,3,\dots,12.
1,2,3,4,5,6,5,4,3,2,1при s=2,3,…,12. Простые суммы в диапазоне 2…122\ldots122…12 — это 2,3,5,7,112,3,5,7,112,3,5,7,11. Соответствующие числа исходов 1,2,4,6,21,2,4,6,21,2,4,6,2, итого 1+2+4+6+2=151+2+4+6+2=151+2+4+6+2=15. Следовательно
P(S простое)=1536=512. P(S\ \text{простое})=\frac{15}{36}=\frac{5}{12}.
P(S простое)=3615 =125 .
2) Наиболее общий способ (k бросков). Пусть X1,…,XkX_1,\dots,X_kX1 ,…,Xk независимы, равномерны на {1,…,6}\{1,\dots,6\}{1,…,6}, и Sk=∑i=1kXiS_k=\sum_{i=1}^k X_iSk =∑i=1k Xi . Тогда
P(Sk=s)=Nk(s)6k, P(S_k=s)=\frac{N_k(s)}{6^k},
P(Sk =s)=6kNk (s) , где Nk(s)N_k(s)Nk (s) — число решений в целых для
x1+⋯+xk=s,1≤xi≤6. x_1+\dots+x_k=s,\qquad 1\le x_i\le6.
x1 +⋯+xk =s,1≤xi ≤6. Его можно выразить формулой включений-исключений:
Nk(s)=∑j=0⌊(s−k)/6⌋(−1)j(kj)(s−6j−1k−1). N_k(s)=\sum_{j=0}^{\lfloor (s-k)/6\rfloor}(-1)^j\binom{k}{j}\binom{s-6j-1}{k-1}.
Nk (s)=j=0∑⌊(s−k)/6⌋ (−1)j(jk )(k−1s−6j−1 ). Тогда для любого множества сумм AAA (например, множества простых чисел) имеем
P(Sk∈A)=∑s1A(s)Nk(s)6k. P(S_k\in A)=\sum_{s} \mathbf{1}_{A}(s)\frac{N_k(s)}{6^k}.
P(Sk ∈A)=s∑ 1A (s)6kNk (s) . Альтернативно, можно взять производящую функцию
Gk(t)=(t+⋯+t66)k, G_k(t)=\Big(\frac{t+\dots+t^6}{6}\Big)^k,
Gk (t)=(6t+⋯+t6 )k, и извлекать коэффициенты [ts]Gk(t)=P(Sk=s) [t^s]G_k(t)=P(S_k=s)[ts]Gk (t)=P(Sk =s).
3) Асимптотика при больших kkk. Пусть μ=E[Xi]=3.5\mu=E[X_i]=3.5μ=E[Xi ]=3.5, σ2=Var(Xi)=35/12\sigma^2=\mathrm{Var}(X_i)=35/12σ2=Var(Xi )=35/12. По локальной центральной предельной теореме
P(Sk=s)≈12πkσ2exp(−(s−kμ)22kσ2). P(S_k=s)\approx\frac{1}{\sqrt{2\pi k\sigma^2}}\exp\Big(-\frac{(s-k\mu)^2}{2k\sigma^2}\Big).
P(Sk =s)≈2πkσ2 1 exp(−2kσ2(s−kμ)2 ). Используя теорему о распределении простых (плотность простых около xxx примерно 1/lnx1/\ln x1/lnx), можно аппроксимировать
P(Sk простое)≈∫k6k1lnx 12πkσ2exp(−(x−kμ)22kσ2) dx. P(S_k\ \text{простое})\approx\int_{k}^{6k}\frac{1}{\ln x}\,\frac{1}{\sqrt{2\pi k\sigma^2}}
\exp\Big(-\frac{(x-k\mu)^2}{2k\sigma^2}\Big)\,dx.
P(Sk простое)≈∫k6k lnx1 2πkσ2 1 exp(−2kσ2(x−kμ)2 )dx. При больших kkk подинтегральный множитель 1/lnx1/\ln x1/lnx меняется медленно и примерно равен 1/ln(3.5k)1/\ln(3.5k)1/ln(3.5k), поэтому интеграл даёт
P(Sk простое)∼1ln(3.5k)(при k→∞), P(S_k\ \text{простое})\sim\frac{1}{\ln(3.5k)}\quad\text{(при }k\to\infty\text{)},
P(Sk простое)∼ln(3.5k)1 (при k→∞), то есть вероятность убывает порядка 1/lnk1/\ln k1/lnk.
Краткое резюме:
- Для двух бросков формула свертки даёт P=15/36=5/12P=15/36=5/12P=15/36=5/12.
- Для kkk бросков общая формула через число решений Nk(s)N_k(s)Nk (s) или через производящую функцию (t+⋯+t66)k(\frac{t+\dots+t^6}{6})^k(6t+⋯+t6 )k.
- Для больших kkk по локальной ЦПТ и теореме о простых P(Sk простое)P(S_k\ \text{простое})P(Sk простое) примерно равно 1/ln(3.5k)1/\ln(3.5k)1/ln(3.5k).