[Trotil]

Задачка, то и дело возникающая в работе, но не знаю, как её точно решать.

Есть некоторое множество состояний объекта А. Число состояний можно обозначить, как |А|.

И есть функция f:A ->{0,1}, которая проверяет, хорошее состояние объекта, или плохое.

Задача: выявить как можно больше плохих состояний или дать оценку, что плохих состояний нет.
Проблема: все состояния физически проверить невозможно, для этого нет необходимых вычислительных мощностей (даже с учётом обработки данных на вычислительном кластере).
Пусть плохие состояния распределены случайным образом, равномерно.

Вопрос. Пусть мы проверили долю состояний p<1 и обнаружили, что плохих состояний там k штук (k может быть и нулём.). Что можно сказать про вероятность того, что на непроверенном участке плохих состояний - m штук?

Частный случай: проверили 1/1000 состояний, ничего не нашли. С какой вероятностью на оставшейся части есть
0 плохих состояний, 1 плохое состояние, 2 плохих состояния и т.д.?

----------------

Похожую задачу можно сформулировать про опросы. Опросили 5% населения, из них поддерживают некоторое нововведение 30%, не поддерживают 60%, затрудняются ответить 10%. Что можно сказать про мнение населения в целом? Понятно, что для 100% числа могут отличаться. С какой вероятностью, 100% населения поддерживают нововведение, скажем, в доверительном интервале (30-5%, 30+5%). Как такая задача решается в общем виде?

Попыток не будет, ибо это не учебная задача. Статистику в отличие от теорвера в институте преподавали весьма скверно.

@темы: Теория вероятностей

Comments

[Integr@l]

Пусть плохие состояния распределены случайным образом, равномерно.

Нет оснований для этой гипотезы.
Задача довольно хорошо сформулирована. Речь об интервальной оценке доли при случайной бесповторной выборке. Здесь даже нелюбимый отдельно взятыми проФФеСорами учебник или задачник Гмурмана подойдёт.
Но! Обратите внимание. Оценка основана на интегральной теореме Муавра–Лапласа. При этом интервал для оценки выбирается симметричным эмпирической относительной частоте, и вычисленные таким образом границы интервала могут выйти за пределы [0; 1]. В таком случае корректно будет использовать формулу для интервальной оценки параметра p биномиального распределения. Границы интервала при этом не симметричны. Естественно, в любой случае оценка делается с наперёд заданным уровнем надёжности (доверительной вероятности, уровнем значимости).
Источник. Например, Ефимов А. В.

[Гость]

Попыток не будет, ибо это не учебная задача.

ГОСТ Р 50779.*

[Trotil]

Нет оснований для этой гипотезы.

Почему? Исходная задача состоит в покрытии некоторого кода тестами и проверки на правильность его выполнения.
Поскольку код пишет человек, точнее, группа разработчиков, то они могут ошибиться где угодно и сколько угодно раз.

А если не задавать закон распределения, то решить начальную задачу будет еще сложнее.

[Гость]

Поскольку код пишет человек, точнее, группа разработчиков

Контрольные примеры не готовятся?

[Trotil]

Готовятся. Но это лишь начальный этап.
Несколько тестов изначально есть непосредственно у разработчика, которыми он проверяет во время разработки правильность функционирования, и по необходимости допиливает код.

Потом это дело передаётся на более массивную обработку случайными данными на входе.

[true-devil]

Задача про доверительные интервалы для схемы Бернулли - поскольку общий объём "генеральной совокупности" велик по сравнению с выборкой, можно считать выбор повторным (от вынимания одного вероятность для следующего практически не меняется), и испытания - схемой Бернулли. Если число успехов в выборке е слишком мало и не слишком велико - скажем, для примера выше 30% - это как раз не слишком мало и не слишком велико, то интегральная теорема Муавра - Лапласа даёт ответ:

Пусть есть `n` элементов выборки `X_1, ..., X_n` со значениями 0 и 1, - случайные величины с распределением Бернулли с неизвестной вероятностью успеха `p`. Наблюдается `overline X=(sum X_i)/n` - число успехов (число единиц), `1-epsilon` - заданный уровень доверия, `tau` - квантиль уровня `1-epsilon/2` стандартного нормального распределения, т.е. такая точка, что для величины `Z` со стандартным нормальным распределением `P(-tau < Z < tau)=1-epsilon`.

Тогда `P(overline X - tau * sqrt(overline X * (1-overline X))/sqrt(n) < p < overline X + tau * sqrt(overline X * (1-overline X))/sqrt(n) ) approx 1-epsilon`.

Это приближение удовлетворительно работает при значениях `n* overline X * (1-overline X)` не менее 5-6, лучше больше.
Эта же формула позволяет решать обратную задачу - по данному доверительному интервалу, при известной средней и известном объёме выборки искать (приближённо) вероятность `1-epsilon` накрытия этим интервалом неизвестного значения `p`.

Если же наблюдаемое доля успехов мала (или, наоборот, близка к 1), используют другой подход к построению доверительных интервалов: так называемый метод Клоппера - Пирсона. Если мы нарисуем набор вероятностей биномиального распределения `B_{n,p}` числа единичек в выборке, то это будет шапочка с максимумом в районе `np`. С ростом `p` шапочка уползает вправо, и при каждом значении `sum X_i = k` вероятность (назову её `Prob2`) получить не более `k` успехов с ростом `p` уменьшается, а вероятность получить не менее `k` успехов (`Prob1`) - увеличивается.

Если наше число успехов `sum X_i = k` не ноль и не единица, и мы хотим получить границы `p_1 <= p <= p_2` с заданным уровнем доверия `1-epsilon`, то обычно берут по половине епсилон для каждого оставшегося кусочка `p < p_1`, `p > p_2`, и решают два уравнения:
1) для поиска `p_1` берут такое самое маленькое `p` такое, что `Prob2 >= epsilon/2`. Нужно в точности приравнять `Prob1` к половине эпсилон:
`Prob1 = sum_{i=k}^n C_n^i p_1^i (1-p_1)^{n-i}=epsilon/2`.
2) для поиска `p_2` берут такое самое большое `p` такое, что `Prob2 >= epsilon/2`. Нужно приравнять `Prob2` к половине эпсилон:
`Prob2 = sum_{i=0}^k C_n^i p_2^i (1-p_2)^{n-i}=epsilon/2`.

Не вручную, понятно, но даже Excel'я обычно хватает.

Вместо половинок от эпсилон можно брать иные доли - это зависит от того, насколько мала или велика доля успехов. Если, скажем, у нас в `n` испытаниях 0 (или совсем мало) успехов, то интервал для `p` должно брать "от забора и до обеда", т.е. от 0 и до какого-нибудь `p_{max}`. Тогда `Prob1` берут нулём, а `Prob2` приравнивают к эпсилон. Для числа успехов `k=0` границу интервала `p_{max}` находим из `(1-p_{max})^n=epsilon`, и интервал получится `0 <= p <= p_{max}`.

[true-devil]

Trotil:

Пусть плохие состояния распределены случайным образом, равномерно.

Integr@l:

Нет оснований для этой гипотезы.

Условное распределение набора номеров успешных испытаний при фиксированном числе успехов, разумеется, равномерное.

[Integr@l]

Условное распределение набора номеров успешных испытаний при фиксированном числе успехов, разумеется, равномерное.

Премного благодарен за просветление. Я в силу своего невежества полагал, что вероятности выявления «плохих» номеров имеют распределение (при большом числе испытаний) близкое к биномиальному (асимптотически при неизвестных точечных оценках — к распределению Стьюдента или нормальному).
И к сожалению, упустил в топике тот факт, что число успехов фиксировано. Не будете ли столь любезны процитировать?

[mpl]

Или спокойное обсуждение или - в учительскую... с родителями.

[Integr@l]

Давайте по существу.
ТС уточняет, что

поскольку код пишет человек, точнее, группа разработчиков, то они могут ошибиться где угодно и сколько угодно раз

Можно ли на основании этого утверждать, что число успехов фиксировано, а распределение — равномерное?
Меня учил в университете профессор Бродецкий Г. Л., что теория вероятностей — наука точная.
Или Геннадий Леонидович ошибался?

[mpl]

Могу предположить.
Сначала определяется, на основании тех или иных данных, гипотеза о характере распределения успехов/неуспехов. Далее ...
По крайней мере в стохастическом тестировании не отдается предпочтение одному характеру распределения.
Точнее не скажу, давно не заглядывал в такую литературу.

[true-devil]

Какие эмоции на пустом-то месте, а? Ещё раз. В каждом наблюдении возможны нолик и единичка, никаких иных результатов. В этой ситуации равносильны две модели:
1) испытания независимы в совокупности, и единичка в каждом наблюдается с одной и той же вероятностью (это называется "схема Бернулли"),
2) при каждом числе испытаний `n` и при любом фиксированном числе успехов `nu_n=k` вектор `n_1 < ... < n_k` номеров успешных испытаний имеет равномерное распределение: `P((n_1,...,n_k)=(i_1,...,i_k) | nu_n=k) = 1/C_n^k`, `i_1< ... <i_k`.

Например, распределение номера неуспеха в `n` испытаниях схемы Бернулли, если нам известно, что он один, равномерное на множестве `{1,...,n}`.
Вам это доказать?

Когда говорят "плохие состояния распределены случайным образом, равномерно", всегда стоит понимать, что речь идёт об условном распределении при фиксированном количестве таковых. Умеете определить равномерное распределение случайного числа объектов иначе? Поделитесь ноу-хау. И поспокойнее.

[Integr@l]

true-devil
Отвечаю исключительно по существу Вашего комментария (по-видимому имеющего прямое отношение к обсуждаемому вопросу).
В поставленной задаче речь идёт об оценке числа (количества, частоты) успехов (неуспехов), а не о способе распределения упорядоченных последовательностей (случайного вектора):

Задача: выявить как можно больше плохих состояний или дать оценку, что плохих состояний нет.

Что можно сказать про вероятность того, что на непроверенном участке плохих состояний - m штук?

Повторю персонально для Вас. Из того, что

Условное распределение набора номеров успешных испытаний при фиксированном числе успехов, разумеется, равномерное.

вовсе не следует, что число успехов является фиксированным (или детерминированной, не стохастической, величиной). Наоборот, это число как раз и требуется оценить с заданным уровнем надёжности.
Ваши комментарии, демонстрирующие несомненно глубокие википедийные знания равномерного закона распределения многомерных (векторных) случайных величин считаю не относящимися к существу задачи и ни на шаг не приближающими к её решению.
Ваш же переход на личности безо всяких на то оснований и даже косвенных поводов (

Какие эмоции на пустом-то месте, а?, И поспокойнее.

) расцениваю как откровенный, ничем не прикрытый флейм, на что убедительно прошу обратить внимание модераторов сообщества.
Всего доброго и крепкого Вам здоровья. Как физического, так и душевного.

[true-devil]

Повторю персонально для Вас. Из того, что Условное распределение набора номеров успешных испытаний при фиксированном числе успехов, разумеется, равномерное. вовсе не следует, что число успехов является фиксированным (или детерминированной, не стохастической, величиной). Наоборот, это число как раз и требуется оценить с заданным уровнем надёжности.

Разумеется, не следует. А каким образом "это число оценить с заданным уровнем надёжности", прочтите выше в моём комментарии. Заодно познакомитесь с методом Клоппера - Пирсона, а то на Муавре и Лапласе в связи с вопросами ТС далеко не уехать.

Вы имеете ещё что-то возразить на следующий комментарий?
------------------------
Trotil: Пусть плохие состояния распределены случайным образом, равномерно.
Integr@l: Нет оснований для этой гипотезы.

Условное распределение набора номеров успешных испытаний при фиксированном числе успехов, разумеется, равномерное.
------------------------

[Integr@l]

true-devil
Если для Вас по каким бы то ни было причинам неприемлемы мои комментарии — ради всего святого, читайте книги. Я уже написал, как можно оценить искомое число. На случай, если этот метод не описан в Вашей методической литературе вставляю формулу, и делаю это исключительно из доброго к Вам отношения:



Искренне надеюсь, что эта информация окажется полезной для Вас и Ваших студентов.
И, как говорила одна классик,

И поспокойнее

.
Ведь здоровье — это бесценный дар, который Вы ну просто обязаны беречь

Upd.
Извините великодушно, в формуле небольшая описка. Следует читать не u²/1, а u²/2.

[true-devil]

Сударь, Вы непристойно себя ведёте, мне стыдно за Вас. Откуда столько ущемлённого самолюбия? Мне не интересно меряться с Вами знаниями. Ваша формула Вилсоновского интервала мне тоже известна, и что? Вы её в задачнике Гмурмана, который рекомендовали ТС выше, нашли? А если нет, отчего Вы мне её сообщаете, а не ТС?

Что же до остальных проблем, я прокомментирую-таки вот эту ранее не понятую мной адекватно фразу:

И к сожалению, упустил в топике тот факт, что число успехов фиксировано. Не будете ли столь любезны процитировать?

Проблема, как я вижу, в понимании того, что такое условное распределение. Покажу на простом примере.
Условие задачи. Случайная величина `xi` принимает значения 1, 2, 3, 4, 5 с равными вероятностями. Целочисленная случайная величина `eta` равномерно распределена от 1 до `xi`. Что-то требуется найти, неважно.

Фраза в условии "целочисленная случайная величина `eta` равномерно распределена от 1 до `xi`" означает дословно следующее: если на элементарном исходе `omega` значение `xi(omega)` есть число `k`, то величина `eta(omega)` принимает значения `1,...,k` с вероятностями по `1/k`. То есть `P(eta=i | xi=k)=1/k` для `i=1,..,k`, `k=1,...,5`.

Рассмотрение условного распределения при фиксированном значении `xi=k` не делает `xi` фиксированной в условии задачи, она как была случайной величиной, так и останется. Это просто единственный способ определить равномерность распределения чего-либо в случайной среде. Равномерность можно определить, только зафиксировав среду. Равномерность распределения чего-либо в случайной среде - это равномерность распределения при каждом возможном состоянии этой среды, и никак иначе.

Что же до вот этого комментария, то я его, простите, вообще не поняла:

Ваши комментарии, демонстрирующие несомненно глубокие википедийные знания равномерного закона распределения многомерных (векторных) случайных величин считаю не относящимися к существу задачи и ни на шаг не приближающими к её решению.

Задача выше давно решена - уже лет 80 как. Вы предлагаете пропускать мимо ушей неверные комментарии? Не будет этого. Человек, задающий вопрос, обычно не в состоянии отличить правильный комментарий от неправильного. Ваше возражение против равномерности распределения не лезет ни в какие ворота. Trotil описал задачу с физической точки зрения совершенно правильно: сколько бы там ни было успехов (это подразумевается), они распределены равномерно. Вот это самое "сколько бы там ни было" и означает на математическом языке "при любом фиксированном числе" оных.

[Integr@l]

Мисс!
И снова с вашей стороны флейм, и снова продолжающийся переход на личности:

Сударь, Вы непристойно себя ведёте, мне стыдно за Вас. Откуда столько ущемлённого самолюбия? Мне не интересно меряться с Вами знаниями.

Как говорят французы, «Если дама не права — извинись перед нею». Мои Вам искренние извинения за то, что осмелился отвечать (простите за тавтологию) на Ваши же ответы к моим комментариям.
Если бы Вы читали книги, то сделали бы для себя потрясающее открытие. Дело в том, что формулы Вилсоновского интервала в задачнике Гмурмана нет.
Ещё раз осмелюсь напомнить Вам, что в задаче речь идёт об интервальной оценке математического ожидания (или вероятности появления) случайной величины с неизвестными математическим ожиданием и дисперсией, а об оценке закона распределения многомерного случайного вектора. Приведенный же Вами наглядный пример равноценен примеру 2 × 2 = 4 хотя бы потому что индикаторная случайная величина X ∈ [0; 1] в обсуждаемой задаче принимает допустимые значения отнюдь не с равными вероятностями.
Заметьте также, что нигде (абсолютно нигде), кроме последнего комментария, Вы не упомянули о том, что в своих примерах ведёте речь о каждом возможном значении случайной величины.
Если для Вас

Что-то требуется найти, неважно

то, думаю, для человека, задавшего вопрос, важен результат, а не процесс наслаждения математической эквилибристикой.
Всего Вам доброго.

[Robot]

Первый раз за много лет возник конфликт такой силы между решателями.

Топик временно закрываю
Сейчас я не в состоянии вчитываться в комментарии.
Кроме того, вопрос будет обсуждаться всеми совладельцами.

---

Не буду открывать комментарии. Но поясню. Существует сообщество решателей, которое можно использовать и таким образом. Можно создать топик. Закрытый. Назвать его "Разговор с другом". При возникновении столь острых противоречий по вопросу оказания помощи ТС можно пойти попить чайку в учительскую. Куда можно пригласить и собеседника. Возможно, отсутствие публики позволит вести разговор по существу. Не заботясь о ...
События в Домодедово вызывают определенные эмоции. Столь острое обсуждение постановки задачи без участия ТС ... поиск абстрактной истины ...

ВМ

[mpl]

Из сообщества на две недели исключается Integr@l .
Основание: игнорирование предупреждения представителя администрации, нарушение правил сообщества.

ВМ.

[true-devil]

...

Поскольку тема доверительного оценивания вероятности успеха вечна, то для тех, кто будет выбирать нужную формулу из массы возможных формул для границ (а если достоверность выводов важна, это придётся делать), может быть полезна следующая ссылка.
Вот очень интересный сравнительный обзор Дасгупты и Co (один из наиболее свежих) доверительных интервалов для вероятности успеха, особенно любопытный многочисленными комментариями, в т.ч. методическими. К сожалению, на английском. Основной вопрос, который авторы разбирают - о "вероятности накрытия" интервалом параметра - в зависимости от вида интервала, от величины истинного `p` и числа испытаний `n`, это как раз тот вопрос, что задавал Trotil. Графики красивые нарисованы этой реальной вероятности накрытия для типичных уровней доверия.