ПЕРВАЯ ПРОБЛЕМА Мы имеем множество выборок значений размером k, в которых

каждый элемент может иметь только одно из N равновероятных значе-ний.

Каков должен быть минимальный размер выборки k в множестве, чтобы с вероятностью P ≥ 1/2 по крайней мере один из элементов был бы равен заранее определенному значению?
Чтобы решить проблему, мы сначала нахо-дим вероятность P, что по крайней мере один элемент равен заранее заданному значению. Затем задаем вероятность к 1/2, чтобы найти ми-нимальный размер элемента.

вероятность того, что выбран-ный элемент равен заранее заданному значению, то

Pэл = 1/N, потому что элемент может с равной вероятностью принимать любое из значений N.
Если Qэл - вероятность, что выбранный элемент не равен заранее заданному значению, то Qэл = 1 - Pэл = (1 - 1/N).
Если каждый элемент независим (справед-ливое предположение) и Q - вероятность, что ни один элемент не равен заранее заданному зна-чению, то Q = Qэлk = (1 - 1/N)k.

один элемент равен заранее опре-деленному значению, то P = 1

- Q или P = 1 - (1 - 1/N)k.
Размер выборки

Теперь мы находим минимальный размер выборки k, чтобы вероятность появления эле-мента была P ≥ 1/2:

P = 1 - (1 - 1/N)k ≥ 1/2 → (1 - 1/N)k ≤ 1/2.

Используя аппроксимацию 1 - x ≈ e-1/N при x = 1/N:

e-k/N ≤ 1/2;

e-k/N ≤ 1/2 → ek/N ≥ 2;

k/N

≥ ln(2) → k ≥ ln(2) × N ≈ 0,69 × N.


Первая проблема:

Вероятность: P = 1 - (1 - 1/N)k ≈ 1 - e-k/N.

Размер выборки: k ≥ ln(2) × N ≈ 0,69 × N.