<jupyter_start><jupyter_text>Разберём одну задачуПусть у нас есть множество с $M$ элементами и мы выбираем $m$ любых элементов пренадлежащих этому множеству. Сначала определим какова вероятность того, хотя бы два элемента из $m$ буду одинаковы? Для этого посчитаем вероятность того, что все элементы будут разные. Способов выбрать $m$ разных элементов $$A^m_M = \frac{M!}{(M-m)!}$$А способов выбрать $m$ элементов $M^m$ по этому наша вероятность будет равна$$P_{all\_diff} = \frac{M!}{(M-m)!M^m} = \frac{(M-1)!}{(M-m)!M^{(m-1)}} = \prod_{i=1}^{m-1}(1-\frac{i}{M})$$А искомая$$ P_{coin} = 1 - P_{all\_diff} = 1 - \prod_{i=1}^{m-1}(1-\frac{i}{M})$$<jupyter_code>import numpy as np

#expeting m > 1, if m == 1 result is 0
def pMm(M, m):
  return 1 - np.prod( 1 - np.arange(1,m, dtype=np.float64) / M )<jupyter_output><empty_output><jupyter_text>Например вероятность того что в класе из 30 человек, хотя бы у двоих совпадут дни рождения будет:<jupyter_code>pMm(365,30)
import matplotlib.pyplot as plt

xs = np.arange(2,400,2)
ys = [pMm(365,x) for x in xs]
plt.plot(xs, ys, 'b')
plt.xlabel("человек в классе")
plt.ylabel("вероятность совпадения ДР")
plt.show()<jupyter_output><empty_output><jupyter_text>Но нас интересует обратная задачаОпределить мощность множества по наличию совпадения.Событие $A_{M}$ - это событие того, что мощность исходного множества $M$. Событие $B$ - это событие того, что в выбранных (из исходного множетсва) $m$ элементов содержится хотя бы два одинаковых.  Дано: m, $P(B) \equiv p_B$ Найти: $P(A_{M}|B)$ ?   $P(B|A_{M}) = P_{coin}$ - мы уже посчитали раньше. Посчитаем $P(A|B)$ по теореме Байеса$$ P(A|B) = \frac{P(B|A)P(A)}{P(B)}$$ $P(A)$ - константа, обозначим её $a$, получим следующую формулу$$ P(A_M|B) = \frac{a}{p_B}P_{coin}(M, m)$$<jupyter_code>xs1 = np.arange(1,4000,10)
ys1 = [pMm(x, 30) for x in xs1]

xs2 = np.arange(1,100,1)
ys2 = [pMm(x, 3) for x in xs2]

fig, (ax1,ax2) = plt.subplots(1,2)

ax1.plot(xs1, ys1, "g")
ax1.set_title("m = 30")
ax1.set_xlabel("days in year")
ax1.set_ylabel("probability of coincidence")

ax2.plot(xs2, ys2, "g")
ax2.set_title("m = 3")
ax2.set_xlabel("days in year")
ax2.set_ylabel("probability of coincidence")
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1740306582506763, 'fraction_numerical': 0.032912533814247066, 'mean_word_length': 5.56508875739645, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 14, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '655401', 'license': 'MIT', 'n_tokens_mistral': 1095, 'n_tokens_neox': 1128, 'n_words': 240, 'path': 'about-one-task.ipynb', 'repo_name': 'rsalmin/drafts', 'size': '2218'}