в идеале это необходимо чтобы посчитать вероятность выпадения хотя бы m одинаковых чисел из диапазона {1..n} при выборке из k чисел. как это посчитать? нужна общая формула. буду очень благодарен! =)

ps. Ответ нужен через отношение числа всех подходящих комбинаций к всем возможным для выборки в k чисел. (то есть C из N по k и перемножение вероятностей не предлагать).

задан 3 Май '13 16:05

изменен 3 Май '13 16:21

falcao,Большое спасибо! )) о_O сейчас буду вдумываться и анализировать ответ)

(3 Май '13 16:55) fowl

"то есть C из N по k и перемножение вероятностей не предлагать" - Вот интересно, а в каком виде ТС предполагал увидеть ответ?...

(3 Май '13 23:10) all_exist
10|600 символов нужно символов осталось
2

Рассмотрим частный случай, когда $%n=2$%. Общее количество выборок из $%k$% чисел равно $%2^k$%. Если $%k\ge2m-1$%, то в любой выборке будут присутствовать $%m$% одинаковых чисел. Если $%k\le m-1$%, то ни в какой выборке $%m$% одинаковых чисел не найдётся. Пусть $%m\le k\le2m-2$%. Рассмотрим случай, когда в выборке имеется $%s$% единиц и $%t$% двоек ($%s+t=k$%). Таких выборок имеется ровно $%C_k^s=C_k^t$%. Подсчитаем число неудачных выборок, то есть таких, при которых $%s\le m-1$%, $%t\le m-1$%. Второе неравенство превращается в $%k-m+1\le s$%. Таким образом, получается сумма $$C_k^{k-m+1}+C_k^{k-m+2}+\cdots+C_k^{m-1}.$$ Отсюда легко выразить и число всех остальных выборок (для которых $%m$% одинаковых чисел найдутся): оно равно $$2(C_k^0+C_k^1+\cdots+C_k^{k-m}).$$

Такого типа выражения, если иметь в виду их точные значения, а не асимптотику, никак не упрощаются. То есть уже для $%n=2$% ответ имеет не слишком хороший вид. Прежде чем рассматривать формулы для общего случая, хотелось бы узнать, является ли такая форма ответа сколь-нибудь полезной.

Добавление. Пусть $%n=53$%, $%k=6$%. Выборок в этом случае будет $%53^6=22164361129$% (около $%20$% миллиардов). Подсчитаем количество выборок, у которых имеется $%m$% одинаковых чисел при $%m=6,5,4,3$%.

1) $%m=6$%. Очевидно, что таких выборок, когда все числа одинаковы, ровно $%53$%.

2) $%m=5$%. Те выборки, которые были подсчитаны в предыдущем пункте, учитывать не будем. Их надо будет добавить, если нас интересует количество выборок, в которых есть как минимум $%5$% одинаковых чисел. А пока сосчитаем число вариантов, где пять чисел одинаковые, а шестое от них отличается. Это будет произведение $%53\cdot52\cdot6=16536$%. Здесь имеется $%53$% способа для выбора повторяющегося числа, $%52$% -- для того, которое будет в одном экземпляре, и $%6$% способов для выбора места, которое займёт "уникальное" число.

3) $%m=4$%. Как и выше, будем рассматривать только случай, когда имеются четыре одинаковых числа, а пяти уже не найдётся. Здесь ответ равен произведению следующих чисел: $%53$% (выбор числа, встречающегося $%4$% раза), $%C_6^2=15$% (выбор двух мест из шести для двух оставшихся чисел), и $%52^2$%. Последнее -- это число способов поместить на двух фиксированных местах какие-то из $%52$% чисел. Получается $%2149680$%.

4) $%m=3$%. Здесь ситуация чуть сложнее. Как и раньше, мы считаем, что четырёх одинаковых чисел нет. Тогда надо различать две ситуации. Первая: имеется выборка типа "три плюс три", то есть какие-то три одинаковых числа перемешаны с какими-то тремя одинаковыми. Здесь получается произведение $%53\cdot10\cdot52=27560$%. Смысл такой: $%53$% способа задать то, что находится на первом месте, $%C_{5}^2=10$% способов задать оставшиеся два места из пяти, где находится то же самое; $%52$% способа выбрать то, что находится на трёх оставшихся местах.

Вторая ситуация такая: есть три одинаковых числа, а среди оставшихся трёх чисел не все одинаковы. Здесь перемножаются $%53$% (выбор троекратно повторяющегося числа), $%C_6^3=20$% (выбор трёх мест из шести для этого числа), и $%52^3-52$% (расстановка на трёх свободных местах любых из $%52$% чисел, за вычетом случая, когда все они одинаковы). Это даёт $%148989360$%.

Поскольку здесь в вычислениях легко ошибиться, то я заодно подсчитал ещё и количество выборок для $%m=2$%, $%m=1$% по тому же принципу, а потом всё сложил. Результат совпал с общим количеством, равным $%53^6$%.

Общие формулы для таких вычислений указать, скорее всего, можно, но там будут какие-то громоздкие суммы. Если это представляет интерес, то можно над этим подумать.

ссылка

отвечен 3 Май '13 16:46

изменен 4 Май '13 18:52

falcao,хотя если можно, было бы здорово узнать в общем случае). Главное чтобы можно было вычислить, зная только начальные 3 параметра. В оригинале вопрос задачи таков: Какова вероятность выбросить 3,4,5 и 6 одинаковых чисел соответственно, из диапазона 1-53 из выборки в 6 чисел ?

(4 Май '13 17:48) fowl

@fowl77: Я сейчас напишу добавление для того случая, который Вы сейчас описали. Какие-то общие формулы для вычисления задать тоже можно, но в указанном случае число $%k$% невелико, поэтому всё считается вручную.

(4 Май '13 18:10) falcao

@falcao; Премного благодарен за обширный и подробный ответ!!))

(4 Май '13 20:15) fowl

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

(5 Май '13 10:19) Urt
1

@Urt: Если иметь в виду просто суммы биномиальных коэффициентов, то их можно оценивать обычным способом, через интеграл от $%e^{-x^2/2}$%. Для более сложных случаев, наверное, требуется что-то более изощрённое. Книгу я нашёл в "колхозе", но она довольно длинная, и сходу я не нашёл там вещи, касающиеся оценок. В каких главах надо смотреть?

(5 Май '13 14:58) falcao

@Falcao, это в приложении А или Б.

(5 Май '13 15:03) Urt

@Urt: спасибо, теперь нашёл. Я на самом деле по оглавлению там и пытался смотреть, но из-за сдвига номеров страниц попал на длинные таблицы. Идея там в принципе простая: применить формулу Стирлинга с подходящей точностью.

(5 Май '13 15:15) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Где-то я уже видел эту задачу

ссылка

отвечен 3 Май '13 17:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×3,372
×2,583
×1,135

задан
3 Май '13 16:05

показан
2583 раза

обновлен
5 Май '13 15:15

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru