Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 3 из 3 |
[ Сообщений: 26 ] | На страницу Пред. 1, 2, 3 |
|
Автор | Сообщение | |
---|---|---|
smer4 |
|
|
mysz писал(а): smer4 А я не верю в вашу формулу. Ничего личного, просто неправдоподобно. Потому превращать ее мне ни во что не хочется. Нет, ну может, вы обоснуете, конечно. Я решил графически, рассматривая позиции, не знаю как сюда выложить картинку Допустим мы стоим в позиции P(k:n) которая означает что после n выбора чисел мы выбрали k уникальных чисел из возможных m с повторениями Дойти сюда мы можем двумя путями. На прошлом шаге было либо позиция P(k:n-1) то есть мы уже тогда выбрали k уникальных чисел и новое - это одно из выбранных. Либо была позиция P(k-1:n-1) то есть мы тогда выбрали k-1 уникальных чисел а выбираем новое. Если у нас есть k-1 выбранных чисел из m, мы вытягиваем ещё одно из всех возможных m, то мы можем вытянуть новое с вероятностью (m-k+1)/m и выбрать то же самое с вероятностью k/n Соответственно, шаг с вероятностью P(k:n-1)* k/m или шаг с вероятностью P(k-1:n-1) * (m-k+1)/m те P(k:n) которые выходят за границы возможных вариантов равны 0 итого имеем P(k:n) = P(k:n-1)* k/m + P(k-1:n-1) * (m-k+1)/m В некоторых случаях формулу можно схлопнуть, например если хитро удаётся посчитать сумму по всем путям я так получал биноминальное, гипергеометрическое и т.п. Но в этой задаче не получается у меня по крайней мере схлопнуть разные пути в одну красивую формулу. Я бы хотел это решить как- то производящей функцией но тут вопрос в том что в рекурсии меняются 2 переменные а не одна как обычно в ряде Добавил Вот смотрите какое тут отличие от биноминального. Тогда, в P(k:n) я могу перейти из P(k:n-1) с вероятностью (1-p) - последний эксперимент неудачный и из P(k-1:n-1) с вероятностью p - последний эксперимент удачный итого имеем для биноминального P(k:n) = P(k:n-1) (1-p) + P(k-1:n-1) *p если это развернуть, то произведение по разным путям будет одинакого, а всего будет путей - биномиинальный коэфициент. В задаче выше , путей тоже в биноминальный коэфициент, но произведение вдоль каждого разное. |
||
Вернуться к началу | ||
mysz |
|
|
smer4 писал(а): итого имеем P(k:n) = P(k:n-1)* k/m + P(k-1:n-1) * (m-k+1)/m А вы пробовали проверить эту формулу, скажем, для k=3, n=4, m=3? Или даже так: k=2, n=3, m=2. Наверное, даже проще. |
||
Вернуться к началу | ||
smer4 |
|
|
mysz писал(а): smer4 писал(а): итого имеем P(k:n) = P(k:n-1)* k/m + P(k-1:n-1) * (m-k+1)/m А вы пробовали проверить эту формулу, скажем, для k=3, n=4, m=3? Или даже так: k=2, n=3, m=2. Наверное, даже проще. def p(k,n,m): результат 1.0 Всё правильно для P(3,4,3) = 0.4444444 недостаток этой рекурсии в том что даже хешируя известные значения P будет время O((k-1)*(n-1)-1)~O(n^2) посчитаем просто так P(1,2,3) = 1/3 - первый выбор случайный а второй тот же самый с вероятностью 1/3 P(2,2,3) = 2/3 - единственный другой вариант для 2 выборов P(2,3,3) = 1/3*2/3+2/3*2/3 = 2/3 - туда можно попасть двумя путями с предыдущих позиций P(3,3,3) = P(2,2,3)*1/3 = 2/9 P(3,4,3) = P(2,3,3) * 1/3 + P(3,3,3) * 1 = 4/9 Шагов O((3-1)(4-1)-1) = O(5) p(2,3,2) = 0.75 |
||
Вернуться к началу | ||
mysz |
|
|
smer4
Понятно. У нас просто разные обозначения. Вернее, обозначение одно, смысл разный. Для вашей вероятности действительно лучше иметь три параметра, хоть меняются лишь два из них. Ну все нормально у вас, рабочий алгоритм. Чего же лучше. То есть можно понять, что лучше для целей задачи: как выбирать маршрут, чтобы вероятность росла. И это будет даже интереснее, чем получить замкнутое выражение для вероятности. Кстати, производящие функции бывают и в виде рядов по двум переменным, если уж очень хочется. Но чем меньше - тем лучше, конечно. Дело-то в том, что значения другого все равно не выйдет в итоге - если уж выползали числа Стирлинга, то снова выползут. Мне кажется, или я сейчас ничего нового для вас не пишу? |
||
Вернуться к началу | ||
smer4 |
|
|
mysz писал(а): smer4 [math]S(m,n)[/math] -- число Стирлинга второго рода. https://mathworld.wolfram.com/StirlingN ... dKind.html Вы хотите формулу (10). Рекурсия - в формуле (19). С ее помощью можно посчитать, как выглядит рекурсия для вероятностей. не, для меня "число Стирлинга" это настолько новое что я не понял, надо будет изучить. Тогда получается что так можно будет выразить вообще любую задачу из рекурсивной |
||
Вернуться к началу | ||
MihailM |
|
|
smer4 писал(а): не знаю как сюда выложить картинку Это очень просто, однако кнопка расположена неудачно и заметить ее трудновато) Она находится сразу под окном в котором вы набираете сообщение, слева. Называется "Добавить сообщение". Как нажмете сразу поймете, что делать. |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3 | [ Сообщений: 26 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Нахождение медианы из количества чисел | 5 |
535 |
12 окт 2014, 13:20 |
|
Вопрос бесконечности количества простых чисел
в форуме Размышления по поводу и без |
10 |
372 |
11 янв 2020, 15:50 |
|
Генератор случайных чисел
в форуме Размышления по поводу и без |
38 |
635 |
05 июн 2022, 23:57 |
|
Идея случайных чисел
в форуме Теория чисел |
2 |
463 |
21 мар 2017, 17:52 |
|
Формула случайных чисел
в форуме Начала анализа и Другие разделы школьной математики |
6 |
694 |
17 окт 2017, 07:42 |
|
Предсказывание случайных чисел
в форуме Палата №6 |
71 |
9207 |
17 сен 2015, 20:21 |
|
Генераторы случайных чисел дисперсия
в форуме Теория вероятностей |
0 |
361 |
22 апр 2018, 14:26 |
|
Расчет чисел
в форуме Размышления по поводу и без |
12 |
605 |
18 сен 2017, 13:35 |
|
Генерация случайных чисел и обработка данных | 2 |
223 |
10 янв 2023, 18:23 |
|
Генерация случайных чисел по геометрическому распределению
в форуме Комбинаторика и Теория вероятностей |
15 |
479 |
17 дек 2022, 23:45 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |