OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 02:46

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




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

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
albobin писал(а):
Рассмотрим ситуацию.
событие A: негенерация числа A за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа B.
событие B: негенерация числа B за N попыток, означает генерацию в каждой попытке любого из остальных, в том числе и числа А.
Отсюда и отсутствие независимости.
из A может следовать 'не B' и наоборот.

А давайте упростим.;)
событие A: генерация числа A за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа B.
событие B: генерация числа B за 1 попыткe, означает негенерацию любого из остальных, в том числе и числа A.
Однако A и B независимы, в чём легко убедиться: P(A|B)=P(AB)/P(B), поскольку P(A|B)=0,P(AB)=0.


Может быть я некорректно использую слова "независимость" и пр.
Но если A и B независимы то вероятность AB равна произведению вероятностей.
То есть в нашем случае N чисел вероятность того что в 1 попытке будут два числа A и B равна (1/N)^2
Чудеса оказываются вполне вероятны :)

P(A|B)#P(A), P(B|A)# P(B) (независимости нет)
P(A|B)=P(A), P(B|A)=P(B) (независимость есть)


Последний раз редактировалось albobin Четверг, 01 Сентябрь, 2011 11:08, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 11:07 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Да, что-то я какой-то бред написал.


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

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


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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Да, распределение получается не биномиальним.
Возьмем m чисел. Существует (n - m)^n вариантов, в которых ни одно из них не генерируется.
А вариантов, в которых не генерируется только эти числа: (n - m)^n - (n - m)(n - m - 1)^n + C(2, n - m)(n - m - 2)^n - ....
Итого, вероятность, что ровно m чисел не сгенерируется равна C(m, n)*SUM((-1)^k*C(k, n-m)*(n - m - k)^n, k= 0 ..n-m)/n^n, если я опять ничего не напутал.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 16:38 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
Да, распределение получается не биномиальним.
Возьмем m чисел. Существует (n - m)^n вариантов, в которых ни одно из них не генерируется.
А вариантов, в которых не генерируется только эти числа: (n - m)^n - (n - m)(n - m - 1)^n + C(2, n - m)(n - m - 2)^n - ....
Итого, вероятность, что ровно m чисел не сгенерируется равна C(m, n)*SUM((-1)^k*C(k, n-m)*(n - m - k)^n, k= 0 ..n-m)/n^n, если я опять ничего не напутал.

Правильно ли понял идею?
имеем к-во , где нет m чисел
для каждого из (n-m) чисел отсекаем кол-во, где нет ещё и его
ввиду пересечений множеств компенсируем двойное вычитание добавлением, и это для каждой пары из (n-m)
далее опять из-за двойных добавок компенсируем вычитанием кол-вом соответствующего множества для каждой тройки из (n-m)
и т.д.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 16:49 

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
albobin писал(а):
Правильно ли понял идею?

Правильно.
Щас ещё одна идея появилась.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Сергей Губанов писал(а):
... Сформулирую "достижение мысли" этой ветки форума. Эффективность (для построения хэштаблицы) идеальной хэшфункции равна 1-1/e. Около этого значения очень маленькая дисперсия. Поэтому при больших N совершенно бессмысленно брать сложную хэшфункцию с эффективностью, например, 0.632, если самая простая имеет эффективность 0.631 (всего на одну тысячную меньше). ...
Не могу судить с определенностью, т.к. нет сил распутывать постановку задачи, но "Поэтому" в цитате выглядит сомнительно: связываются как бэ разные вещи, no?
Малость дисперсии идеальной х.ф. -- это одно, а отклонение простой от сложной (идеальной) -- это другое.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 18:58 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
Я рассуждаю так:

1) Малость дисперсии не у хэшфункции, а у распределения количества разных случайных чисел.

2) Для случайных чисел не важно с помощью сложной или простой хэшфункции они были получены.

Поэтому всякие хэшфункции при больших N одинаково эффективны (если они вообще удовлетворяют условию хэшфункции то есть выдают равномерно "случайное" число).


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 01 Сентябрь, 2011 19:52 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Сергей Губанов писал(а):
1) Малость дисперсии не у хэшфункции, а у распределения количества разных случайных чисел.
Понятно, но распределение-то есть функция хешфункции.

Сергей Губанов писал(а):
2) Для случайных чисел не важно с помощью сложной или простой хэшфункции они были получены.
Тогда зачем вообще об этом вспоминать. Предположили, что "случайно-равномерное распределение", и конец этому делу.

Надеюсь, народ тут разобрался, что к чему...


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

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

Код:
  1                   N^N
1 ░░░░░░░░░████████████ 
2 ░░███████░░░░████████ 
3 ██░░░████░░██░░░█████ 

получается,при рассматривании вертикалей, ░ будет определять к-во отсутствующих цифр в вариантах.
мат.ожидание вычисляем, рассматривая вертикали, двигаясь по горизонтали и имеем:
мат ожидание есть отношение площади всех областей ░ к N^N, M=N(N-1)^N/N^N= N(1-1/N)^N
а отношение мат.ожидания к N,
M/N=(1-1/N)^N

Спасибо Trurl , идея появилась после чтения http://forum.oberoncore.ru/viewtopic.php?f=27&t=3554&start=80#p65190

PS. Поправил текст немного.
Если кого смущает, а зачем нужна это ерунда с разбивкой на части, то отвечу - незачем, просто для того, что бы картинка была более конкретной (этакое упорядочивание применено)

Ну и для полноты уж переведу на более "пацанский" язык.
Всем возможным последовательностям случайных чисел(1..N) длины N присвоим номера от 1 до N^N, и обозначим каждую как Xj, где j=1..N^N
Построим матрицу размерности N (вертикаль) на N^N (горизонталь) из элементов Aij, i=1..N, j=1..N^N
Aij=1 , если число i не присутствует в Xj
Aij=0 , если число i присутствует в Xj
для любого i сумма всех Aij, где j=1..N^N ( по горизонтали) равна (N-1)^N (кол-во всех Xj образованных без числа i)
сумма всех Aij по всей матрице S= N(N-1)^N
обозачим как Sj сумму всех Aij, где i=1..N (сумма по вертикали), т.е. Sj=кол-ву отсутствующих чисел из диапазона 1..N в последовательности Xj
мат.ожидание M (то что нас интересует в рассматриваемом эксперименте) будет равно сумме всех Sj/N^N, где j=1..N^N
вынося 1/N^N за скобки и суммируя все Sj получим M=S/N^N=N(N-1)^N/N^N=N(1-1/N)^N
а отношение M/N=(1-1/N)^N


Последний раз редактировалось albobin Суббота, 03 Сентябрь, 2011 16:58, всего редактировалось 21 раз(а).

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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Вот еще формула. p(k,m) - вероятность того, что после k проб негенерированных будет m.
p(k+1,m)=p(k,m)*(n-m)/n + p(k,m+1)*(m+1)/n
(P[стало m]=P[было m]*P[m не изменилось]+P[было m+1]*P[m уменьшилось]).
Только развернуть красиво не получается.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 02 Сентябрь, 2011 08:22 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
Вот еще формула. p(k,m) - вероятность того, что после k проб негенерированных будет m.
p(k+1,m)=p(k,m)*(n-m)/n + p(k,m+1)*(m+1)/n
(P[стало m]=P[было m]*P[m не изменилось]+P[было m+1]*P[m уменьшилось]).
Только развернуть красиво не получается.


Может быть помог бы направленный граф с весами переходов (вероятность). Тут был у меня вариант.
N узлов отражает кол-во несгенерированных
обозначены как N-1, N-2, ... 2, 1,0
переход (N-j) -> (N-j) вес = j/N
переход (N-j) -> (N-j-1) вес = (N-j)/N

в итого надо сделать N-1 шаг по графу начиная с узла (N-1)

для наглядности удобно развернуть в виде сетки, двигаться по которой можно либо вправо, т.е (N-j)->(N-j)
либо вниз (N-j) ->(N-j-1)
ограничена сетка диагональю (N-1 шагов)

но там тоже комбинаторика ( утомительно)


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
albobin писал(а):
но там тоже комбинаторика ( утомительно)
Гы...

(Где-то наш знаток Галков...)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 02 Сентябрь, 2011 10:42 

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

Вполне допускаю, что там можно применить какой-то другой мат.аппарат, но он мне не известен :(
Уместнее было бы сказать: "но там мне видится только комбинаторика (утомительно)"


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
albobin писал(а):
Info21 писал(а):
albobin писал(а):
но там тоже комбинаторика ( утомительно)
Гы...
Вполне допускаю, что там можно применить какой-то другой мат.аппарат
Да нет, речь о ней родимой.


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
albobin писал(а):
переход (N-j) -> (N-j) вес = j/N
переход (N-j) -> (N-j-1) вес = (N-j)/N
Баян.
viewtopic.php?p=65010#p65010
viewtopic.php?p=65012#p65012
viewtopic.php?p=65013#p65013


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

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Сергей Губанов писал(а):
albobin писал(а):
переход (N-j) -> (N-j) вес = j/N
переход (N-j) -> (N-j-1) вес = (N-j)/N
Баян.
viewtopic.php?p=65010#p65010
viewtopic.php?p=65012#p65012
viewtopic.php?p=65013#p65013


Не пытаюсь завладевать приоритетом. :)
Но и сказать, что формулки срисованы, не могу.
"Было у меня" означает рисовалось давече на бумаге, но было отброшено.
Сорри, если ненароком нарушил "чайные церемонии" :)


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

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
Сергей Губанов писал(а):
Баян.
А где ясно сформулирована исходная проблема? Просьба первый пост не предлагать :)


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

Зарегистрирован: Понедельник, 28 Ноябрь, 2005 10:28
Сообщения: 1428
Да какая проблема? Здесь просто беседы о вероятности.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Пятница, 02 Сентябрь, 2011 15:59 

Зарегистрирован: Пятница, 20 Июль, 2007 17:26
Сообщения: 710
Откуда: Псков
Trurl писал(а):
Да какая проблема? Здесь просто беседы о вероятности.

А как же формула для мат.ожидания в обсуждаемом "эксперименте" :)

Меня лично интересовало как получить (или обосновать интуитивно понятную) формулу для мат.ожидания в неком "'эксперименте"
Не претендуя на ясность, из начала сообщения можно понять о каком http://forum.oberoncore.ru/viewtopic.php?f=27&t=3554&start=40#p65126
Но всё равно, первое сообщение С.Губанова это основное, там главное "почему?"


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

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


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

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


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

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