Этот баннер — требование Роскомнадзора для исполнения 152 ФЗ.
«На сайте осуществляется обработка файлов cookie, необходимых для работы сайта, а также для анализа использования сайта и улучшения предоставляемых сервисов с использованием метрической программы Яндекс.Метрика. Продолжая использовать сайт, вы даёте согласие с использованием данных технологий».
Политика конфиденциальности
|
|
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Прошу прощения за такое название топика ) Вот задача. На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый. Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения. Решение, пропускать числа, не попадающие в рейндж, не очень интересно. Нужно именно преобразование. Можно что-то сохранять между операциями. Но в идеале чистое математическое преобразование нужно :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:49 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Случайные числа от 0 до 9 поступают с "отрезка" (0,9) Надо сделать "отрезок" (0,5), брать случайные числа и прибавлять 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, числа целые или вещественные? если второе, то 2 + r * 5 / 9 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Gennadiy Usov Случайные числа от 0 до 9 поступают с "отрезка" (0,9) Надо сделать "отрезок" (0,5), брать случайные числа и прибавлять 2. Ну это понятно. Одинаковое распределение должно остаться. Все поступающие числа должны быть использованы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, Целые. Но операции преобразования могут быть в поле вещественных чисел, а на выходе опять целое. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:56 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 2 + r * 5 / 9 Отрезаем или округляем? Распределение гарантируется? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 11:58 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Имя пользователя1 2 + r * 5 / 9 Отрезаем или округляем? Распределение гарантируется? боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 12:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 12:41 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Прошу прощения за такое название топика ) Вот задача. На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый. Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения. Решение, пропускать числа, не попадающие в рейндж, не очень интересно. Нужно именно преобразование. Можно что-то сохранять между операциями. Но в идеале чистое математическое преобразование нужно :) Можно попробовать завести массив счетчиков от 2 до 7. И отображать диапазон random(10) на 2..7 с инкрементом. Те ячейки которые получат больше счет - имеют шанс выйти на выход с обнулением (или с вычитанием). В этом есть что-то от алгортма Брезенхема. Типа накопления ошибки. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 12:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Код: sql 1. Одно из двух? )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:04 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Можно попробовать завести массив счетчиков от 2 до 7. И отображать диапазон random(10) на 2..7 с инкрементом. Те ячейки которые получат больше счет - имеют шанс выйти на выход с обнулением (или с вычитанием). В этом есть что-то от алгортма Брезенхема. Типа накопления ошибки. Я думал тут как-то Монте-Карло нужно применить, но не совсем понял как ( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Можно попробовать завести массив счетчиков от 2 до 7. И отображать диапазон random(10) на 2..7 с инкрементом. С массивом такая беда, плохо масштабируется на больших числах :( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:06 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T Код: sql 1. Одно из двух? )) Упс, невнимательно прочитал ТЗ )) Числа целые или вещественные? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:09 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Тебе с большой вероятностью первый диапазон (m=10) будет нужен как число составное. Ну там ... 2^32, 2^64 e.t.c. Второй (n) может быть любым. Велика вероятность что будет некое кратное число между m,n и мы можем как-то на этом сыграть. Может трекать не n чисел на некое (p) номер группы. А номер группы будет трекать счетчики. Пока еще сам не понял что сказал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:10 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Упс, невнимательно прочитал ТЗ )) Числа целые или вещественные? Целые, но математика может быть в вещественном поле ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:15 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7). ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность. Как вариант накапливать сумму Код: plaintext 1. 2. 3. 4. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:22 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Массив чисел, берем каждое следующее прокруткой массива в соответствии с случайным количеством шагов из последовательности 0-9. Например для интервала 2-7 - шесть чисел, индексы массива 0-5, первое число из последовательности - 8, получаем проходом по массиву 2, следующее число из последовательности 1, шаг по массиву получаем 3 и так далее. Сохранится ли закон распределения понятия не имею)) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:25 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T Упс, невнимательно прочитал ТЗ )) Числа целые или вещественные? Целые, но математика может быть в вещественном поле Преобразование целых в вещественные не поможет, т.к. все-равно 10 целых превратятся в другие 10 целых, и в итоге получим два числа будут выдаваться в вероятностью 1/10, а четыре других 2/10. Преобразование возможно только если количество исходных вариантов кратно количеству конечных. Например 10 в 5 (2...6) получится. Код: sql 1. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:29 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7). ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность. Как вариант накапливать сумму А как доказать, что распределение будет ровное? ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:31 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ну я пока один вариант вижу, гарантированный. Если на входе у нас [0..M) А нам нужно [0..N) То нужно брать из входа N значений, затем делить на M. === На приведённом примере. У нас 10 случайных чисел. Нам нужно 6. Значем берём 6 случайных чисел [0..9] и делим на 10. Но это очень плохо масштабируется на больших числах. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Хотя у меня чёт сомнения насчёт "гарантированный" ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Преобразование возможно только если количество исходных вариантов кратно количеству конечных. Например 10 в 5 (2...6) получится. Код: sql 1. Это было бы слишком легко ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:36 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
iOracleDev Массив чисел, берем каждое следующее прокруткой массива в соответствии с случайным количеством шагов из последовательности 0-9. Например для интервала 2-7 - шесть чисел, индексы массива 0-5, первое число из последовательности - 8, получаем проходом по массиву 2, следующее число из последовательности 1, шаг по массиву получаем 3 и так далее. Сохранится ли закон распределения понятия не имею)) Во! А нужно хоть какое-то вшивое доказательство ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:37 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, тебе нужен вспомогательный рандом. покажу на примере: допустим, на входе 5 возможных равновероятных вариантов, на выходе надо 3 --------------- --------------- красный, желтый и оранжевый отрезки (числа 0, 2, 4) однозначно заходят на (0, 1, 2), а зеленый и синий (1 и 3) надо резать. С вероятностью 2/3 зеленый уходит на красный отрезок, иначе на желтый. Для синего аналогично. Ты в своем преобразователе имеешь право поюзать рандом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:40 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
то есть если исходное количество вариантов не делится на целевое, то придется резать "промежуточные" числа. Смекни пропорцию, напиши функцию... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:42 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 красный, желтый и оранжевый отрезки (числа 0, 2, 4) однозначно заходят на (0, 1, 2), а зеленый и синий (1 и 3) надо резать. С вероятностью 2/3 зеленый уходит на красный отрезок, иначе на желтый. Для синего аналогично. Ты в своем преобразователе имеешь право поюзать рандом? Я могу взять следующие числа из входа ) Но разве накидывание ещё одной вероятности на пограничные числа не влияет на общее распределение? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, Т.е. суть, что из входа я могу взять больше, чем отдам. Но использовать надо все числа, которые беру. Ну и входные числа я взял для примера, нужна формула для любых чисел (ограничимся рамками 63 бита)/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:46 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Но разве накидывание ещё одной вероятности на пограничные числа не влияет на общее распределение? в моем примере у каждого числа на входе вероятность 1/5 тогда на выходе вероятность Р(0) = 1/5 + 1/5 * 2/3 = 1/3 P(1) = 1/5 * 1/3 + 1/5 + 1/5 * 1/3 = 1/3 P(2) = ... = 1/3 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:48 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, чем блабла, лучше приведи саму задачу в контексте ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:48 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ViPRos hVostt, чем блабла, лучше приведи саму задачу в контексте Это наложен оттенок на будущее кристально чистое математическое решение ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7). ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность. Как вариант накапливать сумму А как доказать, что распределение будет ровное? ) Оно будет ровное, т.к. оно не меняется. Точка старта (сумма) равновероятна и смещение равновероятное. Но проще тупо смоделировать, т.е. запустить и посмотреть статистику. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Результат Код: plaintext ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ViPRos, задача смапить равновероятные N исходов на равновероятные М исходов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 если резать в правильных пропорциях, то будет равномерно. в моем примере у каждого числа на входе вероятность 1/5 тогда на выходе вероятность Р(0) = 1/5 + 1/5 * 2/3 = 1/3 P(1) = 1/5 * 1/3 + 1/5 + 1/5 * 1/3 = 1/3 P(2) = ... = 1/3 Картинка и правда красивая и показательная. Но как применить это, если границы -- это параметры (в известных пределах конечно же)? Например, на входе [0, 2147483647] На выходе [0, 161443504] + 42530 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 ViPRos, задача смапить равновероятные N исходов на равновероятные М исходов. Да, всё верно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Но проще тупо смоделировать, т.е. запустить и посмотреть статистику. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. Результат Код: plaintext Да, я тож получаю смещения ( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 ViPRos, задача смапить равновероятные N исходов на равновероятные М исходов. нет такой задачи, а то жисть была бы чернобелой ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:56 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Ну я пока один вариант вижу, гарантированный. Если на входе у нас [0..M) А нам нужно [0..N) То нужно брать из входа N значений, затем делить на M. === На приведённом примере. У нас 10 случайных чисел. Нам нужно 6. Значем берём 6 случайных чисел [0..9] и делим на 10. Но это очень плохо масштабируется на больших числах. Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой NM02132435465762738495 а в таблицу тебе не упихать равное количество каждого значения M, т.к. M не кратно N. В данном примере 6 и 7 по одному разу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, а просто если число меньше m/2 умножить на m/n, иначе на n/m? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 13:58 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 hVostt пропущено... Отрезаем или округляем? Распределение гарантируется? боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома Можно погрешность "накапливать". Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности Обычный алгоритм дизиренга (когда градации серого 0..255 преобразуется в 0..2, а картинка остается) IMHO ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен). Однако при больших M, это становится слишком дорого. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ViPRos hVostt, а просто если число меньше m/2 умножить на m/n, иначе на n/m? Интересное решение, на чём основано? Можно прогнать через бенч ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:01 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T а в таблицу тебе не упихать равное количество каждого значения M, т.к. M не кратно N. В данном примере 6 и 7 по одному разу. Потому что у тебя мапится одно число к одному, конечно так не получится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:02 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности Ну вот тоже об этом думаю. Непонятно, как применить остаток. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:03 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен). Однако при больших M, это становится слишком дорого. Опять невнимательно прочитал, работой отвлекают )) Да, так сработает, но проще тупо игнорить. Так ты 6 прочитал, а игнорить надо только 4. Но пять же на больших числах не взлетит. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:07 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt ViPRos hVostt, а просто если число меньше m/2 умножить на m/n, иначе на n/m? Интересное решение, на чём основано? Можно прогнать через бенч да просто сжатие, коэффициенты можно подбирать поточнее в зависимости от размеров m/2, n/2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен). Однако при больших M, это становится слишком дорого. Если я правильно тебя понял: ты сложил 6 случайных и поделил на 10, то это вообще не вариант. Например случайно выпало шесть девяток ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Не очень понятно практическая ценность данной задачи, т.е. бюджет на решение Т.к. ответ на вопрос топик стартера, совпадает с ответом на общеизвестный вопрос "сколько программистов нужно что бы закрутить лампочку" - ни одного, тут математик нужен (не для лампочки, а для доказательства равномерного распределения случайных величин) Как минимум, случайные числа мы можем складывать http://scask.ru/a_book_tp.php?id=60 ну и мне показалось, что статья https://habr.com/ru/post/208684/ тоже о чем-то похожем На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый. Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения. Как мне кажется (доказать не возьмусь) - напрмер можно просто лишние числа выкидывать. Если задачу делать чисто теоретически-дискретной, то я бы предложил 0...9 заменить на 0 / 1, мы же все же программисты ))) и живем в эпоху цифровой техники )))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
если бы числовая ось была вещественная, то всю историю можно было бы видеть как растяжение/сжатие с коэффициентом M/N Пусть есть N чисел от n0 до n0+N и M числе от m0 до m0+M N<M тогда произвольный n(k) можно было преобразовать в m0 + (n(k) + m0)*M/N для целых я пока не вижу как сделать идеально гладкое преобразование... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:32 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby если бы числовая ось была вещественная, то всю историю можно было бы видеть как растяжение/сжатие с коэффициентом M/N Пусть есть N чисел от n0 до n0+N и M числе от m0 до m0+M N<M тогда произвольный n(k) можно было преобразовать в m0 + (n(k) + m0)*M/N для целых я пока не вижу как сделать идеально гладкое преобразование... ошибка, у меня n от нуля скакали... m0 + (n(k) - n0 + m0)*M/N ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:33 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Википедия, вроде об этом, но я нифига не понял ))) я не математик ))) ВикипедияКонечные дискретные распределения Для дискретного распределения с конечным числом n значений случайной величины, в которых функция вероятности f принимает значения, отличные от нуля, базовый алгоритм выборки довольно прост. Интервал [0, 1) делится на n интервалов [0, f(1)), [f(1), f(1) + f(2)), … Длина интервала i равняется вероятности f(i). Предположим, кому-то дано равномерно распределенное число X, которому ставится в соответствие индекс i соответствующего интервала. Таким образом определенный индекс i будет иметь распределение f(i). Формализовать сказанную мысль просто, используя (кумулятивную) функцию распределения Удобно задать F(0) = 0. Тогда n интервалов будут иметь вид [F(0), F(1)), [F(1), F(2)), …, [F(n − 1), F(n)). И тогда главной вычислительной задачей становится поиск такого i, для которого выполняется F(i − 1) ≤ X < F(i). Поиск может быть произведен различными алгоритмами, например: Линейный поиск с линейной вычислительной сложностью. Бинарный поиск с логарифмической сложностью. И прочие виды поисков. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby если бы числовая ось была вещественная, то всю историю можно было бы видеть как растяжение/сжатие с коэффициентом M/N Пусть есть N чисел от n0 до n0+N и M числе от m0 до m0+M N<M тогда произвольный n(k) можно было преобразовать в m0 + (n(k) + m0)*M/N для целых я пока не вижу как сделать идеально гладкое преобразование... зачем идеально гладкое, обычное округление приведет к тому что надо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:36 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Leonid Kudryavtsev Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности Ну вот тоже об этом думаю. Непонятно, как применить остаток. Вот так идеальное распределение получается Результат Код: plaintext Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. Я не могу объяснить как это работает, но оно работает на любых парах (N, M) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby, кхе ... m0 + (n(k) - n0)*M/N ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:51 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T, хороший программист :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ViPRos ... зачем идеально гладкое, обычное округление приведет к тому что надо обычное неравномерно на пятерке. что-то типа "банковского" для "достаточно длинных" диапазонов. на малых диапазонах края останутся неравномерно заполненными. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 14:58 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby ViPRos ... зачем идеально гладкое, обычное округление приведет к тому что надо обычное неравномерно на пятерке. что-то типа "банковского" для "достаточно длинных" диапазонов. на малых диапазонах края останутся неравномерно заполненными. я думаю, этого хвосту будет достаточно А так все это можно сделать точнее, конечно ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:10 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ViPRos, точнее и для произвольной пары целочисленный последовательностей, это, если на бегу, то заветы Имя пользователя1 надо использовать со вторым генератором. например M<N тогда первые M из последовательности [N] мапятся 1:1 на последовательность [M] а оставшиеся (N-M) распределяются случайным генератором. может какая-то схема равномерного распределения остатка и есть, но с разбегу не вижу подходящего косоугола. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:16 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T, double - не наш метод! ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:16 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby, впрочем, для N-M можно держать последнюю использованную позицию, и использовать всегда следующую с циклом по модулю M вот. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:18 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
вариант со вспомогательным рандомом, который иллюстрируется картинкой 22078294 Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. тест на распределение https://jsfiddle.net/6xkz7tap/ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:20 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Во! А нужно хоть какое-то вшивое доказательство ) Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?)) PS: тут математик нужен, техник-программист для решения подобных задач не пригоден ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Код: plaintext 1. Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Dima T Код: plaintext 1. Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму. Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++. Надо в других ЯП затестить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
iOracleDev Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?)) У меня щас когнитивный диссонанс случился. Если не можешь, зачем завёл топик? А если можешь, нафига завёл топик? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений. На двух - незаметно. Но форма уже меняется. Представь что мы с тобой играем в кости на сумму. И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю. Ты - можешь ставить на любое число и с большей вероятностью проиграешь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby booby, впрочем, для N-M можно держать последнюю использованную позицию, и использовать всегда следующую с циклом по модулю M вот. Я тоже изначально из этого исходил, но в ходе дальнейших размышлений, это "оптимизируется" в банальное сложение и последующий модуль от итога. а здесь, есть очень большое опасение, что mayton Нельзя складывать случайные распределения. Это меняет их форму. Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную т.ч. дальше нужно сидеть за листочком бумаги и выводить формулы Т.ч. я даже не уверен, что из "Нельзя складывать случайные распределения. Это меняет их форму" следует "математическая ошибка". Вполне возможно, что итоговая формула по математике ровно такой и должна получится. Тут математик нужен ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Не очень понятно практическая ценность данной задачи, т.е. бюджет на решение Тут сложно говорить про бюджет. А задача в данном случае теоретическая, с уклоном в практику. Практически, хорошие случайные числа на диапазоне нужны много для каких задач. Касательно приведённых статей, конечно же определённое распределение и вероятность, это немного разные задачи. Leonid Kudryavtsev Как мне кажется (доказать не возьмусь) - напрмер можно просто лишние числа выкидывать. Это вынес в исключение к задаче. Leonid Kudryavtsev Если задачу делать чисто теоретически-дискретной, то я бы предложил 0...9 заменить на 0 / 1, мы же все же программисты ))) и живем в эпоху цифровой техники )))) Ну можно на биты разложить. И получать на входе случайные биты. Что никак не противоречит задаче. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby m0 + (n(k) + m0)*M/N для целых я пока не вижу как сделать идеально гладкое преобразование... Для целых мы получим разные вероятности, ага ( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Если не можешь, зачем завёл топик? А если можешь, нафига завёл топик? совершенно верно Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость Топик какой-то наброс на вентелятор. Или опиши _реальную_задачу_ или запишись в детский(или не очень) клуб любителей математики (из тех, что по математическим олимпиад ездят) и задай вопрос преподавателю ))) а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную Я рассматриваю также это как некую криптографическую уязвимость которая позволяет делать прогнозы относительно SUM. Из просто случайных они становятся ... более закономерными что-ли. Дальше - куда нас заведет логика задачи. Предсказывать следующее значение? Или может вообще в топике мы просто проектируем очередной линейный конгруэнтный генератор только сами еще этого не поняли. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 15:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++. Нужно брать аппаратный. Например CryptGenRandom . ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость Я знаю как проверить, провести эксперимент как минимум. Если будет доказательство, могу и над ним посидеть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:01 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
давайте ещё раз уточним, что именно требуется. на вход поступает некое случайное число 0...9, надо на выход отдать 2...7 поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа. но мы хотим, чтобы результат зависел от входа, и даже одноразовое применение давало равную вероятность. Так? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:01 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Топик какой-то наброс на вентелятор. Или опиши _реальную_задачу_ или запишись в детский(или не очень) клуб любителей математики (из тех, что по математическим олимпиад ездят) и задай вопрос преподавателю ))) а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва Извините, но ни о чём. Это задача для ума. Если вам такое решать не интересно, то я не навязываю :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:03 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 на вход поступает некое случайное число 0...9, надо на выход отдать 2...7 Это для примера. Лучше конечно обобщить. Приходит [0..N), с равной вероятностью получения любого из значений. Нужно получить [M0..M1], или [0..M) (не так важно на самом деле). Значение из входа можно брать несколько раз, чтобы получить одно для выхода. Вероятность получения любого значения на диапазоне [0..M) должна быть одинаковая. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:08 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа. Ну не... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:09 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений. На двух - незаметно. Но форма уже меняется. Представь что мы с тобой играем в кости на сумму. И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю. Ты - можешь ставить на любое число и с большей вероятностью проиграешь. Похоже ты не заметил что смещение каждый раз разное, это предыдущее значение Код: plaintext 1. PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось (( Потестил на C# тоже работаетРезультат Код: plaintext Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:10 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Значение из входа можно брать несколько раз, чтобы получить одно для выхода. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:16 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Давай отвлечемся. Вот линейный метод. Код: plaintext 1. 2. 3. 4. Может нам посмотреть на него и поднять кое-какие идеи? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:22 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным. Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны? Может они идут из другой галлактики с длинным лагом? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 hVostt Значение из входа можно брать несколько раз, чтобы получить одно для выхода. Да, всё верно, в этом и смысл :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось (( Потестил на C# тоже работает Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider: Код: powershell 1. 2. 3. 4. 5. 6. 7. Видим небольшие, но всё же отклонения, хм.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:32 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось (( Потестил на C# тоже работает Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider: Код: powershell 1. 2. 3. 4. 5. 6. 7. Видим небольшие, но всё же отклонения, хм.. ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:46 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным. Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны? Может они идут из другой галлактики с длинным лагом? Ну тут нормально, я просто смысла пока не понимаю. Почему 2 раза, а не 3, допустим. И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке. Задача решена? )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:46 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Прошу прощения за такое название топика ) Вот задача. На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый. Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения. Решение, пропускать числа, не попадающие в рейндж, не очень интересно. Нужно именно преобразование. Можно что-то сохранять между операциями. Но в идеале чистое математическое преобразование нужно :) Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение. Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными. Так что два варианта - фильтр по диапазону и перекодирование отличаются лишь видом фильтра и наличием перекодирования. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ? Конечно, либо надо первое число целенаправлено выкинуть. В идеале, хотелось бы решение без состояния. Но и состояние тоже подойдёт, если будет понятно, что оно позволяет решить задачу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:48 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ну я Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение. С фильтром понятно. Но мы можем долго не получать следующего значения при сужении фильтра. ну я Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными. Брать остаток от деления, например? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 16:56 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt mayton Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным. Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны? Может они идут из другой галлактики с длинным лагом? Ну тут нормально, я просто смысла пока не понимаю. Почему 2 раза, а не 3, допустим. И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке. Задача решена? )) Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно. Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная. У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной долей вероятности попадает в 2 либо 3 большую нижнюю коробку. Вобщем такая вот физическая метафора. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:03 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, число штук элементов большего диапазона, равное остатку от целочисленного деления N\M должно просто скользить по меньшему диапазону. Остальные мапятся по кругу строго 1:1 вот и всё. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Имя пользователя1 ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ? Конечно, либо надо первое число целенаправлено выкинуть. В идеале, хотелось бы решение без состояния. Но и состояние тоже подойдёт, если будет понятно, что оно позволяет решить задачу. очевидно, задачу легко решить напрямую и без состояний, только если N k делится на M, потому что k использований рандомайзера дают N k равновероятных исходов, которые надо равномерно раскидать на M групп. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:06 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 но это в любом случае не будет идеальный рандом в математическом смысле. по сути, здесь любое состояние - это результат предыдущих вызовов рандомайзера, то есть опять всё те же N k исходов ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:18 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно. Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная. У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной долей вероятности попадает в 2 либо 3 большую нижнюю коробку. Вобщем такая вот физическая метафора. Да, прекрасная метафора! Хотелось бы формулу )) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:21 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Вобщем всё просто. Просто выдаем шар из той нижней коробки в которой их больше. Только буфер надо. Грубо говоря мой алгоритм - буферизированный. Например как только рухноло с неба > 50 шаров - начинаем на каждый новый шар просто извлекать из самой тяжелой коробки. Profit. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:28 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Потестил на C# тоже работает потестил на Java - результат противоречит математике и здравому смыслу Задал N=2, M=1000 Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:33 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ну.. в малой коробке еще ест варианты. 1) Мы однозначно кидаем шар в большую. 2) Есть выбор кинуть чуть правее или чуть левее. Здесь не нужно случайный генератор. Здесь нужно просто шары по кругу разбрасывать. чтоб 30% падало например в 1 большой ящик и 40% в следующий большой. Мою мысль легко понять если нарисовать коробки и падающие шары. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton, то, что ты говоришь, можно понимать двояко. Одно из пониманий дает возможность точно предсказать, какой следующий шар извлечется. т.е. тогда на входе поток случайный у тебя окажется, а на выходе последовательно детерминированный. заполнение выходного потока должно сохранять видимость случайности той же характеристики, какова случайность входного потока. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Да это добротность генератора. О которой хвост пока еще не говорил. Линейность - будет. Добротность - ХЗ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton ....начинаем на каждый новый шар просто извлекать из самой тяжелой коробки. Profit. Нифига не понял. Самое главное, не понимаю, что значит "самой тяжелой коробки" может ли быть такое, что коробки одинаковые по весу? если да, то фигня получится - даже матиматически доказывать не надо ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:36 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Dima T Потестил на C# тоже работает потестил на Java - результат противоречит математике и здравому смыслу Задал N=2, M=1000 Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:42 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton, не думаю, что это добротность. но твой "буфер" с "моим" слайдом головы/хвоста можно соединить так: мапим по кругу N на M и заполняем M в рамках текущего мапа до тех пор, пока не заполнится каждая ячейка в M в рамках фиксированного мапа, независимо от числа зерен, упавших в каждый горшок. В момент каждого полного заполнения в М, когда в каждой ячейке есть хотя бы одно зерно, независимо от размера насыпавшихся горок, циклически смещаем мапировку на единицу и обнуляем горшки. Продолжаем сыпать до следующего заполнения/попадания в каждe. из ячеек "буфера". ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:43 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 Leonid Kudryavtsev пропущено... потестил на Java - результат противоречит математике и здравому смыслу Задал N=2, M=1000 Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает Первые 100-о значения из "случайной последовательности". (вариант с одним rnd !, от двух rnd лучше явно не станет) 1 2 3 4 4 4 4 4 4 4 4 4 4 4 5 5 5 6 6 7 8 8 9 10 11 12 13 14 14 14 15 16 16 17 17 18 18 18 18 18 18 18 18 19 19 20 20 20 21 21 21 21 22 22 23 23 23 23 24 24 25 26 26 26 26 26 26 27 28 28 29 30 30 30 30 30 30 30 30 31 31 32 32 33 34 34 34 35 35 36 36 36 37 37 38 38 38 38 39 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Dima T PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось (( Потестил на C# тоже работает Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider: Код: powershell 1. 2. 3. 4. 5. 6. 7. Видим небольшие, но всё же отклонения, хм.. Отклонение в 0.01% можно на погрешность списать. Ты бы лучше потестил на нужных тебе M:N. У меня есть объяснение почему это работает для 10:6, собственно думал что получил решение для этого частного случая, но я не понимаю почему это работает для разных M:N, пробовал разные варианты, но со значениями не более 20. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:56 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ну или если все мои коробки завернуть в карусель... Кручу-верчу случайное число хочу. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 17:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Имя пользователя1 пропущено... последовательность случайная, но для каждого результата нет равновероятности Первые 100-о значения из "случайной последовательности". (вариант с одним rnd !, от двух rnd лучше явно не станет) 1 2 3 4 4 4 4 4 4 4 4 4 4 4 5 5 5 6 6 7 8 8 9 10 11 12 13 14 14 14 15 16 16 17 17 18 18 18 18 18 18 18 18 19 19 20 20 20 21 21 21 21 22 22 23 23 23 23 24 24 25 26 26 26 26 26 26 27 28 28 29 30 30 30 30 30 30 30 30 31 31 32 32 33 34 34 34 35 35 36 36 36 37 37 38 38 38 38 39 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:03 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
итого, задача решается только для частных кейсов N и M. В общем случае будет только приблизительное решение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Отклонение в 0.01% можно на погрешность списать. Ты бы лучше потестил на нужных тебе M:N. У меня есть объяснение почему это работает для 10:6, собственно думал что получил решение для этого частного случая, но я не понимаю почему это работает для разных M:N, пробовал разные варианты, но со значениями не более 20. Твой тест просто показывает, что _в_очень_большом_ псевдослучайном числе очень много и примерно одинаково знаменателей от 1 до ...не более 20... Весь алгоритм можно свести к формуле: сгенерировать BigInteger методом сложения многих случайных чисел от 0 до N взять остаток от деления этого BigInteger на M НО ! 1) Так как мы знаем, что очень большой BigInteger будет подчинять не "равномерному распределению", а будет "нормальное распределение" То, следующим шагом нужно доказать/опровергнуть, что значение mod % M из случайного числа подчиняющегося "нормальному распределению" будет подчиняться "равномерному распределению" Я не математик, т.ч. я пасс ))) 2) Кроме всего прочего, нужно доказать, что не будет корреляции между соседними значениями. В вырожденных случаях (напрмер N < M), такая корреляция явно наблюдается. В случае M > N, как мне кажется, корреляция тоже должна быть. "Двойной" рандом, такую корреляцию конечно будет сглаживать, но это как-то из пушки по воробьям (плюс двойной рандом должен портить генератор, давая вместо "равномерного" "нормальное" распределение) 3) Двойной вызов рандома, с чисто "програмной" точки зрения расточительно. Кроме того, смысл двойного (а не тройного, пятерного, десятерного) - я вообще не понимаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:13 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, что значит "приблизительное решение"? статистическая вероятность вообще только на бесконечном числе испытаний. Любая конечная серия дает всегда приближение. "приблизительное решение", это когда и на бесконечном числе испытаний распределение не выравнивается. А в рамках кратких серий длиной << M и о распределении судить нет возможности. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:28 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Я понял что rand() в C++ кривоват, меня натолкнул тройной на мысль что с двойным решение правильное Код: plaintext 1. тут итого ухудшается Код: plaintext но тоже самое на C# Код: sql 1. никак не влияет на итого Код: plaintext ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:48 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Ну я пока один вариант вижу, гарантированный. Если на входе у нас [0..M) А нам нужно [0..N) То нужно брать из входа N значений, затем делить на M. Нужно примешивать свое случайное число. Чтобы размазать входящее количество M на диапазон N*M, а уже после этого из него разбивать на N значений. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 18:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
ну я hVostt Ну я пока один вариант вижу, гарантированный. Если на входе у нас [0..M) А нам нужно [0..N) То нужно брать из входа N значений, затем делить на M. Нужно примешивать свое случайное число. Чтобы размазать входящее количество M на диапазон N*M, а уже после этого из него разбивать на N значений. В игре с коробками я предложил не случайное число а циклический счетчик. Тоже равномерное распределение но с плохой корреляцией. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Давай отвлечемся. Вот линейный метод. Код: plaintext 1. 2. 3. 4. Может нам посмотреть на него и поднять кое-какие идеи? +1 надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:13 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T mayton Давай отвлечемся. Вот линейный метод. Код: plaintext 1. 2. 3. 4. Может нам посмотреть на него и поднять кое-какие идеи? +1 надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного. Да. Мы просто знаем что этот датчик более-менее идеальный. И все что нам надо - параметризировать его Хвостовскими входными данными. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:14 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
DimaT, Доказать, что алгоритм работает - крайне сложно Доказать, что алгоритм НЕ работает - крайне легко, привести пример, когда он не работает Беру простой вариант val = ( prev_value + rnd N ) mode M беру N = 3, M = 2 предположим, что на каком-то шаге алгоритм сгенерил число 1 какая вероятность генерации разных чисел на следующем шаге? prev_value rnd N результат 1 0 = (1+0) mod 2 = 1 1 1 = (1+1) mod 2 = 0 1 2 = (1+2) mod 2 = 1 итого, если в результате мы видем 1, то следующее значение за ней будет 1 с вероятностью 66 % и 0 с вероятностью 33%. корреляция налицо Двойной - тройной - четверной - стократный рандом - это тот же рандом, но испорченный! т.к. вместо равномерного распределения, будет нормальное Ну ладно, те же предположения, двойной рандом (1+0+0) mod 2 = 1 (1+0+1) mod 2 = 0 (1+0+2) mod 2 = 1 (1+1+0) mod 2 = 0 (1+1+1) mod 2 = 1 (1+1+2) mod 2 = 0 (1+2+0) mod 2 = 1 (1+2+1) mod 2 = 0 (1+2+2) mod 2 = 1 Если в результате мы видим 1, то следующее значение за ней будет 1 с вероятностью 5/9 и 0 с вероятностью 4/9 корреляция налицо ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:19 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T +1 надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного. ЗАЧЕМ ? И так уже есть случайное число (псевдослучайное), зачем в него что-то совать? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:21 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev В случае M > N, как мне кажется, корреляция тоже должна быть. "Двойной" рандом, такую корреляцию конечно будет сглаживать, но это как-то из пушки по воробьям (плюс двойной рандом должен портить генератор, давая вместо "равномерного" "нормальное" распределение) Хоть явно это не заявлено в ТЗ, но я пока не рассматриваю случаи M > N, хотя есть мысли. Leonid Kudryavtsev 3) Двойной вызов рандома, с чисто "програмной" точки зрения расточительно. Кроме того, смысл двойного (а не тройного, пятерного, десятерного) - я вообще не понимаю. Одинарный вызов rand() это уже зло, но у ТС случайные числа откуда-то идут на вход, поэтому считаю неуместным обсуждать источник их появления. У меня вызов rand() только для моделирования поставленной задачи и не более того. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:21 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Смотрите. Подвох в самом вопросе Хвоста. Он говорит. Есть черный ящик. На вход идут какие-то случайные числа от 0 до 9. Я хочу получить числа от 2 до 7 (включительно) тоесть 6 штук. 10 не кратно шести и никак не делится. Какие еще требования? Чистая функция? Скорее нет. Мы не можем за 1 итерацию сразу получить ответ. Не хватает энтропии. Конечный автомат? Скорее да. Имеем право накапливать результат. Что еще известно об ограничениях. Ничего. Можем накапливать энтропию хоть 1000 лет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:26 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Если мы будем делить 6 на 10 то получим рациональный коэффициент вида 6/10 или 3/5 Если мы будем умножать random(10) на рациональный тип данных вида rational(3,5) и в результате - получим красивое линейное распределение РАЦИОНАЛЬНЫХ чисел в диапазоне от 0 до 5. Далее - сложение и перенос в диапазон от 2 до 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:31 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Все таки. если мы начинаем эмперитечески изобретать, без чтения книжет по теории вероятности, я предлагаю отталкиваться от простых случаев. На входе есть последовательность случайных 0 / 1 (пусть аппаратный датчик случайных чисел), нам нужно последовательность 0..3 Теорема 1. У меня есть чувство, что если мы из последовательности случайных бит склееваем случайный байт, то он будет "равномерно распределен" (требуется доказательство!). Собственно суммирования тут нет. Теорема 2. Так же, есть такое чувство, что если взять случайные байты и расклееть их на биты - будет аналогично (требуется доказательство) а вот дальше, уже аксиома: из "большого числа" мы всегда можем __экономно__ нарезать любое кол-во чисел в другой системе счисления Т.е. получаем queue из двух алгоритмов 1) Т.е. один алгоритм должен digit'ы в системе счисления N наталкивать new_value = value * N + digitIn 2) С другого конца, алгоритм digit'ы в системе счисления M выталкивать digitOut = value mod M new_value = value / M Что-то пока не сообразить, как отслеживать текущее кол-во актуальных digit'ов в value и когда собственно запускать считывание следующего digit'а ((( ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
эх, так и хотся узнать ваши оклады :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 19:58 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
5 стр. в мгновение ока наплодили. Хочу отметиьт обстоятельство. ТС пишет, что нужно такое же (равновероятное) распределение . Что он поимает под этим? Терминоогически это не означает случайность. Где-то уже это было отмечено. Равные доли каждой цифры. Это абсурд. В пределе только если. Поэтому самое простое - больший период накручивать на меньший. Или формула генератора. Это тоже было. Я просто рассуждаю. При накручивании целого кол-ва кругов (НОД(N,M)) равномерность очевидна. Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться. А если ещё разрешено было повторно использовать часть входого потока, о-о-о!.. Ну то есть неплохо бы окончательно оформить формулировку. Мэйтону на заметку: нормальным будет ср.арифметич. независимых случ.величин с одинаковыми M и D. Сумма же одинаковых - нет. Можжно представить: в 1-м случае это 2-мерная мишень расстреленная в десятку, во 2-м - некий микст точек на мишени, достаточно равномерный, Мож=сумме. Диме: аплодирую! Нормальная мысль была: при кривизне датчика их двойное использование вдруг да сгладит несколько кривизну. Я так понял. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 20:46 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 Ну то есть неплохо бы окончательно оформить формулировку. суть задачи: Есть функция getRandomN(), которая возвращает случайное равновероятное целое число 0...(N-1), итого N равновероятных исходов (N зашито внутри функции, не параметр). Написать функцию getRandomM(), которая возвращает аналогично 0...(М-1), то есть М равновероятных исходов. В качестве рандомайзера можно использовать только getRandomN(). суть решения: Какая бы не была реализация внутри getRandomM, там будет вызвано getRandomN() максимум k раз. Итого мы получаем N k равновероятных исходов, которые надо тем или иным способом распихать на M равных кучек. Очевидно, это можно сделать, если N k делится на М, при некотором k. И ещё более очевидно, что оно будет делиться только в том случае, если среди множителей М нет такого простого, на которое не делится N. В примере ТС было дано N=10, М=6, здесь в составе М есть 3, его нет в составе N, потому сделать нельзя. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 21:04 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 суть решения: Какая бы не была реализация внутри getRandomM, там будет вызвано getRandomN() максимум k раз. Итого мы получаем N k равновероятных исходов, которые надо тем или иным способом распихать на M равных кучек. Очевидно, это можно сделать, если N k делится на М, при некотором k. И ещё более очевидно, что оно будет делиться только в том случае, если среди множителей М нет такого простого, на которое не делится N. В примере ТС было дано N=10, М=6, здесь в составе М есть 3, его нет в составе N, потому сделать нельзя. Как-то доказательство лично для меня не убедительно "там будет вызвано getRandomN() максимум k раз" "мы получаем N k равновероятных исходов" если кол-во вызовов getRandomN может быть разным (на что намекает слово максимум в предыдущем предложении), то получим не N k , а какое-то число <= N k ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 21:19 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Имя пользователя1 суть решения: Какая бы не была реализация внутри getRandomM, там будет вызвано getRandomN() максимум k раз. Итого мы получаем N k равновероятных исходов, которые надо тем или иным способом распихать на M равных кучек. Очевидно, это можно сделать, если N k делится на М, при некотором k. И ещё более очевидно, что оно будет делиться только в том случае, если среди множителей М нет такого простого, на которое не делится N. В примере ТС было дано N=10, М=6, здесь в составе М есть 3, его нет в составе N, потому сделать нельзя. Как-то доказательство лично для меня не убедительно "там будет вызвано getRandomN() максимум k раз" "мы получаем N k равновероятных исходов" если кол-во вызовов getRandomN может быть разным (на что намекает слово максимум в предыдущем предложении), то получим не N k , а какое-то число <= N k короче, все ветки можно "выровнять" до N k ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 21:32 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 как если бы мы в конце сделали два лишних вызова ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 21:45 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
В целом мысль понял и даже, частично! согласен. Только я бы упростил формулировку Есть N^K возможных значений, где K это кол-во данных/циферек на входе, нужно разложить по M равным кучкам.... Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." Во вторых, все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось. Как я представлял бы данную задачу __практически__ (мы же в форуме программирование): Есть аппаратный генератор случайных чисел от 0..N (я бы для упрощения предложил 0 / 1), нужен алгоритм генерации числа 0..M максимально экономно использующий входные данные. Попытаюсь объяснить свою идея с /dev/null: Предположим на входе поток битов, нам нужно набрать байты. Пусть мы банально склееваем биты друг с другом. Понятно, что если на входе пришло 15 битов (k=15), мы можем склееть только один байт, а 7 оставшихся битов уйдут в /dev/null. Станет ли от этого первый получившися байт хуже "вероятным"? С точки зрения делетанта, сидящего на окладе ниже рыночного ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:42 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось. 22078105 авторРешение, пропускать числа, не попадающие в рейндж, не очень интересно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:51 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 22:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, то, что работает с rand, это не функция, в формальном смысле, и не может ею быть. Это процесс, вычислительный. Процессу принципиально разрешается работать бесконечно. PS Красиво рассуждаешь. Чувствуется образование. Совсем не частый для форума случай ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 12.02.2020, 23:26 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 Leonid Kudryavtsev Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться." потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу Вроде даже и согласен, но "не убедили" Даже сел писать код, но дошел до того, о чем говорил mayton 22078740 остаток получается в виде дроби, и что с ним потом делать (как применить операцию остаток от деления к дроби), в 3-и часа ночи после работы как-то сильно заумно ))) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 03:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Если мы будем делить 6 на 10 то получим рациональный коэффициент вида 6/10 или 3/5 Если мы будем умножать random(10) на рациональный тип данных вида rational(3,5) и в результате - получим красивое линейное распределение РАЦИОНАЛЬНЫХ чисел в диапазоне от 0 до 5. Далее - сложение и перенос в диапазон от 2 до 7. ну, допустим, вместо чисел 0...4 у нас появятся числа 0, 3/5, 6/5, 9/5, 12/5. Всё равно их не раскидать равномерно на 0, 1, 2 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 08:25 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
booby то, что работает с rand, это не функция, в формальном смысле, и не может ею быть. Это процесс, вычислительный. Процессу принципиально разрешается работать бесконечно. только на момент первого (да и любого по счету) результата рандомайзер будет вызван конечное количество раз. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 08:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома Брезенхем с этим не согласен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 10:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. Имя пользователя1 боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома Брезенхем с этим не согласен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 11:24 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
В чем проблема равномерно распределить смасштабированный вещественный диапазон 2..7 в целочисленный диапазон 2..7? Эта задача уже полвека, как решена. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 11:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30 И на него падают короткие отрезки длиной в 3 целых единицы. Далее - накопительный алгоритм который режет эти отрезки на единицы и распределяет их на пятёрки. Накапливаем гистограмму пятерок и решаем когда высота слолбика настолько высока чтобы сгенерировать следующее целое случаное число уже в диапазоне целых от 1 до 6. Или от 2 до 7. Как физическая аналогия - 10 стаканов в которые падают капли жидкости. И распределяются по 6 стаканам через систему труб в соотвествии с справедливостью. По подобию коробок которые я описывал. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 12:15 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Потому что НОК(6,10) = 30 Это частный случай. А в общем случае используется алгоритм Брезенхема. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:08 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ты имеешь в виду не-кратные m,n ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:23 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются. Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Какие рекомендации по накоплению и сбросу? Сколько прибавлять? И через сколько сбросить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 13:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. количество итераций велико, то и итоговые данные будут распределены равномерно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:07 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Нет. Было написано: "с таким же одинаковым шансом выпадения". Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Alibek B. Нет. Было написано: "с таким же одинаковым шансом выпадения". Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение. Брезенхем - это итеративный алгоритм. Он бежит по оси X, или Y (где уклон меньше) и делает опциональн либо инкремент +1 для противоположной оси либо не делает ничего на этой итерации. Он фиксирует ошибку коррекции по Y на каждой итерации. В настоящий момент - неясно как применить Брезенхема без O(n). Тоесть без линейного пробегания по всему диапазону. Разумеется мы не всегда ищем O(1) но хотелось - бы не снизить зависимость от длины интервала. Ведь Хвост мог захотеть отображать дипазон MAX_LONG на какое-то число раза в полтора меньшее чем MAX_LONG. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
господа, "алгоритм Брезенхама" - это про попиксельное рисование? не понимаю, как он относится к сабжу. вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1, алгоритм заменяет частые импульсы на редкие за счет периода ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 14:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить можно только без детерминизма. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:02 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Имя пользователя1 вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить можно только без детерминизма. задача - уметь создать число, равновероятное из М вариантов., пользуясь специальным рандомайзером. 22078797 тут я собрал условие в кучу, по ответам ТСа на вопросы. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:13 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7). ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность. Как вариант накапливать сумму Код: plaintext 1. 2. 3. 4. ИМХО Этот вариант был нормальный, не надо никаких лишних rand(), модель кривая получилась, подвел кривоватый rand() из C++. Результат 6-ти запусков на C# Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. Код: plaintext 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. Надо бы на ГСЧ посерьезней затестить, но и тут уже видно что есть отклонения всего на 0.005%, но они тоже случайные, каждый раз разные, не в пользу какого-то конкретного элемента. PS Только для случаев N>=M ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:17 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть? Еще есть мысль что тебе не стоит париться о качестве встроенного генератора в данной конкретной задаче. Вряд-ли мы получим что-то более качественное. В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10 И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг". Скорее всего маппинга не существует а есть некое управляющее воздействие на конечный автомат (FSM) который периодически выдает (а может и не выдать!) очередное псевдо-случайное число как отклик на внешнее воздействие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:35 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10 И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг". Счетчик не взлетел, случайность нужна Код: plaintext 1. 2. 3. 4. 5. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev ...Станет ли от этого первый получившися байт хуже "вероятным"?.. Но автор хочет фсю её. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 15:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть? Фиг его знает. Тут исходник , посмотри, может чего поймешь. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 16:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev ...Станет ли от этого первый получившися байт хуже "вероятным"?.. Но автор хочет фсю её. Немного наврал в формулировке, попозже уточню ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 16:10 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T mayton Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть? Фиг его знает. Тут исходник , посмотри, может чего поймешь. Хм... та тут похитрее будет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 16:49 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98, уточняю: как раз для нашего случая. Это св-во случайной послед-сти называют частотоустойчивостью (у нас - это равновероятность). Я, правда, предполагаю, что наш поток не просто равновероятен, а ещё и псевдослучаен. Тогда согласо определению каждая "законная" подпо-сть обладает частотоустойчивостью, т.е. равновероятностью. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 16:57 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
И не программа: SET NOCOUNT ON; declare @count table(id int identity(1,1),nn int); declare @ir int=1 declare @res table (id int identity(1,1),nn int) /*Начальное формирование таблиц*/ while @ir<=9 begin insert @count(nn) values(0) insert @res(nn) values(0) set @ir+=+1 end declare @id int set @ir=0 while @ir<=1000000 begin /*равномерное распределение от 1 до 9*/ select @id= ROUND(RAND()*9,0) select @id=case when @id=0 then 9 else @id end update @count set nn=nn+1 where id=@id /*перевод в равномерное от 1 до 6*/ select @id=floor(@id*6/9.)+nn%2 from @count where id=@id select @id=case when @id=0 then 6 when @id>6 then 1 else @id end update @res set nn+=1 where id=@id select @ir+=1 end select t0.id [id_1-9], t0.nn [было 1-9], t1.id [id_1-6], t1.nn [Перевод 1-6] from @count t0 join @res t1 on t1.id = t0.id Результат: 1 110513 1 166402 2 111083 2 166775 3 110935 3 166886 4 111532 4 166790 5 111304 5 166713 6 111452 6 166435 7 110824 7 0 8 111150 8 0 9 111208 9 0 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 17:36 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число. Тогда оставшиеся значения тоже будут равномерно распределены. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 17:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Anatoly Moskovsky Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число. Тогда оставшиеся значения тоже будут равномерно распределены. Это старый боян из собеседований. Типа брошена игральная кость. И надо получить Случайное число от 1 до 25 за наименьшее число бросков. Но эта идея с гневом отвергнута где-то в начале бесед. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 18:06 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Но эта идея с гневом отвергнута где-то в начале бесед. Она с гневом отвергнута в самом стартовом посте ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 18:11 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt, F(n + 1) = 2 + (F(n) - 2 + S(n+1)) / 5 Не читал но осуждаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 18:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Имя пользователя1 господа, "алгоритм Брезенхама" - это про попиксельное рисование? не понимаю, как он относится к сабжу. вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз как его равномерно смапить на набор (0, 1, 2) ? покажите на примере это алгоритм равноценен предложенному в 22078706 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 19:23 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Leonid Kudryavtsev mayton Но эта идея с гневом отвергнута где-то в начале бесед. Она с гневом отвергнута в самом стартовом посте так делать в общем случае нельзя этот же генератор может использоваться в получении другой вероятности н-р, если нам нужно получить две независимые случайные величины a, b то "обрезка" будет "искажать" распределение другой величины например, так очень сильно накололись с довольно известным преобразованием такого типа Код: pascal 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.02.2020, 19:49 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Но это очень плохо масштабируется на больших числах. может уже писали за 7 страниц, но после этих загадочных намёков есть смысл посмотреть полное условие там наверняка ещё какие-то детали всплывут... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2020, 00:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Почему вы думаете что полное условие вообще существовало? Авторы часто задают тему топика еще без осознания всех деталей. Детали уточняются в процессе. И это нормальный процесс. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2020, 12:33 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt Но в идеале чистое математическое преобразование нужно :) Можно преобразовывать по частям - добавили несколько десятичных цифры, выдали несколько шестиричных, вот только есть такой момент - может оказаться, что добавление очередной десятичной цифры даст перенос в шестиричный разряд, который мы уже выдали раньше... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2020, 12:59 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt У меня щас когнитивный диссонанс случился. Если не можешь, зачем завёл топик? А если можешь, нафига завёл топик? А как ты думал, когда задаешь такие задачки предполагается что можешь сделать какую то экспертизу решения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2020, 15:58 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
а, ну раз конь, то вот вам "писча для коня" на 36:00 тут занятная тема, может получится куда-то прикрутить ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 14.02.2020, 19:09 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30 В первую очередь об этом подумал. И писал уже выше про частный случай, когда НОК(A, B) = A * B, на больших числах придётся выбирать очень много значений из потока. Математически, задача решена. Практически -- страдает большими проблемами избыточности. Alibek B. Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются. Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно. А нужно, чтобы вероятность была применима к каждому следующему числу на выходе, а не на больших объёмах статистически. Имя пользователя1 ставилась задача не о равномерном распределении на множестве итераций, а о равновероятности каждого конкретного результата + Речь о вероятности, а не о распределении. Статистика на больших выборках просто показывает эту вероятность. Т.е. это значит, что если на вход придёт 10 одинаковых цифр, значит на выходе должно быть тоже что-то такое. А превращение любого входа в равномерное распределение по рейнджу :) Короче я не математик и можете закидывать камнями. Предложенные в топике решения выглядит рабочими, на больших выборках. Но хочется же красиво ) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 00:33 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Anatoly Moskovsky Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число. Тогда оставшиеся значения тоже будут равномерно распределены. Метод Монте-Карло. Самый простой способ, да. Но выходит за рамки задачи, которую хочется решить. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 00:38 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
полудух может уже писали за 7 страниц, но после этих загадочных намёков есть смысл посмотреть полное условие там наверняка ещё какие-то детали всплывут... Там было употреблено слово "допустим" :) Это же не ТЗ-шка для реализации за срок. А задача для размышления, для генерации интересных идей. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 00:40 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
iOracleDev А как ты думал, когда задаешь такие задачки предполагается что можешь сделать какую то экспертизу решения. Ржевский (Р) пришел к Пьеру Безухову(Б) на вечеринку. Там кто-то грит: - Шестьдесят первый! Взрыв смеха. Другой грит: - Двенадцатый! Опять хохот. (Р) спрашивает у (Б): что тут у вас за приколы? - А это мы анекдоты рассказываем. Все их уже запомнили, чтобы каждый раз не повторять, пронумеровали их. ... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 00:43 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
hVostt mayton Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30 В первую очередь об этом подумал. И писал уже выше про частный случай, когда НОК(A, B) = A * B, на больших числах придётся выбирать очень много значений из потока. Математически, задача решена. Практически -- страдает большими проблемами избыточности. Не решена она математически, mayton уже писал об этом mayton Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений. На двух - незаметно. Но форма уже меняется. Представь что мы с тобой играем в кости на сумму. И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю. Ты - можешь ставить на любое число и с большей вероятностью проиграешь. Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 11:31 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Dima T Представь что мы с тобой играем в кости на сумму. И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю. Ты - можешь ставить на любое число и с большей вероятностью проиграешь. Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных. Нет. Если A - случайная величина точек на 1 кости (от 1 до 6) а B - количество точек на 2 кости то их произведение даст линейное распределенеи от 1 до 36. А их сумма - даст "три ступеньки". Ломаную линию разных высот. В количестве 12 полосок. И чем больше костей мы сложим в сумму - тем ближе и ближе мы будем аппроксимировать следующий график-колокольчик. В котором заранее мы будем знать моду, медиану, среднее квадратическое и прочее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 11:38 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Dima T пропущено... Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных. Нет. Убедил. Только сумма. Но если ты собрался использовать НОК, то надо будет складывать, умножение тут не уместно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 11:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Мой алгоритм падающих капель (Fallen Fluids) или отрезков (тоже самое) не предполагает сложения самих случайных величин. Есть просто учёт величины жидкости в стаканах. Есть еще один вариант. Я-бы назвал его quantum particles. Тоже самое но из 10 источников вылетает 1 электрон случайным образом. Попадает на некоторый роутер. Или мультиплексор. Который случайным образом направляет электрон в 1 из двух возможных прёмников. В пропорции. Приемники образуют батарею из 6 штук. Это и есть выход нашего черного ящика. В данном алгоритме никакой кумулятивности нет. Мы получаем результат сразу. Но честно говоря Хвост поставил меня в парадоксальную ситуацию. Для роутинга электрона мне нужен новый ГПСЧ. Которого у меня нет. Получается рекурсия. Я строю ГПСЧ для Хвоста но для реализации этого ГПСЧ мне нужен еще один ГПСЧ. Вобщем ладно. Если заменить случайных роутинг электронов на простоё счет по модулю 30/6 = 5. Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон влево или вправо. Это немножко сломает авто-корреляцию. Тоесть на выходе мы получим ГПСЧ который "косит" в сторону наличия мелких монотонных последовательностей. Хвост как тебе квантовый? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 12:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Вобщем ладно. Если заменить случайных роутинг электронов на простоё счет по модулю 30/6 = 5. Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон влево или вправо. По сути ты изобрел тоже что и я 22078250 только сложнее. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 13:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Без накопления. Quantum particles выдает сразу результат. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 13:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Для роутинга электрона мне нужен новый ГПСЧ. Которого у меня нет. да есть у тебя всё коли уж добрался до электронов, то лови случайные фотоны из окружающей среды и юзай в кач-ве СЧ ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 14:42 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ты понимаешь что такое "метафора" ? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 15:43 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
зы: там нет слова "метафора" поэтому в идеале - бери НЕЙТРИНО. Их тупо больше и они повсюду. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 15:56 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Я тебя чем то обидел? Чего злой такой? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 16:09 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ты модер и друг Димы в одном лице. P.S. А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 17:51 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
:рука-лицо. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 17:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 Ты модер и друг Димы в одном лице. Даже не знаю что сказать. Может не стоит теории заговора искать? Забей и не заморачивайся. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 18:18 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Я тебя чем то обидел? Чего злой такой? чё если без смайликов, то сразу злой? ты как первый день замужем ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 19:27 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Quantum particles. Усечённый до отображения 5:3. Работает абсолютно точно. При 3000 входных факторах в виде последовательности выдает ровную гистограмму с полосками по 1000 попаданий. Если надо смасштабировать до 10:6 - то делается всё по аналогии. Ну и генерализованный кейс для кратных и не кратных чисел - я уже поскипаю. Неинтересно. Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. Возможно есть плохая авто-корреляция. Но это уже надо не мне а другим. Пускай ищут и доказывают. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 16.02.2020, 20:22 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Но честно говоря Хвост поставил меня в парадоксальную ситуацию. Для роутинга электрона мне нужен новый ГПСЧ. Которого у меня нет. Получается рекурсия. Я строю ГПСЧ для Хвоста но для реализации этого ГПСЧ мне нужен еще один ГПСЧ. Почему же? У тебя тот же самый ГПСЧ, ты можешь брать дополнительные значения оттуда. Так как мы имеем дело с вероятностью, что один вход, что несколько -- разницы-то нет :) mayton 30/6 = 5. Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон влево или вправо. Это немножко сломает авто-корреляцию. Тоесть на выходе мы получим ГПСЧ который "косит" в сторону наличия мелких монотонных последовательностей. Хвост как тебе квантовый? Вообще норм. Но получается, что у тебя коллизия на конкретных пограничных значениях, что не позволяет построить стройную концепцию. Понятное дело, что это лучше, чем журавль в небе, но всё же :) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 00:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Если надо смасштабировать до 10:6 - то делается всё по аналогии. А если надо масштабировать до нескольких порядков? Лан. У Димы алгоритм тоже рабочий :) Правда один из выступающих тут говорил, что так как на входе величина вероятностная, то что бы мы не делали с ней, на выходе получим такую же вероятностную величину. Но у меня свербит больше из-за отсутствия математической базы. Практически там и Монте-Карлой можно обойтись, или любой из вариаций алгоритма Димы. Воть. Похоже придётся расчехлять тервер... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 00:53 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 P.S. А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N). приближается, и довольно быстро ... деление же просто масштабирование PS: не узнаю вас в гриме ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 07:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Если я правильно понял, то задачу можно сформулировать так: На основании входной последовательности, которая состоит из чисел (вариантов чисел M1) сделать выходную последовательность чисел (вариантов M2). Допускается из входной последовательности прочитать K1 чисел, прежде чем начать вывод в выходную последовательность (в общем случае в выходную последовательность можно записать не одно число, а сразу серию из K2 чисел). При этом для построения выходной последовательности необходимо использовать всю информацию из входящей и только ее. В таком случае имеем равенство: K1 * {количество информации, содержащийся в одном числе вх. последовательности} = K2 * {количество информации, содержащийся в одном числе вых. последовательности} Количество информации в высказывании «Конкретное число из M вариантов» равно (в битах) log 2 M. Тогда: K1 * log 2 M1 = K2 * log 2 M2 или K1 / K2 = log 2 M2 / log 2 M1 или K1 / K2 = log M1 M2 Возникает вопрос: существуют ли такие натуральные K1 и K2, при заданных M1 и M2, при которых выполняется это равенство. В конкретно нашем случае (M1 = 10 и M2 = 6), логарифм дает иррациональное число, т.е. таких K1 и K2 не существует. Таким образом невозможно создать алгоритм преобразования (для нашего случая) последовательности, который бы работал только на основании информации из входной последовательности. Через это задачу можно решить, если нарушить «закон сохранения информации»: Способ №1: Терять часть информации (например, в первом посте упоминался вариант с пропуском входных чисел, которые не входят в выходной диапазон) Способ №2: Генерировать дополнительную информацию (например, квантовый алгоритм от mayton, где добавляется информация, что первые два из трех яблок из мелкой коробки №1 попадают в большую коробку №0, а третье – в №1) PS Я ни фига не математик, потому прошу прощения, если написал хрень. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 08:30 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Colt Через это задачу можно решить, если нарушить «закон сохранения информации»: Способ №1: Терять часть информации (например, в первом посте упоминался вариант с пропуском входных чисел, которые не входят в выходной диапазон) Способ №2: Генерировать дополнительную информацию (например, квантовый алгоритм от mayton, где добавляется информация, что первые два из трех яблок из мелкой коробки №1 попадают в большую коробку №0, а третье – в №1) PS Я ни фига не математик, потому прошу прощения, если написал хрень. Все правильно. +Способ №3: Отказаться от синхронизма. И накапливать энтропию. Это алгоритм падающих капель в стакан о которых я также писал выше. У него будет задержка в выдаче информации. И потребитель информации (Consumer) технически получит ее не сразу а по факту накопления этой самой "энтропии". Код: java 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 12:12 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Colt ...например, квантовый алгоритм от mayton, ... прошу прощения, если написал хрень. Насчёт хрени ... она в том, что сколько мнений, столько и постановок. Тепреь ЕиМНИП, то ТС мечтал что-то вроде такого. Если 100500 раз подряд выпала "9", то и в диапазоне 2-7 доолжно быть что-то аналогичное (уверен, что смысл сохранил). И как это прикажете понимать? в чём д.б. аналогия с "9"?.. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 18:13 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan) exp98 P.S. А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N). деление же просто масштабирование PS: не узнаю вас в гриме Осталось ещё уточнить, какую сумму подразумевал М-н. Послед-сть частичных сумм одного ряда или послед-сть сумм независимых сл.вел? ЦПТ про предел последнего. Для послед-сти 2-х слагаемых случ.вел. спор вообще бессмысленен. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 18:23 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98, разговор про распределение т.е. делается много повторений формулы. Грубо говоря, каждое значение выдаваемое формулой это куда упала очередная снежинка и смотрится куда она осела, вот полученный общий контур и будет распределение если кидать одну равнораспределённую величину будет ровный однородный слой если кидать сумму двух величин - будет треугольник ... при довольно большом количестве просуммированных (естественнно независимых велечин), "распредение бросков" этой функции будет стремиться к нормальному, всё как в предельной теореме - Локальная теорема Муавра — Лапласа ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 17.02.2020, 19:34 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), я не использую свистипедию в качестве научно-технического ресурса. И обычно не читаю ссылки туда в кач-ве подтверждения. Меня постоянно мучил вопрос, чего это я не помню такого знаменателя. И действительно, я ошибся с делением на корень (неверно посчитал дисперсию), нет там никакого корня - всё то же ср.арифм. В данном случае я пользуюсь заслуженным "справочником Корн" (перевод от 1984 г, подобный есть в инете). Находим п.18.6-5. Предельные теоремы. Увы мне, там действительно есть и случай с просто суммой. Но для схождения суммы необходимо специальное условие. Наверное поэтому мне не запомнилось или вообще мимо прошёл. Я не могу пока упрощённо его передать. Всё дело в дисперсиях. Не могут быть они быть какими угодно. Я пока уверен, что сумма одинаковых равномерных сл.величин не будет сходитья к нормальному за просто так, нужен спец.фильтр. Там же, п.18.8-1, табл. 18.8-3 самый конец -- предельная т. Муавра-Лапласа, но! для суммы биномиальных распр-й. Да и то со спец. условиями. Обещаю, что покопаться на предмет "локальной ТМ-Л", потому что за просто так суммы к нормальному не сходятся. И нормальное - это не любой "колокольчик", а с определёнными св-вами. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.02.2020, 20:15 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98, Я ж лекции по ММК и теории измерений сканировать не буду, по памяти теоремы гуглю. Кто ж виноват, что википедия самый быстронаходимый ресурс. В данном случае википедия права - во всяком случае то, что я помню и то, что написано там - сходится (гифка там довольно хорошая). ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 18.02.2020, 22:46 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), остаюсь при своём мнении,опираясь ещё дополнительно на Мат.энциклопедию(под ред. Виноградова), Зубков,Чистяков "Сборник задач по теор.вер"(там справочно дана теория тоже), Феллер ......... Кстати вчера ошибся, лишнее вычёркиваю: этоЯТам же, п.18.8-1, табл. 18.8-3 самый конец -- предельная т. Муавра-Лапласа, но! для суммы биномиальных распр-й. Да и то со спец. условиями.Какая связь формулы М_Л с суммой случ.распределений? По поводу всё же суммы снова Яп.18.6-5. Предельные теоремы. Тут интерпретация достаточного условия в моей вольной трактовке: отклонения должны оч-чень хорошо уменьшать при n-->беск-ти (а не просто даже наличие одной такой подпослед-сти). Собственно римерно так я и представлял проблему достаточ. усл. Кроме того, неформальные рекомендации по применению ФМ-Л к биноминальному распр-ю npq>20, и желательно р достаточно близко к 1/2. Иначе (маленькое р) рекомендуется приближение распределением Пуассона. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 14:44 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Старый школьный боян ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 14:47 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton Старый школьный боян Конус, изготовленный с намерением получить "горку" (трения там всякие, вес горошин и т.д. мешают им разлететься). Послед-сть фильтров для исходной выборки. Пуассон тоже горкой. Где сумма независимых распределений? И наверное там говорят, мол, клянусь, получился Гаусс! следует верить? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 15:12 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 mayton Старый школьный боян Конус, изготовленный с намерением получить "горку" (трения там всякие, вес горошин и т.д. мешают им разлететься). Послед-сть фильтров для исходной выборки. Пуассон тоже горкой. Где сумма независимых распределений? И наверное там говорят, мол, клянусь, получился Гаусс! следует верить? Давай порассуждаем что происходит с шариком когда он ударяется о колышек. Наверное пофиг на его траекторию. И даже пофиг куда он полетит после 1 колышка. Важно что мы не можем (реально не можем) спрогнозировать его попадание на колышки 2-го уровня. Мы можем просто предположить что его вектор направления впаво и влево - случаен. Далее - гистограмма просто моделирует сумму случайных величин. Суть которых - векторы левый или правый. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 15:54 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98, тут видишь на этом факте построена вся теория измерений и расчёта погрешностей косвенных измерений более хороший тынц по предельным теоремам ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 16:06 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), авторВ этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники. Эта отметка установлена 15 мая 2011 года.И я с этим роботом полностью согласен. Мне очень странно. Я могу понять поколение вики. Для них не имеется большей реальности, чем виртуальная. Но неужели мои ссылки на заслуженные, речензируемые, с ответственными редакторами и корректорами не имеют веса? Вспоминаю не столь давнюю комедию с "совершенными числами", когда выяснилось ( как? не может быть!), что в свистипедии оказыается тоже бывают опечатки. kealon, ты хотя бы пытался разобраться в условии применимости т.н.(по свистипедии) "ЦПТ Линдеберга"? Там, где предел -->1 (И пусть выполняется условие Линдеберга:). При каком условии? Да там чушью по белому написано |X-mu|>eps*Sn. Больше, Карл! Больше!!! Что это означает? Сумма сходится при сколь угодно больших или малых отклонениях от среднего! Я же вам всем дал перевод Американского издания Справочника, Корн. В нём чистым русским языком написано, что при сколь угодно меньших отклонениях. Меньше,Карл! Меньше!!! Ну да, подумаешь - опечатка! Ну и чему будем верить? или голосование? Что это означает? Вот скорее всего, что квадраты отклонений д.б. сколь угодно маленькими на бесконечности! Вот эту мою трактовку и стоит опровергать. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 22:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Ну вы хотя бы прониклись тем, что, если ваши отклонения(их квадраты) будут на бесконечности больше любого заранее числа, то ни о каком предельном распределении с КОНЕЧНОЙ дисперсией не м.б и речи? Я не оспариваю других букв в этой "хорошей ссылке". С условием применимости у этих знатоков точно проблемы. Одно это говорит о качестве вашей любимой свистипедии. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 22:05 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton, я впервые пытаюсь разгадать принцип теорвера пусть даже простого физического устр-ва. Я не вижу здесь суммы (тем более независимых) случайных величин. Больше склоняюсь, что реализовано либо биномиальное распределение при р=1/2 и показано, что оно стремится к горбу. И тогда я верю, что горб Гауссов со скоростью О(1/корень(N)) согласно ЛокТМ-Л. Либо тут как-то соединено оно же с законом больших чисел (для распр. тоже при р=1/2). ЗБЧ - это когда для каждой отдельной случ.вел. ср.арифм. --> к мат.ож. Но у каждой своя скорость и для одного N отклонения у горошин будут разные, но в целом вокруг середины как мишень. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 22:14 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 kealon, ты хотя бы пытался разобраться в условии применимости т.н.(по свистипедии) "ЦПТ Линдеберга"? Там, где предел -->1 (И пусть выполняется условие Линдеберга:). При каком условии? Да там чушью по белому написано |X-mu|>eps*Sn. Больше, Карл! Больше!!! Что это означает? Сумма сходится при сколь угодно больших или малых отклонениях от среднего! Я же вам всем дал перевод Американского издания Справочника, Корн. В нём чистым русским языком написано, что при сколь угодно меньших отклонениях. Меньше,Карл! Меньше!!! Ну да, подумаешь - опечатка! Ну и чему будем верить? или голосование? Что это означает? Вот скорее всего, что квадраты отклонений д.б. сколь угодно маленькими на бесконечности! Вот эту мою трактовку и стоит опровергать. Эта теория даёт очень удобный матаппарат для расчёта погрешностей аналитическими методами. Для практического применения этого достаточно. Для более правдивого приближения есть ММК Кроме того, в ссылке приводится более сильное утверждение, чем то, что привёл я изначально. С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли. А уж как там это обосновывать, мне как практику тяжело лезть в эти дебри. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 22:50 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Я ещё раз повторюсь. У меня есть заслуженные печатные издания. К прежнему списку добавю детализацию. Мат-я энциклопедия, гл.ред. Виноградов, в 5-ти томах (каждый том в свой год ~1980) редколлегия: Адян, Александров, Бахвалов, ..., Кудрявцев, Мищенко, Свешников, Тихонов, ..., Яблонский. Конкретно про сумму слex.вел. статья Петрова. про ЦПТ см. т.5, с.804-806 про условие Линдеберга-Феллера (необх.и достаточное для суммы) см. т.3, с.285, "Линдеберга-Феллера теорема". Записаное в этой форме условие более чем прозрачное. Для схождения частичных сумм к нормальному н. и д. условия Линдеберга . Т.е. чтобы нормированная центрированная вероятность сколь угодно малых и больших больших отклонений -->0. В частности наверное поэтому тоже ср.арифм. одинаковых величин сходится к нормальному. У них как раз суммарные квадраты дисперсии -->0. Дополнительно см. Петров В.В., Суммы независимых случ-х вел-н, М. 1972. P.S. Я уже лет 30 часто замечаю пренебрежения к условиям применимости тех или иных теоретических утверждений к практике. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 22:55 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), я много забыл и ещё больше не знаю. Трудно вспомнить будет схему поверки? С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 19.02.2020, 23:01 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
Алексей Роза, там кстати должно двух-модовое получиться в конце. Просто ящик такого мелкого размера что эти два холмика сливаются в волну и это не очевидно. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 00:21 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
По моему предложению по Бернулли. Для P=2/3 ~ 0.66666666666 следующая табличка показывает Вероятность появления события (k) раз в (n) независимых исптытаниях при условии что вероятность возникновения события (p) Табличка похожа по смыслу на треугольник паскаля. Только добавляются множители p,q с высокими степенями. 1 2 3 4 5 6 7 8 9 10 1 0.666667 0.444444 0.222222 0.098765 0.041152 0.016461 0.006401 0.002439 0.000914 0.000339 2 0.000000 0.444444 0.444444 0.296296 (0.164609) 0.082305 0.038409 0.017071 0.007316 0.003048 3 0.000000 0.000000 0.296296 0.395062 0.329218 0.219479 0.128029 0.068282 0.034141 0.016258 4 0.000000 0.000000 0.000000 0.197531 0.329218 0.329218 0.256059 0.170706 0.102423 0.056902 5 0.000000 0.000000 0.000000 0.000000 0.131687 0.263374 0.307270 0.273129 0.204847 0.136565 6 0.000000 0.000000 0.000000 0.000000 0.000000 0.087791 0.204847 0.273129 0.273129 0.227608 7 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.058528 0.156074 0.234111 0.260123 8 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.039018 0.117055 0.195092 9 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.026012 0.086708 10 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.017342 Если ищется вероятность к примеру 16% то ее можно найти по табличке как наиболее близкую ячейку и симулировать запуском 5 испытаний и фиксацией только 2х удачных событий. Код: javascript 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. Вроде нигде не ошибся. Если криво - поправте. По практике. Я так и не решил что делать с длинной серией испытаний которые уже использованы? Можно ли их выбросить (5 штук) или сделать сдвиг на 1 испытание и считать предыдущие - независимыми. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 01:00 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 kealon(Ruslan), я много забыл и ещё больше не знаю. Трудно вспомнить будет схему поверки? С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли пусть есть функция f(), которая даёт значение в интервале (a,b] делим интервал на равные промежутки (количество из целесообразности задаём) заводим массив для подсчёта много-много раз запускаем функцию и смотрим в какой интервал попало, увеличивая элемент массива в итоге, в массиве получается контур функции распределения: c y *F(x) - можно нарисовать для наглядности Совпадение проверяем методом наименьших квадратов: Имеем предполагаемое распределение (в данном случае нормальное) и посчитанное: F'(x i ) и c y *F(x i ) соответственно. Для линейного уравнения находим коэффициент c y и коэффициент корреляции Пирсона (в том же экселе стандартная функция, при построении графика, если кто не знает как его считать) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 08:04 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan) Кроме того, в ссылке приводится более сильное утверждение , чем то, что привёл я изначально. - Ну-у, это вряд ли. (цэ) Условия Линдеберга-Феллера-Леви необх и достат. Если что-то более сильное, то оно для более спец случаев. Скорее всего имеет место путаница. Если утверждать про голую сумму, то см. условия Л-Ф-Л. Если про неким образом "нормализованную" случ величину, являющуюся ф-цией от суммы независ случ величин, то нет ничего невозможного. В кач-ве "нормализации" обычно рассматривают Sn/n либо (Sn - nMi)/Sum Dn. Об них и есть ЗБЧ, ЦПТ, ТМ-Л и ЛокТМ-Л. Судя по всему "нормализация" и стала причиной взаимонепонимания. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 14:38 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton, насчёт сдвинуть ли не скажу. Вообще-то можно проверить гипотезу о независимости. А насчёт аналогий с Паскаля тругольником вы мне не оставили вчера возможности. Не сумел высказаться вчера, что сумма равновероятностных просто провоцирует на заблуждения. Уже для 2-х дискретных слагаемых понятно, что в суммарном распределении более центральные значения могут комбинироваться большим кол-вом способов, нежели краевые. Что и показывал треугольник. Отсюда делался перенос с ошибкой на предельный случай. Забывая, что дисперсия суммы независимых == сумме дисперсий. И, в случае одинаковых Д, D sum --> беск. Имено поэтому в теоремах делается "нормировка" в терминах энного кол-ва сигм. Но это уже будет функцией от суммы случайных величин, а не сама сумма. И теоремы - для функции. P.S. За последние месяцы уже 2-й случай, когда я читаю свистипедию и по ссылке, а там оказывается путаница, отсутствие источников и вообще бардак. Может это тенденция? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 14:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
mayton, появилось мнение, что 1 сдвиг недостаточен. Если подразумевается конечно, что есть датчик, и из его потока последвательно выбираются серии. Тогда сдвинутые последовательности будут просто напросто коррелировать, что даст их ковариационную матрицу <>0, хорошо не равной. Получится Д(а+б)=Д(а)+Д(б)+cov(а,б). А для независимых cov() = 0. Примерно так. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 15:32 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 mayton, появилось мнение, что 1 сдвиг недостаточен. Если подразумевается конечно, что есть датчик, и из его потока последвательно выбираются серии. Тогда сдвинутые последовательности будут просто напросто коррелировать, что даст их ковариационную матрицу <>0, хорошо не равной. Получится Д(а+б)=Д(а)+Д(б)+cov(а,б). А для независимых cov() = 0. Примерно так. Да. Согласен надо сдвигать на величину которая даст 100% независимость от предыдущего измерения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 16:59 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 kealon(Ruslan) Кроме того, в ссылке приводится более сильное утверждение , чем то, что привёл я изначально. - Ну-у, это вряд ли. (цэ) Условия Линдеберга-Феллера-Леви необх и достат. Если что-то более сильное, то оно для более спец случаев. Скорее всего имеет место путаница. Если утверждать про голую сумму, то см. условия Л-Ф-Л. Если про неким образом "нормализованную" случ величину, являющуюся ф-цией от суммы независ случ величин, то нет ничего невозможного. В кач-ве "нормализации" обычно рассматривают Sn/n либо (Sn - nMi)/Sum Dn. Об них и есть ЗБЧ, ЦПТ, ТМ-Л и ЛокТМ-Л. Судя по всему "нормализация" и стала причиной взаимонепонимания. т.е.: Summ(rnd(), k) / k - диапазон (0, 1] и Summ(rnd(), k) - диапазон (0, k] оба приближаются к нормальному только у второго сигма и матожидание больше в k раз ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 17:52 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), если не считать того, что в последнем случае на каждой итерации всего лишь суммы нормальные, каждый раз с бесконечно возрастающими М и Д, и т.о. не может быть речи о сходимости. Короче говоря, есть теорема Линденберга-Феллера-Леви о необх. и достаточном условии сходимости суммы. Можно их опровергать сколько влезет, от них не убудет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 20.02.2020, 20:16 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98, простые вопросы: в проверке 22083479 r^2 будет приближаться к 1 при увеличении k ? r и c y зависят от того выберем мы 1-й или 2-й вариант? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 21.02.2020, 00:17 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
kealon(Ruslan), вы не тот тезис отстаиваете. Аккуратнее читайте например здесь . это уже будет функцией от суммы случайных величин , а не сама сумма. И теоремы - для функции. Упрямый компутер хорошо лечит от инерции мышления. Одна таблетка. Вычислить 20 итераций суммы и записать данные в файл. Затем то же самое для ср.арифм. Затем сравнить результаты и ответить на вопрос: равны ли значения? и задуматься почему. Вторая таблетка теоретическая. Нужно ответить на 2 вопроса а) можно ли конечным числом сумм получить чистое теоретическое Нормальное распределение? (для одинаковых равномерных) б) тот же вопрос для ср.арифм. Ответы(не подглядывать): а) и б) - оба нет. И тоже задуматься почему. Я больше этот вопрос не обсуждаю. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2020, 20:33 |
|
||
|
Случайный конь в вакууме
|
|||
|---|---|---|---|
|
#18+
exp98 Упрямый компутер хорошо лечит от инерции мышления. Одна таблетка. Вычислить 20 итераций суммы и записать данные в файл. Затем то же самое для ср.арифм. Затем сравнить результаты и ответить на вопрос: равны ли значения? и задуматься почему. 20 раз???? какой в этом смысл? распределения проверяются массовым рассчётом - 22083479 что бы хотя бы картинку визуально получить, интервальчиков на 100, нужно хотя бы миллиончик раз прогнать тестовую функцию ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 25.02.2020, 21:02 |
|
||
|
|

start [/forum/topic.php?all=1&fid=16&tid=1339820]: |
0ms |
get settings: |
10ms |
get forum list: |
12ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
161ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
180ms |
get tp. blocked users: |
1ms |
| others: | 295ms |
| total: | 676ms |

| 0 / 0 |
