Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу Пред.  1, 2, 3
Автор Сообщение
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 11:12 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2021, 08:25
Сообщений: 34
Cпасибо сказано: 7
Спасибо получено:
10 раз в 10 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
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

если это развернуть, то произведение по разным путям будет одинакого, а всего будет путей - биномиинальный коэфициент.

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 12:31 
Не в сети
Мастер
Зарегистрирован:
26 янв 2021, 03:04
Сообщений: 274
Cпасибо сказано: 14
Спасибо получено:
59 раз в 53 сообщениях
Очков репутации: 8

Добавить очки репутацииУменьшить очки репутации
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. Наверное, даже проще.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 13:16 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2021, 08:25
Сообщений: 34
Cпасибо сказано: 7
Спасибо получено:
10 раз в 10 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
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):
if k==0 and n==0: return 1.0
if k < 0 or k > n: return 0.0

return p(k,n-1,m)*k/m + p(k-1,n-1,m)*(m-k+1)/m

print(p(0,0,3))
print(p(1,1,3))
print(p(1,0,3))

#----

print(p(1,2,3))
print(p(2,2,3))

print(p(1,3,3))
print(p(2,3,3))
print(p(3,3,3))

#---
print("P(k,n,3)")
print(p(0,4,3))
print(p(1,4,3))
print(p(2,4,3))
print(p(3,4,3))
print(p(4,4,3))


результат

1.0
1.0
0.0
0.3333333333333333
0.6666666666666666
0.1111111111111111
0.6666666666666666
0.2222222222222222
P(k,n,3)
0.0
0.037037037037037035
0.5185185185185185
0.4444444444444444
0.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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 14:22 
Не в сети
Мастер
Зарегистрирован:
26 янв 2021, 03:04
Сообщений: 274
Cпасибо сказано: 14
Спасибо получено:
59 раз в 53 сообщениях
Очков репутации: 8

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

Кстати, производящие функции бывают и в виде рядов по двум переменным, если уж очень хочется. Но чем меньше - тем лучше, конечно.

Дело-то в том, что значения другого все равно не выйдет в итоге - если уж выползали числа Стирлинга, то снова выползут.

Мне кажется, или я сейчас ничего нового для вас не пишу? :pardon:

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 23:14 
Не в сети
Начинающий
Зарегистрирован:
11 янв 2021, 08:25
Сообщений: 34
Cпасибо сказано: 7
Спасибо получено:
10 раз в 10 сообщениях
Очков репутации: 3

Добавить очки репутацииУменьшить очки репутации
mysz писал(а):
smer4

[math]S(m,n)[/math] -- число Стирлинга второго рода. https://mathworld.wolfram.com/StirlingN ... dKind.html
Вы хотите формулу (10).
Рекурсия - в формуле (19).
С ее помощью можно посчитать, как выглядит рекурсия для вероятностей.


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

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Расчёт количества случайных чисел
СообщениеДобавлено: 01 фев 2021, 23:46 
Не в сети
Последняя инстанция
Зарегистрирован:
12 сен 2010, 12:46
Сообщений: 6078
Cпасибо сказано: 137
Спасибо получено:
1033 раз в 976 сообщениях
Очков репутации: 67

Добавить очки репутацииУменьшить очки репутации
smer4 писал(а):
не знаю как сюда выложить картинку

Это очень просто, однако кнопка расположена неудачно и заметить ее трудновато)
Она находится сразу под окном в котором вы набираете сообщение, слева.
Называется "Добавить сообщение". Как нажмете сразу поймете, что делать.

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3  Страница 3 из 3 [ Сообщений: 26 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Нахождение медианы из количества чисел

в форуме Математическая статистика и Эконометрика

Moondust

5

535

12 окт 2014, 13:20

Вопрос бесконечности количества простых чисел

в форуме Размышления по поводу и без

ammo77

10

372

11 янв 2020, 15:50

Генератор случайных чисел

в форуме Размышления по поводу и без

Dotsent

38

635

05 июн 2022, 23:57

Идея случайных чисел

в форуме Теория чисел

alligator

2

463

21 мар 2017, 17:52

Формула случайных чисел

в форуме Начала анализа и Другие разделы школьной математики

mazol90

6

694

17 окт 2017, 07:42

Предсказывание случайных чисел

в форуме Палата №6

valerchi

71

9207

17 сен 2015, 20:21

Генераторы случайных чисел дисперсия

в форуме Теория вероятностей

evs

0

361

22 апр 2018, 14:26

Расчет чисел

в форуме Размышления по поводу и без

vladhur

12

605

18 сен 2017, 13:35

Генерация случайных чисел и обработка данных

в форуме Математическая статистика и Эконометрика

garicchem

2

223

10 янв 2023, 18:23

Генерация случайных чисел по геометрическому распределению

в форуме Комбинаторика и Теория вероятностей

garicchem

15

479

17 дек 2022, 23:45


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 15


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved