шары в урне: какова вероятность, что в урне нет черных шаров

[ha]

Посмотрим на худший случай - в урне лишь один черный шар. Мы хотим, чтобы с вероятностью не меньше 99% мы при тестировании нашли хотя бы один черный шар. Если мы не возвращаем шары, то отсюда немедленно следует ответ - нужно извлечь не менее 99% всех шаров.

Т.е. для обоснования абсолютной правильности программы с уверенностью 99% нужно подать на вход 99% всех возможных входных данных. Вот только если вы смогли подать на вход 99% всех возможных входных данных, кто вам мешает еще немного поднапрячься и подать на вход все 100% .

[Splendid]

шаров черных в урне может не быть вообще...
Как доказать, что их нет?
Сколько шаров из урны нужно вытащить, чтобы с уверенностью 90% сказать, что черных шаров там нет?

[worm2]

Splendid писал(а):

Сколько шаров из урны нужно вытащить, чтобы с уверенностью 90% сказать, что черных шаров там нет?

90% от всего числа имеющихся шаров.

[Narn]

Brukvalub писал(а):

Я бы выбрал некую априорную вероятность обнаружения ошибки при однократном тестировании программы. Тогда понятно, что речь идет об испытаниях по схеме Бернулли, и можно задаться вопросом: каково минимальное число испытаний, сделав которые и не получив ошибки, можно с вероятностью, не меньшей, чем р, утверждать, что ошибок нет.

Только вероятность, ИМХО, можно брать не априорную, а вполне точную.

Допустим, я написал программу вычисления суммы двух чисел:

var
  a,b: integer;
  c : longint;
begin
 {получаем как-нибудь a,b, из файла, readln, и т.п.}
  c:=a+b;
 {выводим как-нибудь результат}
end.

Специально не пишу readln(a), ..., чтобы избежать вопросов "а что, если пользователь ввел -00,23-55". В спецификации программы прописано, что складывать она умеет числа из $[-32768, 32767] \cap \mathbb{Z}$.

Заказчик кода не видит и мне не верит. Я говорю - хорошо, генерируем случайные входные данные, испытываем на них программу. Понятно, что если программа валится на $n$ возможных входных данных, то вероятность попасть хотя бы на один такой набор в $N$ тестах считается легко (всех возможных входных параметров, очевидно, $2^{32}$, $p =\frac{n}{2^{32}}$, etc). В такой ситуации, может, и можно говорить о чем-то более-менее математически строго. Но практически это очень сложно реализовать даже для вещественных типов (надо точно знать их мощность), плюс вопросы точности, и т. п. Но если известно количество всех возможных входных данных (а для компьютера оно всегда конечно), то теоретически такую задачу решать можно, нес па?

[Splendid]

gris писал(а):

Опять же, если мы рассматриваем классическую урновую схему, то задачу можно поставить так: В урне N шаров. Достается наугад n. Они все белые. Найти вероятность того, что в урне все шары белые.
При малых N это задача на формулу Байеса.
При больших N нужно пользоваться интегральными теоремами.

Хорошо, если эта постановка правильная, то как такую задачу решить при больших N? Какие именно интергальные теоремы?

[gris]

Для больших N и малых n эта вероятность будет очень маленькой. Если в урне миллиард белых шаров, то никакие интегральные теоремы не обратят внимания на пару-тройку черных.

На самом деле, я даже и не знаю решения этой задачи

Да и не она же вас интересует. Вы бы почётче сформулировали именно ту задачу, которую собирались решать изначально. Так четко и подробно, чтобы никто не мог придраться ни к одному слову.

[Splendid]

в том то и дело, что задача уже сформулирована максимально четко и подробно. Это все условия, больше их нет и надо решать так. Вот:(

[gris]

В урне N белых и чёрных шаров. Испытание состоит в том, что из урны без возвращения вынимается n шаров и определяется количество чёрных. После этого шары возвращаются в урну. Всего проведено m испытаний, в результате которых не было вынуто ни одного чёрного шара. Определить вероятность того, что в урне все шары белые.
Так?

Просто если рассуждать нестрогo, по-обывательски, то я бы подошёл бы к этому вопросу так:
У меня не вынулось ни одного чёрного шара. Значит (при соответствующих N,n и m) их в урне очень мало, может быть и вовсе нет.Допустим, что есть ровно один. Тогда вероятность того, что я его обнаружу в m испытаниях равна

$ 1 - (1-\frac n N)^m$.

И я бы это число принял за приближение вероятности того, что чёрных шаров в урне нет.
Пример: 200 шаров, вынул 50 белых. Вероятность того, что чёрных шаров нет - 0,25.
200 шаров, 10 раз вынул 50 белых. Вероятность того, что чёрных шаров нет - 0,94.

Но можно и так. По формуле Байеса. Я устанавливаю априорные вероятности 0.5 - что в урне все шары белые, 0.5 - что есть один чёрный. Вероятность того, что в урне больше одного чёрного шара, я считаю пренебрежимо малой. При первом предположении вероятность того, что все шары будут белыми, равна 1; при втором - $ (1-\frac n N)^m$. Полная вероятность равна $ 0.5*(1 + (1-\frac n N)^m$. Ну и наконец, посчитаем апостериорную вероятность того, то в урне все шары белые.
Это $ 1 / (1 + (1-\frac n N)^m$

Видно, что при достаточно большом объеме выборки n и/или количестве испытаний m, обе вероятности мало отличаются. Хотя всё это может показаться притянутым за уши, но на практике должно работать.

[Splendid]

gris
Спасибо большое! Надо осмыслить:)