OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Четверг, 28 Март, 2024 20:23

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 103 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.
Автор Сообщение
СообщениеДобавлено: Пятница, 26 Август, 2011 11:39 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Trurl писал(а):
Сергей Губанов писал(а):
Вероятность того что все числа разные равна (N-1)! * (1/N)^(N-1), то есть практически нулевая при больших N.
У меня получается N!/N^N. Всего отображений N^N, из них N! - перестановки.
Так это одно и тоже: N!/N^N = (N-1)! * (1/N)^(N-1)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 26 Август, 2011 12:07 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Так, ну их распределения, работаем с матожиданиями.
Пусть X(k) - количество совпадений.
X(1) =0.
X(k+1)= X(k)+(k-X(k))/n = X(k)(1-1/n)+k/n.
Разворачиваем и подставляем k=n.

X(n)=SUM(k/n*(1 - 1/n)^(n - k - 2), k= 1..n-1) = n*(1 - 1/n)^(n-1).

lim X(n)/n = 1/e.


Последний раз редактировалось Trurl Пятница, 26 Август, 2011 12:34, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 26 Август, 2011 12:13 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Сергей Губанов писал(а):
Так это одно и тоже: N!/N^N = (N-1)! * (1/N)^(N-1)


Действительно. :?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 26 Август, 2011 14:28 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Численный эксперимент для N=25, 50, 100 и 200. Распределение количества разных N случайных чисел из диапазона 1..N.
Вложение:
phenom63.png
phenom63.png [ 14.16 КБ | Просмотров: 6546 ]
Горизонтальная ось отнормирована на N, так что всё кучкуется к 0.63. Нормировка по вертикальной оси у меня хромает, её не уточняю.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Суббота, 27 Август, 2011 10:15 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Очень интересно!
У меня подтверждается опытным путем на другой задаче.
Есть решетка размером L*L. Случайным образом очередные координаты узла. L > 1000 всегда.
Опытным путем я отловил, что примерно до 0.6 можно особо не заморачиваться проверками на совпадение.
А вот после... :)
При том, что в качестве датчика случайных чисел использовался вихрь Мерсенна.
Спасибо за формулу!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Воскресенье, 28 Август, 2011 22:26 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Хотелось бы уточнить, есть ли возражения?
В случае если генерим N раз случайное число из диапазона 1..N то,
1. для любого из чисел 1..N вероятность того, что ни разу оно не выпадет будет выражаться формулой
((N-1)/N)^N или (1-(1/N))^N (кому как нравится)
и сразу же следует
2. отношения мат.ожидания кол-ва ни разу не выпавших чисел к N или, в другой формулировке,
отношения мат.ожидания кол-ва повторных выпадений чисел к N
будет выражаться той же самой формулой.
Я тут было засомневался в том, а правильно ли делать вывод 2. сразу же из 1. , но потом на досуге не нашёл опровержений.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 10:53 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Только помогите разобраться в формулировке: вероятность того, что оно ни разу не выпадет.
Вероятность выпадения любого числа из N равна 1/N - это очевидно.
Тогда вероятность невыпадения равна 1-1/N - я правильно рассуждаю?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 11:04 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Валерий Лаптев писал(а):
Только помогите разобраться в формулировке: вероятность того, что оно ни разу не выпадет.
Вероятность выпадения любого числа из N равна 1/N - это очевидно.
Тогда вероятность невыпадения равна 1-1/N - я правильно рассуждаю?


Если вопрос ко мне, то - да ( при единичном "бросании")
N раз не выпало -соответственно в степени N


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 11:05 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
albobin писал(а):
Валерий Лаптев писал(а):
Только помогите разобраться в формулировке: вероятность того, что оно ни разу не выпадет.
Вероятность выпадения любого числа из N равна 1/N - это очевидно.
Тогда вероятность невыпадения равна 1-1/N - я правильно рассуждаю?


Если вопрос ко мне, то - да ( при единичном "бросании")
N раз не выпало -соответственно в степени N

Ну, в степени - это понятно. Потом к пределу - и имеем отличное число 1/e
Спасибо!


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 12:37 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Тогда получается, что вероятность НЕ повторения равна 0.36 (1/е), а вероятность повторения - 0.63.
А должно быть вроде наоборот по сообщениям Сергея.
Или я где-то не догоняю?
Ага!
Вероятность выпадения первых N неповторяющихся чисел P(N) = N!/N^N.
Или не так?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 13:17 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Надо разделить ситуации, итоговую, так сказать, и моментальную.
Если очень огрубить, то после 100 бросаний имеем 63 выпавших различных числа, 37 ни разу не выпавших ( а значит столько же повторов)
а вот если делать 101 бросок, то вероятность повтора в этом броске будет 0.63.
Сразу оговорюсь, я не мат.спец и потому все мои объяснения носят рабоче-крестьянский характер :)
PS.
это при N=100


Последний раз редактировалось albobin Понедельник, 29 Август, 2011 13:39, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 13:19 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Большое спасибо!
Но спецов хотелось бы послушать.
Иначе мои рабоче-крестьянские мозги в раскоряку: из 100 бросков выпало 63 и НЕ выпало 37! Это как?... :)
Может быть? потому, что считаем из N >> 100?


Последний раз редактировалось Валерий Лаптев Понедельник, 29 Август, 2011 13:55, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 13:40 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Это спасибо С.Губанову.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 13:44 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Валерий Лаптев писал(а):
Вероятность выпадения первых N неповторяющихся чисел P(N) = N!/N^N.
Или не так?

Не совсем.
Это было ответвление в теме. А какова вероятность, что все числа из диапазона 1..N будут различными при N бросаниях"


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 14:38 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Валерий Лаптев писал(а):
Большое спасибо!
Но спецов хотелось бы послушать.
Иначе мои рабоче-крестьянские мозги в раскоряку: из 100 бросков выпало 63 и НЕ выпало 37! Это как?... :)
Может быть? потому, что считаем из N >> 100?

Рассматриваем генерацию N случайных чисел из диапазона 1..N
Некоторые числа из диапазона ни разу не сгенерились, некоторые один раз, а некоторые больше чем один раз.
Если в итоге K чисел (различных) ни разу не появились, то такое же кол-во K каких то других чисел были сгенерированы более чем один раз (повторы).
Для любого из N чисел можно утверждать, что вероятность того, что это число ни разу не будет сгенерировано равна (1-(1/N))^N
Помножив на N можно получить мат.ожидание (M) кол-ва ни разу не сгенерированных чисел (или повторов).
Или , в другом варианте того же, имеем формулу: отношение M/N=(1-(1/N))^N
Я понимаю, что здесь может быть нужны более строгие рассуждения, но это удел других людей.
Ну а насчет приведённых конкретных кол-в (63 и 37 в случае когда N=100) так это же что-то вроде упрощения (=вульгаризация).
Кстати, в случае N=2, мат.ожидание кол-ва повторов будет = 1/2
PS.
Чувствую, что время моё уже давно истекло, имеется явный перебор.
А что скажет начальник транспортного цеха? :)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 15:38 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Кажись дошло.
0.63 - это вероятность того, что среди первых 100 чисел не более 63 уникальных.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 15:50 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Валерий Лаптев писал(а):
Кажись дошло.
0.63 - это вероятность того, что среди первых 100 чисел не более 63 уникальных.

Боюсь, что не так.
В другой формулировке: вероятность того,что кол-во уникальных чисел не превысит мат.ожидание, даст другую величину (слёту ставлю на 1/2, но могу ошибаться, естественно)


Последний раз редактировалось albobin Понедельник, 29 Август, 2011 16:15, всего редактировалось 2 раз(а).

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 16:07 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Валерий Лаптев писал(а):
Но спецов хотелось бы послушать.

Присоединяюсь.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 16:22 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2449
Откуда: Россия, Томск
Валерий Лаптев писал(а):
Кажись дошло.
0.63 - это вероятность того, что среди первых 100 чисел не более 63 уникальных.

Я так понимаю, что для диапазона 1..100 при генерации 100 случайных чисел наиболее вероятно, что 63 будет уникальных, и 37 повторятся. 0.63 - это наиболее вероятная доля уникальных чисел. Вероятность того, что доля уникальных чисел будет больше или меньше 63% сильно падает при удалении от этого значения. Т.е. вероятность получить 60% или 70% уникальных числе будет ниже, чем вероятность получить 63%.

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Понедельник, 29 Август, 2011 16:28 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Александр Ильин писал(а):
В общем, чем жёстче условия на последовательность, тем меньше вероятность соответствия ей, и вероятности эти надо по-разному высчитывать.

Вероятность появления любой конкретной последовательности чисел одинакова и равна (1/N)^N
PS.
Это только для уточнения, что равновероятно к примеру выпадение конкретного числа N раз и выпадение последовательности 1,2,3 ... N


Последний раз редактировалось albobin Понедельник, 29 Август, 2011 16:38, всего редактировалось 1 раз.

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

Часовой пояс: UTC + 3 часа


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

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


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

Найти:
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB