powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
223 сообщений из 223, показаны все 9 страниц
Случайный конь в вакууме
    #39925546
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Прошу прощения за такое название топика )

Вот задача.

На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый.
Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения.

Решение, пропускать числа, не попадающие в рейндж, не очень интересно.
Нужно именно преобразование.
Можно что-то сохранять между операциями.
Но в идеале чистое математическое преобразование нужно :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925549
Gennadiy Usov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Случайные числа от 0 до 9 поступают с "отрезка" (0,9)

Надо сделать "отрезок" (0,5), брать случайные числа и прибавлять 2.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925551
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

числа целые или вещественные? если второе, то 2 + r * 5 / 9
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925552
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Gennadiy Usov
Случайные числа от 0 до 9 поступают с "отрезка" (0,9)

Надо сделать "отрезок" (0,5), брать случайные числа и прибавлять 2.


Ну это понятно. Одинаковое распределение должно остаться. Все поступающие числа должны быть использованы.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925553
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

Целые. Но операции преобразования могут быть в поле вещественных чисел, а на выходе опять целое.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925554
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
2 + r * 5 / 9


Отрезаем или округляем? Распределение гарантируется?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925556
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Имя пользователя1
2 + r * 5 / 9


Отрезаем или округляем? Распределение гарантируется?
это только для вещественных...

боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925584
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: sql
1.
n = x < 5 ? 2 : 7;
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Прошу прощения за такое название топика )

Вот задача.

На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый.
Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения.

Решение, пропускать числа, не попадающие в рейндж, не очень интересно.
Нужно именно преобразование.
Можно что-то сохранять между операциями.
Но в идеале чистое математическое преобразование нужно :)

Можно попробовать завести массив счетчиков от 2 до 7.
И отображать диапазон random(10) на 2..7 с инкрементом.
Те ячейки которые получат больше счет - имеют шанс выйти на выход
с обнулением (или с вычитанием).

В этом есть что-то от алгортма Брезенхема. Типа накопления ошибки.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925606
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Код: sql
1.
n = x < 5 ? 2 : 7;



Одно из двух? ))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925607
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Можно попробовать завести массив счетчиков от 2 до 7.
И отображать диапазон random(10) на 2..7 с инкрементом.
Те ячейки которые получат больше счет - имеют шанс выйти на выход
с обнулением (или с вычитанием).

В этом есть что-то от алгортма Брезенхема. Типа накопления ошибки.


Я думал тут как-то Монте-Карло нужно применить, но не совсем понял как (
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925608
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Можно попробовать завести массив счетчиков от 2 до 7.
И отображать диапазон random(10) на 2..7 с инкрементом.


С массивом такая беда, плохо масштабируется на больших числах :(
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925615
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
Код: sql
1.
n = x < 5 ? 2 : 7;



Одно из двух? ))

Упс, невнимательно прочитал ТЗ ))

Числа целые или вещественные?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925620
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Тебе с большой вероятностью первый диапазон (m=10) будет нужен как число составное.
Ну там ... 2^32, 2^64 e.t.c.

Второй (n) может быть любым.

Велика вероятность что будет некое кратное число между m,n и мы можем как-то на этом сыграть.
Может трекать не n чисел на некое (p) номер группы. А номер группы будет трекать счетчики.

Пока еще сам не понял что сказал.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925630
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Упс, невнимательно прочитал ТЗ ))

Числа целые или вещественные?


Целые, но математика может быть в вещественном поле
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925640
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7).

ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность.

Как вариант накапливать сумму
Код: plaintext
1.
2.
3.
4.
thread_local int sum = 0;
sum += rand();
while (sum > 5) sum -= 6;
return sum + 2;
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925644
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Массив чисел, берем каждое следующее прокруткой массива в соответствии с случайным количеством шагов из последовательности 0-9. Например для интервала 2-7 - шесть чисел, индексы массива 0-5, первое число из последовательности - 8, получаем проходом по массиву 2, следующее число из последовательности 1, шаг по массиву получаем 3 и так далее. Сохранится ли закон распределения понятия не имею))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925650
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
Упс, невнимательно прочитал ТЗ ))

Числа целые или вещественные?


Целые, но математика может быть в вещественном поле

Преобразование целых в вещественные не поможет, т.к. все-равно 10 целых превратятся в другие 10 целых, и в итоге получим два числа будут выдаваться в вероятностью 1/10, а четыре других 2/10.

Преобразование возможно только если количество исходных вариантов кратно количеству конечных. Например 10 в 5 (2...6) получится.
Код: sql
1.
2 + x / 2
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925651
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7).

ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность.

Как вариант накапливать сумму


А как доказать, что распределение будет ровное? )
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925655
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну я пока один вариант вижу, гарантированный.

Если на входе у нас [0..M)
А нам нужно [0..N)

То нужно брать из входа N значений, затем делить на M.

===

На приведённом примере.
У нас 10 случайных чисел.
Нам нужно 6.

Значем берём 6 случайных чисел [0..9] и делим на 10.

Но это очень плохо масштабируется на больших числах.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925656
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя у меня чёт сомнения насчёт "гарантированный" )
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925658
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Преобразование возможно только если количество исходных вариантов кратно количеству конечных. Например 10 в 5 (2...6) получится.
Код: sql
1.
2 + x / 2



Это было бы слишком легко )
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925659
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iOracleDev
Массив чисел, берем каждое следующее прокруткой массива в соответствии с случайным количеством шагов из последовательности 0-9. Например для интервала 2-7 - шесть чисел, индексы массива 0-5, первое число из последовательности - 8, получаем проходом по массиву 2, следующее число из последовательности 1, шаг по массиву получаем 3 и так далее. Сохранится ли закон распределения понятия не имею))


Во! А нужно хоть какое-то вшивое доказательство )
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925665
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

тебе нужен вспомогательный рандом.

покажу на примере:

допустим, на входе 5 возможных равновероятных вариантов, на выходе надо 3


---------------
---------------


красный, желтый и оранжевый отрезки (числа 0, 2, 4) однозначно заходят на (0, 1, 2), а зеленый и синий (1 и 3) надо резать. С вероятностью 2/3 зеленый уходит на красный отрезок, иначе на желтый. Для синего аналогично.

Ты в своем преобразователе имеешь право поюзать рандом?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925668
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
то есть если исходное количество вариантов не делится на целевое, то придется резать "промежуточные" числа. Смекни пропорцию, напиши функцию...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925671
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
красный, желтый и оранжевый отрезки (числа 0, 2, 4) однозначно заходят на (0, 1, 2), а зеленый и синий (1 и 3) надо резать. С вероятностью 2/3 зеленый уходит на красный отрезок, иначе на желтый. Для синего аналогично.

Ты в своем преобразователе имеешь право поюзать рандом?


Я могу взять следующие числа из входа )

Но разве накидывание ещё одной вероятности на пограничные числа не влияет на общее распределение?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925673
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

Т.е. суть, что из входа я могу взять больше, чем отдам. Но использовать надо все числа, которые беру.
Ну и входные числа я взял для примера, нужна формула для любых чисел (ограничимся рамками 63 бита)/
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925676
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925677
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

чем блабла, лучше приведи саму задачу в контексте
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925680
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos
hVostt,

чем блабла, лучше приведи саму задачу в контексте


Это наложен оттенок на будущее кристально чистое математическое решение
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925681
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
void rand10_6() {
	
	int sum = 0;
	int arr[6] = {0};
	for (int i = 1; i < 1000000000; i++) {
		if ((i & 0xFFFFFF) == 0) {
			printf("\r%d: ", i);
			for(auto &x : arr) printf("%0.4f ", (double)x / i);
		}
		sum += rand() % 10;
		while (sum > 5) sum -= 6;
		arr[sum]++;
	}
}


Результат
Код: plaintext
989855744: 0.1671 0.1662 0.1671 0.1662 0.1671 0.1662
немного не равномерно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925682
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos,

задача смапить равновероятные N исходов на равновероятные М исходов.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925686
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925689
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
ViPRos,

задача смапить равновероятные N исходов на равновероятные М исходов.


Да, всё верно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925691
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Но проще тупо смоделировать, т.е. запустить и посмотреть статистику.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
void rand10_6() {
	
	int sum = 0;
	int arr[6] = {0};
	for (int i = 1; i < 1000000000; i++) {
		if ((i & 0xFFFFFF) == 0) {
			printf("\r%d: ", i);
			for(auto &x : arr) printf("%0.4f ", (double)x / i);
		}
		sum += rand() % 10;
		while (sum > 5) sum -= 6;
		arr[sum]++;
	}
}



Результат
Код: plaintext
989855744: 0.1671 0.1662 0.1671 0.1662 0.1671 0.1662
немного не равномерно.


Да, я тож получаю смещения (
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925694
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
ViPRos,

задача смапить равновероятные N исходов на равновероятные М исходов.

нет такой задачи, а то жисть была бы чернобелой
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925696
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Ну я пока один вариант вижу, гарантированный.

Если на входе у нас [0..M)
А нам нужно [0..N)

То нужно брать из входа N значений, затем делить на M.

===

На приведённом примере.
У нас 10 случайных чисел.
Нам нужно 6.

Значем берём 6 случайных чисел [0..9] и делим на 10.

Но это очень плохо масштабируется на больших числах.

Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой
NM02132435465762738495
а в таблицу тебе не упихать равное количество каждого значения M, т.к. M не кратно N. В данном примере 6 и 7 по одному разу.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925698
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

а просто если число меньше m/2 умножить на m/n, иначе на n/m?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925700
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
hVostt
пропущено...

Отрезаем или округляем? Распределение гарантируется?
это только для вещественных...

боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома


Можно погрешность "накапливать". Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности

Обычный алгоритм дизиренга (когда градации серого 0..255 преобразуется в 0..2, а картинка остается)

IMHO
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925701
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой


Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен).

Однако при больших M, это становится слишком дорого.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925703
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos
hVostt,

а просто если число меньше m/2 умножить на m/n, иначе на n/m?


Интересное решение, на чём основано? Можно прогнать через бенч
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925704
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
а в таблицу тебе не упихать равное количество каждого значения M, т.к. M не кратно N. В данном примере 6 и 7 по одному разу.


Потому что у тебя мапится одно число к одному, конечно так не получится.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925705
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности


Ну вот тоже об этом думаю. Непонятно, как применить остаток.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925709
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой


Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен).

Однако при больших M, это становится слишком дорого.

Опять невнимательно прочитал, работой отвлекают ))

Да, так сработает, но проще тупо игнорить. Так ты 6 прочитал, а игнорить надо только 4. Но пять же на больших числах не взлетит.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925719
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
ViPRos
hVostt,

а просто если число меньше m/2 умножить на m/n, иначе на n/m?


Интересное решение, на чём основано? Можно прогнать через бенч

да просто сжатие, коэффициенты можно подбирать поточнее в зависимости от размеров m/2, n/2
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925720
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
Это не поможет. У тебя N целых как-то превращаются в M целых. Какую бы ты функцию не взял все-равно в итоге результат сведется к таблице типа такой


Ну почему, я же взял M случайных чисел из N, значит сделал вероятность кратной. Должно получиться (пока не уверен).

Однако при больших M, это становится слишком дорого.

Если я правильно тебя понял: ты сложил 6 случайных и поделил на 10, то это вообще не вариант. Например случайно выпало шесть девяток ...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925722
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не очень понятно практическая ценность данной задачи, т.е. бюджет на решение

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

Как минимум, случайные числа мы можем складывать
http://scask.ru/a_book_tp.php?id=60

ну и мне показалось, что статья
https://habr.com/ru/post/208684/
тоже о чем-то похожем

На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый.
Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения.

Как мне кажется (доказать не возьмусь) - напрмер можно просто лишние числа выкидывать.

Если задачу делать чисто теоретически-дискретной, то я бы предложил 0...9 заменить на 0 / 1, мы же все же программисты ))) и живем в эпоху цифровой техники ))))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925726
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
если бы числовая ось была вещественная, то всю историю можно было бы видеть
как растяжение/сжатие с коэффициентом M/N

Пусть есть N чисел от n0 до n0+N
и M числе от m0 до m0+M
N<M

тогда
произвольный n(k) можно было преобразовать в
m0 + (n(k) + m0)*M/N
для целых я пока не вижу как сделать идеально гладкое преобразование...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925730
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925732
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Википедия, вроде об этом, но я нифига не понял ))) я не математик )))

ВикипедияКонечные дискретные распределения

Для дискретного распределения с конечным числом 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).

Поиск может быть произведен различными алгоритмами, например:

Линейный поиск с линейной вычислительной сложностью.
Бинарный поиск с логарифмической сложностью.
И прочие виды поисков.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925733
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
если бы числовая ось была вещественная, то всю историю можно было бы видеть
как растяжение/сжатие с коэффициентом M/N

Пусть есть N чисел от n0 до n0+N
и M числе от m0 до m0+M
N<M

тогда
произвольный n(k) можно было преобразовать в
m0 + (n(k) + m0)*M/N
для целых я пока не вижу как сделать идеально гладкое преобразование...

зачем идеально гладкое, обычное округление приведет к тому что надо
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925742
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Leonid Kudryavtsev
Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности


Ну вот тоже об этом думаю. Непонятно, как применить остаток.

Вот так идеальное распределение получается
Результат
Код: plaintext
989855744: 0.1667 0.1667 0.1667 0.1667 0.1667 0.1667

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#define N 10
#define M 6

int my_rand() {
	static int sum = 0;
	sum = (sum + rand() % N + rand() % N) % M;
	return sum;
}

void test_rand() {
	
	int arr[M] = {0};
	for (int i = 1; i < 1000000000; i++) {
		if ((i & 0xFFFFFF) == 0) {
			printf("\r%d: ", i);
			for(auto &x : arr) printf("%0.4f ", (double)x / i);
		}
		arr[my_rand()]++;
	}
}


Я не могу объяснить как это работает, но оно работает на любых парах (N, M)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925745
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,
кхе
...
m0 + (n(k) - n0)*M/N
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925746
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

хороший программист :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925749
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos
...
зачем идеально гладкое, обычное округление приведет к тому что надо

обычное неравномерно на пятерке.
что-то типа "банковского" для "достаточно длинных" диапазонов.
на малых диапазонах края останутся неравномерно заполненными.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925757
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
ViPRos
...
зачем идеально гладкое, обычное округление приведет к тому что надо

обычное неравномерно на пятерке.
что-то типа "банковского" для "достаточно длинных" диапазонов.
на малых диапазонах края останутся неравномерно заполненными.

я думаю, этого хвосту будет достаточно
А так все это можно сделать точнее, конечно
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925762
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos,

точнее и для произвольной пары целочисленный последовательностей,
это, если на бегу, то заветы Имя пользователя1
надо использовать со вторым генератором.
например
M<N
тогда первые M из последовательности [N] мапятся 1:1 на последовательность [M]
а оставшиеся (N-M) распределяются случайным генератором.
может какая-то схема равномерного распределения остатка и есть,
но с разбегу не вижу подходящего косоугола.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925763
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

double - не наш метод!
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925765
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,
впрочем, для N-M можно держать последнюю использованную позицию,
и использовать всегда следующую с циклом по модулю M
вот.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925766
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вариант со вспомогательным рандомом, который иллюстрируется картинкой 22078294


Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
function mapNtoM(x, n, m) {
    if (x === 0) return 0;
    var ratio = m / n;
    if (n % m === 0) return Math.floor(x * ratio);
    var fx = x / n;
    var fmax = (x + 1) * ratio;
    var fmin = x * ratio;
    var max = Math.ceil(fmax) - 1;
    var min = Math.floor(fmin);
    if (min === max) return min;
    var r = (x + Math.random()) / n;
    var destFMin = (min + 1) / m, destFMax = max / m;
    if (r < destFMin) return min;
    if (r >= destFMax || max - min === 1) return max;
    return min + 1 + Math.floor((r - (destFMin - fx)) / (max - min));
}

result = 2 + mapNtoM(x, 10, 6); // для кейса из примера




тест на распределение https://jsfiddle.net/6xkz7tap/
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925768
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Во! А нужно хоть какое-то вшивое доказательство )

Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?))

PS: тут математик нужен, техник-программист для решения подобных задач не пригоден
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925769
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T

Код: plaintext
1.
	sum = (sum + rand() % N + rand() % N) % M;



Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925772
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Dima T

Код: plaintext
1.
	sum = (sum + rand() % N + rand() % N) % M;



Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму.

Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++. Надо в других ЯП затестить.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925778
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iOracleDev
Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?))


У меня щас когнитивный диссонанс случился.
Если не можешь, зачем завёл топик?
А если можешь, нафига завёл топик?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925779
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений.

На двух - незаметно. Но форма уже меняется.

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925786
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
booby,
впрочем, для N-M можно держать последнюю использованную позицию,
и использовать всегда следующую с циклом по модулю M
вот.

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

а здесь, есть очень большое опасение, что
mayton

Нельзя складывать случайные распределения. Это меняет их форму.


Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную

т.ч. дальше нужно сидеть за листочком бумаги и выводить формулы

Т.ч. я даже не уверен, что из "Нельзя складывать случайные распределения. Это меняет их форму" следует "математическая ошибка". Вполне возможно, что итоговая формула по математике ровно такой и должна получится.

Тут математик нужен
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925788
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Не очень понятно практическая ценность данной задачи, т.е. бюджет на решение


Тут сложно говорить про бюджет. А задача в данном случае теоретическая, с уклоном в практику. Практически, хорошие случайные числа на диапазоне нужны много для каких задач.

Касательно приведённых статей, конечно же определённое распределение и вероятность, это немного разные задачи.


Leonid Kudryavtsev
Как мне кажется (доказать не возьмусь) - напрмер можно просто лишние числа выкидывать.


Это вынес в исключение к задаче.


Leonid Kudryavtsev
Если задачу делать чисто теоретически-дискретной, то я бы предложил 0...9 заменить на 0 / 1, мы же все же программисты ))) и живем в эпоху цифровой техники ))))


Ну можно на биты разложить. И получать на входе случайные биты. Что никак не противоречит задаче.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925789
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
m0 + (n(k) + m0)*M/N
для целых я пока не вижу как сделать идеально гладкое преобразование...


Для целых мы получим разные вероятности, ага (
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925790
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt

Если не можешь, зачем завёл топик?
А если можешь, нафига завёл топик?

совершенно верно

Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость

Топик какой-то наброс на вентелятор. Или опиши _реальную_задачу_ или запишись в детский(или не очень) клуб любителей математики (из тех, что по математическим олимпиад ездят) и задай вопрос преподавателю )))

а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925792
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev

Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную

Я рассматриваю также это как некую криптографическую уязвимость которая позволяет делать прогнозы
относительно SUM. Из просто случайных они становятся ... более закономерными что-ли. Дальше - куда нас
заведет логика задачи. Предсказывать следующее значение?

Или может вообще в топике мы просто проектируем очередной линейный конгруэнтный генератор
только сами еще этого не поняли.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925794
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++.


Нужно брать аппаратный. Например CryptGenRandom .
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925798
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость


Я знаю как проверить, провести эксперимент как минимум.
Если будет доказательство, могу и над ним посидеть.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925799
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
давайте ещё раз уточним, что именно требуется.

на вход поступает некое случайное число 0...9, надо на выход отдать 2...7

поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа.

но мы хотим, чтобы результат зависел от входа, и даже одноразовое применение давало равную вероятность. Так?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925801
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Топик какой-то наброс на вентелятор. Или опиши _реальную_задачу_ или запишись в детский(или не очень) клуб любителей математики (из тех, что по математическим олимпиад ездят) и задай вопрос преподавателю )))

а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва


Извините, но ни о чём. Это задача для ума. Если вам такое решать не интересно, то я не навязываю :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925808
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
на вход поступает некое случайное число 0...9, надо на выход отдать 2...7


Это для примера.
Лучше конечно обобщить.
Приходит [0..N), с равной вероятностью получения любого из значений.
Нужно получить [M0..M1], или [0..M) (не так важно на самом деле).

Значение из входа можно брать несколько раз, чтобы получить одно для выхода.

Вероятность получения любого значения на диапазоне [0..M) должна быть одинаковая.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925810
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа.


Ну не...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925812
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений.

На двух - незаметно. Но форма уже меняется.

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.

Похоже ты не заметил что смещение каждый раз разное, это предыдущее значение
Код: plaintext
1.
static int sum = 0;


PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
Потестил на C# тоже работаетРезультат
Код: plaintext
 83886080: 0.1666 0.1666 0.1666 0.1666 0.1666 0.1667
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
static class Program {
	const int N = 10;
	const int M = 6;

	static Random rand = new Random();
	static int prev = 0;

	static int my_rand() {
		prev = (prev + rand.Next(N) + rand.Next(N)) % M;
		return prev;
	}

	static void Main(string[] args) {
		var arr = new int[M];
		for (int i = 1; i < 100000000; i++) {
			if ((i & 0xFFFFFF) == 0) {
			Console.Write($"\r {i}: ");
				foreach(var x in arr) Console.Write($"0.{(Int64)x * 10000 / i} ");
			}
			arr[my_rand()]++;
		}
	}
}

...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925819
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Значение из входа можно брать несколько раз, чтобы получить одно для выхода.
то есть входное значение используется как генератор случайных целых чисел из фиксированного набора, и никакого другого генератора мы использовать не можем?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925824
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Давай отвлечемся.

Вот линейный метод.

Код: plaintext
1.
2.
3.
4.
int rand(void){
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}



Может нам посмотреть на него и поднять кое-какие идеи?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925830
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925833
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
hVostt
Значение из входа можно брать несколько раз, чтобы получить одно для выхода.
то есть входное значение используется как генератор случайных целых чисел из фиксированного набора, и никакого другого генератора мы использовать не можем?


Да, всё верно, в этом и смысл :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925838
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
Потестил на C# тоже работает


Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider:

Код: powershell
1.
2.
3.
4.
5.
6.
7.
    0  100009746 14,29%
    1  100000838 14,29%
    2   99993654 14,28%
    3   99992243 14,28%
    4  100008260 14,29%
    5   99992411 14,28%
    6  100002848 14,29%



Видим небольшие, но всё же отклонения, хм..
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925855
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
Потестил на C# тоже работает


Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider:

Код: powershell
1.
2.
3.
4.
5.
6.
7.
    0  100009746 14,29%
    1  100000838 14,29%
    2   99993654 14,28%
    3   99992243 14,28%
    4  100008260 14,29%
    5   99992411 14,28%
    6  100002848 14,29%



Видим небольшие, но всё же отклонения, хм..
отклонения в количествах всегда будут, даже если рандомайзер идеальный. Надо, чтобы с ростом количества вариантов отклонения стремились к нулю.

ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925856
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?


Ну тут нормально, я просто смысла пока не понимаю.
Почему 2 раза, а не 3, допустим.
И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке.

Задача решена? ))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925858
Фотография ну я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Прошу прощения за такое название топика )

Вот задача.

На вход поступают случайные числа, допустим от 0 до 9, шанс выпадения любого из чисел одинаковый.
Однако нам нужны только случайные числа от 2 до 7, с таким же одинаковым шансом выпадения.

Решение, пропускать числа, не попадающие в рейндж, не очень интересно.
Нужно именно преобразование.
Можно что-то сохранять между операциями.
Но в идеале чистое математическое преобразование нужно :)

Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение.

Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными.

Так что два варианта - фильтр по диапазону и перекодирование отличаются лишь видом фильтра и наличием перекодирования.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925859
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?


Конечно, либо надо первое число целенаправлено выкинуть.
В идеале, хотелось бы решение без состояния.

Но и состояние тоже подойдёт, если будет понятно, что оно позволяет решить задачу.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925862
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну я
Если значения от 0 до 9 каждое является случайным, то их диапазон не важен. И фильтр по вхождению в диапазон и есть правильное решение.


С фильтром понятно. Но мы можем долго не получать следующего значения при сужении фильтра.


ну я
Что касается перекодирования из одного диапазона (10 значений) в другой (6 значений) то надо знать физику значений. Если физика - это случайность, то можно перекодировать как угодно, главное не 2 входных в 1 выходное. И потому можно вырезать любые 6 значений из входных и переобозвать в любом соответствии с выходными.


Брать остаток от деления, например?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925866
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
mayton
Кстати периодическое вычитывание генератора rand.Next(N) + rand.Next(N) должно быть обоснованным.

Хвост нас не ограничивал. Но я себе понимаю так что мы должны экономно и по хозяйски отнестись
к работе полученных случайных чисел. Может они ценны для нас? Криптографически сложны?
Может они идут из другой галлактики с длинным лагом?


Ну тут нормально, я просто смысла пока не понимаю.
Почему 2 раза, а не 3, допустим.
И ещё погонял на разных диапазонах, и получаю в принципе достойное распределение, с отклонениями не больше, чем в исходном потоке.

Задача решена? ))

Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно.
Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная.
У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной
долей вероятности попадает в 2 либо 3 большую нижнюю коробку.

Вобщем такая вот физическая метафора.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925869
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,
число штук элементов большего диапазона,
равное остатку от целочисленного деления N\M должно просто скользить по меньшему диапазону.
Остальные мапятся по кругу строго 1:1
вот и всё.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925871
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Имя пользователя1
ещё вопрос: надо ли, чтобы самый первый вызов нашей функции, используя предоставленный рандомайзер целого числа [0 ... N-1] не более k раз, мог дать равновероятное число [0 ... M-1] ?


Конечно, либо надо первое число целенаправлено выкинуть.
В идеале, хотелось бы решение без состояния.

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

очевидно, задачу легко решить напрямую и без состояний, только если N k делится на M, потому что k использований рандомайзера дают N k равновероятных исходов, которые надо равномерно раскидать на M групп.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925884
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
но это в любом случае не будет идеальный рандом в математическом смысле.
точнее, рандом-то будет идеальный (если использовать идеальный рандомайзер), но равные шансы для [0 ... M-1] никак не сделать.

по сути, здесь любое состояние - это результат предыдущих вызовов рандомайзера, то есть опять всё те же N k исходов
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925887
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Погоди. Я себе представил 10 маленких коробок. В которые падают шары. Равномерно. Линейно.
Эти 10 малых коробок стоят на 7 больших коробках так что общая длина - ровная.
У коробок - нет дна и верха. Но случайных шар. Попавший в 2 верхнюю коробку с разной
долей вероятности попадает в 2 либо 3 большую нижнюю коробку.

Вобщем такая вот физическая метафора.


Да, прекрасная метафора!
Хотелось бы формулу ))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925895
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вобщем всё просто.

Просто выдаем шар из той нижней коробки в которой их больше.

Только буфер надо.

Грубо говоря мой алгоритм - буферизированный. Например как только рухноло
с неба > 50 шаров - начинаем на каждый новый шар просто извлекать
из самой тяжелой коробки.

Profit.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925899
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T

Потестил на C# тоже работает

потестил на Java - результат противоречит математике и здравому смыслу

Задал N=2, M=1000

Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925901
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну.. в малой коробке еще ест варианты.
1) Мы однозначно кидаем шар в большую.
2) Есть выбор кинуть чуть правее или чуть левее. Здесь не нужно случайный генератор.
Здесь нужно просто шары по кругу разбрасывать. чтоб 30% падало например в 1 большой
ящик и 40% в следующий большой.

Мою мысль легко понять если нарисовать коробки и падающие шары.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925902
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
то, что ты говоришь, можно понимать двояко.

Одно из пониманий дает возможность точно предсказать, какой следующий шар извлечется.
т.е. тогда на входе поток случайный у тебя окажется, а на выходе последовательно детерминированный.
заполнение выходного потока должно сохранять видимость случайности той же характеристики, какова случайность входного потока.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925903
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да это добротность генератора. О которой хвост пока еще не говорил.
Линейность - будет. Добротность - ХЗ.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925905
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton

....начинаем на каждый новый шар просто извлекать
из самой тяжелой коробки.

Profit.

Нифига не понял.

Самое главное, не понимаю, что значит "самой тяжелой коробки"
может ли быть такое, что коробки одинаковые по весу?
если да, то фигня получится - даже матиматически доказывать не надо )))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925908
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Фуух.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925909
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Dima T

Потестил на C# тоже работает

потестил на Java - результат противоречит математике и здравому смыслу

Задал N=2, M=1000

Понятно, что последовательность нифига не случайная, но вывод программы этого не показывает
последовательность случайная, но для каждого результата нет равновероятности
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925910
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

не думаю, что это добротность.

но твой "буфер" с "моим" слайдом головы/хвоста можно соединить так:

мапим по кругу N на M
и заполняем M в рамках текущего мапа до тех пор, пока не заполнится каждая ячейка в M
в рамках фиксированного мапа, независимо от числа зерен, упавших в каждый горшок.
В момент каждого полного заполнения в М, когда в каждой ячейке есть хотя бы одно зерно,
независимо от размера насыпавшихся горок,
циклически смещаем мапировку на единицу и обнуляем горшки.
Продолжаем сыпать до следующего заполнения/попадания в каждe. из ячеек "буфера".
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925916
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925918
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Dima T
PS Имя sum не очень подходящее. В процессе творчества смысл переменной поменялся, а название осталось ((
Потестил на C# тоже работает


Я потестил на C#, на больших объёмах, входящий поток RNGCryptoServiceProvider:

Код: powershell
1.
2.
3.
4.
5.
6.
7.
    0  100009746 14,29%
    1  100000838 14,29%
    2   99993654 14,28%
    3   99992243 14,28%
    4  100008260 14,29%
    5   99992411 14,28%
    6  100002848 14,29%



Видим небольшие, но всё же отклонения, хм..

Отклонение в 0.01% можно на погрешность списать. Ты бы лучше потестил на нужных тебе M:N. У меня есть объяснение почему это работает для 10:6, собственно думал что получил решение для этого частного случая, но я не понимаю почему это работает для разных M:N, пробовал разные варианты, но со значениями не более 20.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925919
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну или если все мои коробки завернуть в карусель...

Кручу-верчу случайное число хочу.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925924
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
а, ну тем более)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925925
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
итого, задача решается только для частных кейсов N и M. В общем случае будет только приблизительное решение.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925931
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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)
Двойной вызов рандома, с чисто "програмной" точки зрения расточительно. Кроме того, смысл двойного (а не тройного, пятерного, десятерного) - я вообще не понимаю.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925938
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

что значит "приблизительное решение"?

статистическая вероятность вообще только на бесконечном числе испытаний.
Любая конечная серия дает всегда приближение.
"приблизительное решение", это когда и на бесконечном числе испытаний распределение не выравнивается.
А в рамках кратких серий длиной << M и о распределении судить нет возможности.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925945
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я понял что rand() в C++ кривоват, меня натолкнул тройной на мысль что с двойным решение правильное
Код: plaintext
1.
sum = (sum + rand() % N + rand() % N + rand() % N) % M;


тут итого ухудшается
Код: plaintext
989855744: 0.1671 0.1662 0.1671 0.1662 0.1671 0.1662


но тоже самое на C#
Код: sql
1.
prev = (prev + rand.Next(N) + rand.Next(N) + rand.Next(N)) % M;


никак не влияет на итого
Код: plaintext
 989855744: 0.1666 0.1666 0.1666 0.1666 0.1666 0.1666
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925949
Фотография ну я
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Ну я пока один вариант вижу, гарантированный.

Если на входе у нас [0..M)
А нам нужно [0..N)

То нужно брать из входа N значений, затем делить на M.

Нужно примешивать свое случайное число.
Чтобы размазать входящее количество M на диапазон N*M, а уже после этого из него разбивать на N значений.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925952
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну я
hVostt
Ну я пока один вариант вижу, гарантированный.

Если на входе у нас [0..M)
А нам нужно [0..N)

То нужно брать из входа N значений, затем делить на M.

Нужно примешивать свое случайное число.
Чтобы размазать входящее количество M на диапазон N*M, а уже после этого из него разбивать на N значений.

В игре с коробками я предложил не случайное число а циклический счетчик.

Тоже равномерное распределение но с плохой корреляцией.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925958
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Давай отвлечемся.

Вот линейный метод.

Код: plaintext
1.
2.
3.
4.
int rand(void){
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}



Может нам посмотреть на него и поднять кое-какие идеи?

+1

надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925959
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
mayton
Давай отвлечемся.

Вот линейный метод.

Код: plaintext
1.
2.
3.
4.
int rand(void){
  next = next * 1103515245 + 12345;
  return (unsigned int)(next/65536) % (RAND_MAX + 1);
}



Может нам посмотреть на него и поднять кое-какие идеи?

+1

надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного.

Да. Мы просто знаем что этот датчик более-менее идеальный. И все что нам надо - параметризировать его Хвостовскими
входными данными.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925964
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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

корреляция налицо
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925966
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T

+1

надо сюда как-то сунуть наши входные случайные 0..9, тогда возможно хватит одного случайного.


ЗАЧЕМ ?

И так уже есть случайное число (псевдослучайное), зачем в него что-то совать?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925967
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
В случае M > N, как мне кажется, корреляция тоже должна быть. "Двойной" рандом, такую корреляцию конечно будет сглаживать, но это как-то из пушки по воробьям (плюс двойной рандом должен портить генератор, давая вместо "равномерного" "нормальное" распределение)

Хоть явно это не заявлено в ТЗ, но я пока не рассматриваю случаи M > N, хотя есть мысли.

Leonid Kudryavtsev
3)
Двойной вызов рандома, с чисто "програмной" точки зрения расточительно. Кроме того, смысл двойного (а не тройного, пятерного, десятерного) - я вообще не понимаю.

Одинарный вызов rand() это уже зло, но у ТС случайные числа откуда-то идут на вход, поэтому считаю неуместным обсуждать источник их появления. У меня вызов rand() только для моделирования поставленной задачи и не более того.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925971
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Смотрите. Подвох в самом вопросе Хвоста.

Он говорит. Есть черный ящик. На вход идут какие-то случайные числа от 0 до 9.
Я хочу получить числа от 2 до 7 (включительно) тоесть 6 штук.

10 не кратно шести и никак не делится.

Какие еще требования?

Чистая функция? Скорее нет. Мы не можем за 1 итерацию сразу получить ответ. Не хватает энтропии.

Конечный автомат? Скорее да. Имеем право накапливать результат.

Что еще известно об ограничениях. Ничего.

Можем накапливать энтропию хоть 1000 лет.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925973
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если мы будем делить 6 на 10 то получим рациональный коэффициент вида 6/10 или 3/5

Если мы будем умножать random(10) на рациональный тип данных вида rational(3,5)
и в результате - получим красивое линейное распределение РАЦИОНАЛЬНЫХ
чисел в диапазоне от 0 до 5. Далее - сложение и перенос в диапазон от 2 до 7.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925974
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Все таки. если мы начинаем эмперитечески изобретать, без чтения книжет по теории вероятности, я предлагаю отталкиваться от простых случаев.

На входе есть последовательность случайных 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'а (((
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925978
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
эх, так и хотся узнать ваши оклады :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925993
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
5 стр. в мгновение ока наплодили.
Хочу отметиьт обстоятельство. ТС пишет, что нужно такое же (равновероятное) распределение . Что он поимает под этим? Терминоогически это не означает случайность. Где-то уже это было отмечено.

Равные доли каждой цифры. Это абсурд. В пределе только если. Поэтому самое простое - больший период накручивать на меньший. Или формула генератора. Это тоже было.

Я просто рассуждаю. При накручивании целого кол-ва кругов (НОД(N,M)) равномерность очевидна. Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться.

А если ещё разрешено было повторно использовать часть входого потока, о-о-о!..
Ну то есть неплохо бы окончательно оформить формулировку.

Мэйтону на заметку: нормальным будет ср.арифметич. независимых случ.величин с одинаковыми M и D. Сумма же одинаковых - нет. Можжно представить: в 1-м случае это 2-мерная мишень расстреленная в десятку, во 2-м - некий микст точек на мишени, достаточно равномерный, Мож=сумме.

Диме: аплодирую! Нормальная мысль была: при кривизне датчика их двойное использование вдруг да сгладит несколько кривизну. Я так понял.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925999
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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, потому сделать нельзя.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926002
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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926004
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
если, например, в некоторой ветке if-в хватило k-p вызовов getRandomN для возврата значения, то это эквивалентно тому, как если бы мы в конце сделали два лишних вызова, и вместо одного исхода, имевшего вероятность N k-p , получили бы N p исходов, имевших вероятность N k

короче, все ветки можно "выровнять" до N k
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926007
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
как если бы мы в конце сделали два лишних вызова
здесь не "два", а "p".
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926035
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В целом мысль понял и даже, частично! согласен. Только я бы упростил формулировку

Есть N^K возможных значений, где K это кол-во данных/циферек на входе, нужно разложить по M равным кучкам....

Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."

Во вторых, все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось.

Как я представлял бы данную задачу __практически__ (мы же в форуме программирование):
Есть аппаратный генератор случайных чисел от 0..N (я бы для упрощения предложил 0 / 1), нужен алгоритм генерации числа 0..M максимально экономно использующий входные данные.

Попытаюсь объяснить свою идея с /dev/null:
Предположим на входе поток битов, нам нужно набрать байты. Пусть мы банально склееваем биты друг с другом.
Понятно, что если на входе пришло 15 битов (k=15), мы можем склееть только один байт, а 7 оставшихся битов уйдут в /dev/null. Станет ли от этого первый получившися байт хуже "вероятным"?

С точки зрения делетанта, сидящего на окладе ниже рыночного )))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926037
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
все же остается не очень понятно, почему мы обязаны раскладывать все возможные значения по M равным кучкам. Предположим, что у нас есть M кучек, куда нам нужно разложить "ровно", +/dev/null куда мы можем выкинуть то, что не разложилось.
пожелание автора топика.
22078105
авторРешение, пропускать числа, не попадающие в рейндж, не очень интересно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926039
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."
но требуемая функция не может сколько угодно забирать данные из потока. Она должна отработать за конечное время.
потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926046
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

то, что работает с rand, это не функция, в формальном смысле, и не может ею быть.
Это процесс, вычислительный.
Процессу принципиально разрешается работать бесконечно.

PS
Красиво рассуждаешь.
Чувствуется образование.
Совсем не частый для форума случай
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926079
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
Leonid Kudryavtsev
Почему "частично", т.к. у автора поток данных скорее бесконечный и "Если кругов дофига, то имеет ли значение для задачи, насколько нек-рые из меньших цифр будут менее вероятны? на мизер ведь, и этот мизер с каждым кругом будет уменьшаться."
но требуемая функция не может сколько угодно забирать данные из потока. Она должна отработать за конечное время.
потому, можно сделать только приблизительную равновероятность. Некоторые кучки получат на единицу больше, их вероятность будет на 1/N k выше чем у "маленьких кучек", и увеличивая k, мы сокращаем разницу


Вроде даже и согласен, но "не убедили"

Даже сел писать код, но дошел до того, о чем говорил mayton 22078740
остаток получается в виде дроби, и что с ним потом делать (как применить операцию остаток от деления к дроби), в 3-и часа ночи после работы как-то сильно заумно )))
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926096
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926097
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
то, что работает с rand, это не функция, в формальном смысле, и не может ею быть.
Это процесс, вычислительный.
Процессу принципиально разрешается работать бесконечно.
согласен.
только на момент первого (да и любого по счету) результата рандомайзер будет вызван конечное количество раз.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926148
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома

Брезенхем с этим не согласен.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926165
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
Имя пользователя1
боюсь, что равномерно смапить (0, 1, ... 9) в (2, 3, ..., 7) не получится без вспомогательного рандома

Брезенхем с этим не согласен.
?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926179
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В чем проблема равномерно распределить смасштабированный вещественный диапазон 2..7 в целочисленный диапазон 2..7?
Эта задача уже полвека, как решена.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926193
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30

И на него падают короткие отрезки длиной в 3 целых единицы. Далее - накопительный алгоритм
который режет эти отрезки на единицы и распределяет их на пятёрки.

Накапливаем гистограмму пятерок и решаем когда высота слолбика настолько высока чтобы сгенерировать
следующее целое случаное число уже в диапазоне целых от 1 до 6. Или от 2 до 7.

Как физическая аналогия - 10 стаканов в которые падают капли жидкости.
И распределяются по 6 стаканам через систему труб в соотвествии с справедливостью.

По подобию коробок которые я описывал.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926215
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Потому что НОК(6,10) = 30

Это частный случай.
А в общем случае используется алгоритм Брезенхема.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926225
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты имеешь в виду не-кратные m,n
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926244
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются.
Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926249
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Какие рекомендации по накоплению и сбросу?

Сколько прибавлять? И через сколько сбросить.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926263
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
количество итераций велико, то и итоговые данные будут распределены равномерно.
ставилась задача не о равномерном распределении на множестве итераций, а о равновероятности каждого конкретного результата
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926270
Alibek B
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нет. Было написано: "с таким же одинаковым шансом выпадения".
Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926272
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Alibek B.
Нет. Было написано: "с таким же одинаковым шансом выпадения".
Если целочисленный диапазон 0..9 (с равномерным выпадением) привести к целочисленному диапазону 2..7 (2+x/9*5, с распределением дробной части по алгоритму Брезенхема), то там тоже будет равномерное выпадение.

Брезенхем - это итеративный алгоритм. Он бежит по оси X, или Y (где уклон меньше)
и делает опциональн либо инкремент +1 для противоположной оси либо не делает
ничего на этой итерации. Он фиксирует ошибку коррекции по Y на каждой итерации.

В настоящий момент - неясно как применить Брезенхема без O(n). Тоесть без линейного
пробегания по всему диапазону.

Разумеется мы не всегда ищем O(1) но хотелось - бы не снизить зависимость от длины интервала.

Ведь Хвост мог захотеть отображать дипазон MAX_LONG на какое-то число раза в полтора меньшее чем MAX_LONG.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926279
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
господа, "алгоритм Брезенхама" - это про попиксельное рисование?

не понимаю, как он относится к сабжу.

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926284
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1,

алгоритм заменяет частые импульсы на редкие за счет периода
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926286
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере

Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает
наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить
можно только без детерминизма.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926289
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Имя пользователя1

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере

Сходу поправка. Надо помнить о законе больших чисел и о некой кумулятивной памяти которой обладает
наш черный ящик или алгоритм. Если наш алгоритм это некая функция с состоянием F тогда его смапить
можно только без детерминизма.
закон больших чисел - следствие вероятностей. Не надо от него плясать.

задача - уметь создать число, равновероятное из М вариантов., пользуясь специальным рандомайзером.

22078797 тут я собрал условие в кучу, по ответам ТСа на вопросы.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926291
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Если числа целые, то нам надо 10 равновероятных вариантов превратить в 6 (2,3,4,5,6,7).

ИМХО Без запоминания чего-нибудь после расчета никак не получить равную вероятность.

Как вариант накапливать сумму
Код: plaintext
1.
2.
3.
4.
thread_local int sum = 0;
sum += rand();
while (sum > 5) sum -= 6;
return sum + 2;


ИМХО Этот вариант был нормальный, не надо никаких лишних 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.
0: 99995522     16,6659%
1: 99998844     16,6665%
2: 99998109     16,6664%
3: 99988758     16,6648%
4: 100003266    16,6672%
5: 100015500    16,6693%

0: 100005194    16,6675%
1: 99993056     16,6655%
2: 100007572    16,6679%
3: 99989516     16,6649%
4: 99998428     16,6664%
5: 100006233    16,6677%

0: 99986272     16,6644%
1: 100012836    16,6688%
2: 100022654    16,6704%
3: 100000588    16,6668%
4: 99980680     16,6634%
5: 99996969     16,6662%

0: 99998352     16,6664%
1: 99997879     16,6663%
2: 99979625     16,6633%
3: 99996773     16,6661%
4: 100013016    16,6688%
5: 100014354    16,6691%

0: 99990543     16,6651%
1: 100008784    16,6681%
2: 99998934     16,6665%
3: 100013355    16,6689%
4: 99990095     16,6650%
5: 99998288     16,6664%

0: 99994203     16,6657%
1: 100024501    16,6708%
2: 99991417     16,6652%
3: 99992826     16,6655%
4: 99994362     16,6657%
5: 100002690    16,6671%

Код: 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.
static class Program {
	const int N = 10;
	const int M = 6;

	static Random rand = new Random();
	static int prev = 0;

	static int my_rand() {
		prev = (prev + rand.Next(N)) % M;
		return prev;
	}

	static void Main(string[] args) {
		var arr = new int[M];
		for (int i = 1; i < 100000000*M; i++) {
			if ((i & 0xFFFFF) == 0) {
				int min = 100000000, max = 0;
				foreach(var x in arr) {
					if(x < min) min = x;
					if(x > max) max = x;
				}
				Console.Write($"\r {i}  min:{min}  max:{max} delta:{((double)max/min-1)*100:N4}%");
			}
			arr[my_rand()]++;
		}
		Console.Write("\r                                                                \r");
		for(int i = 0; i < arr.Length; i++) {
			Console.WriteLine($"{i}: {arr[i]}\t{(double)arr[i]/1000000/M:N4}%");
		}
	}
}


Надо бы на ГСЧ посерьезней затестить, но и тут уже видно что есть отклонения всего на 0.005%, но они тоже случайные, каждый раз разные, не в пользу какого-то конкретного элемента.

PS Только для случаев N>=M
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926298
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть?

Еще есть мысль что тебе не стоит париться о качестве встроенного генератора в данной конкретной задаче.
Вряд-ли мы получим что-то более качественное.

В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10
И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг".

Скорее всего маппинга не существует а есть некое управляющее воздействие на конечный автомат
(FSM) который периодически выдает (а может и не выдать!) очередное псевдо-случайное число
как отклик на внешнее воздействие.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926305
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
В качестве краш-сравнения я предлагаю заменить random(10) на циклический счетчик i % 10
И предлагаю подумать вообще о чем рассуждал Хвост когда он хотел просто получить "маппинг".

Счетчик не взлетел, случайность нужна
Код: plaintext
1.
2.
3.
4.
5.
0: 209999999    35,0000%
1: 90000000     15,0000%
2: 0    0,0000%
3: 210000000    35,0000%
4: 90000000     15,0000%
5: 0    0,0000%
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
	static int prev = 0;
	static int rnd = 0;

	static int my_rand() {
		//prev = (prev + rand.Next(N)) % M;
		rnd++;
		if(rnd >= N) rnd = 0;
		prev = (prev + rnd) % M;
		return prev;
	}
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926315
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
...Станет ли от этого первый получившися байт хуже "вероятным"?..
Нет не станет. По Колмогорову: для случайной послед-сти любая подпослед-сть случайна.
Но автор хочет фсю её.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926317
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть?

Фиг его знает. Тут исходник , посмотри, может чего поймешь.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926323
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
...Станет ли от этого первый получившися байт хуже "вероятным"?..
Нет не станет. По Колмогорову: для случайной послед-сти любая подпослед-сть случайна.
Но автор хочет фсю её.
Немного наврал в формулировке, попозже уточню ...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926349
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
mayton
Dima T, в шарпах тоже линейный конгруэнтный? Или там другая реализация? Можешь глянуть?

Фиг его знает. Тут исходник , посмотри, может чего поймешь.

Хм... та тут похитрее будет.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926354
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98, уточняю: как раз для нашего случая. Это св-во случайной послед-сти называют частотоустойчивостью (у нас - это равновероятность). Я, правда, предполагаю, что наш поток не просто равновероятен, а ещё и псевдослучаен.
Тогда согласо определению каждая "законная" подпо-сть обладает частотоустойчивостью, т.е. равновероятностью.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926365
Borodat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И не программа:

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
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926369
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число.
Тогда оставшиеся значения тоже будут равномерно распределены.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926373
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky
Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число.
Тогда оставшиеся значения тоже будут равномерно распределены.

Это старый боян из собеседований. Типа брошена игральная кость. И надо получить
Случайное число от 1 до 25 за наименьшее число бросков.

Но эта идея с гневом отвергнута где-то в начале бесед.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926376
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton

Но эта идея с гневом отвергнута где-то в начале бесед.

Она с гневом отвергнута в самом стартовом посте
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926382
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Спасибо.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926385
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

F(n + 1) = 2 + (F(n) - 2 + S(n+1)) / 5

Не читал но осуждаю.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926408
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
господа, "алгоритм Брезенхама" - это про попиксельное рисование?

не понимаю, как он относится к сабжу.

вот у нас равновероятное число из набора (0, 1, 2, 3, 4), или, например, k таких чисел, если вызвали рандомайзер несколько раз
как его равномерно смапить на набор (0, 1, 2) ?
покажите на примере

это алгоритм равноценен предложенному в 22078706
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926423
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
mayton

Но эта идея с гневом отвергнута где-то в начале бесед.

Она с гневом отвергнута в самом стартовом посте
она отвергнута по простой причине
так делать в общем случае нельзя
этот же генератор может использоваться в получении другой вероятности

н-р, если нам нужно получить две независимые случайные величины a, b
то "обрезка" будет "искажать" распределение другой величины

например, так очень сильно накололись с довольно известным преобразованием такого типа
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
function NormalDev(const AEngine: IHepRandomEngine):RandFloat;
var v1,v2,r:RandFloat;
begin
  //Преобразование Бокса — Мюллера
  repeat
     v1:= 2.0 * AEngine.flat() - 1.0;
     v2:= 2.0 * AEngine.flat() - 1.0;
     r:=sqr(v1)+sqr(v2);
  until r<=1;
  {$IFDEF OriginalGauss}
  Result:=v1*sqrt(-2*ln(r)/r);
  {$ELSE}
  Result:=(v1+v2)*sqrt(-ln(r)/r);
  {$ENDIF}
end;

оно кстати до сих пор входит в стандартную библиотеку многих языков, но в реальных вычислительных задачах его использовать нельзя
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926512
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Но это очень плохо масштабируется на больших числах.

может уже писали за 7 страниц, но после этих загадочных намёков есть смысл посмотреть полное условие
там наверняка ещё какие-то детали всплывут...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926647
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Почему вы думаете что полное условие вообще существовало?

Авторы часто задают тему топика еще без осознания всех деталей. Детали уточняются в процессе. И это нормальный процесс.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926665
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Но в идеале чистое математическое преобразование нужно :)
Чистое математическое преобразование - бесконечная десятичная дробь в бесконечную шестиричную дробь.
Можно преобразовывать по частям - добавили несколько десятичных цифры, выдали несколько шестиричных, вот только есть такой момент - может оказаться, что добавление очередной десятичной цифры даст перенос в шестиричный разряд, который мы уже выдали раньше...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926767
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
У меня щас когнитивный диссонанс случился.
Если не можешь, зачем завёл топик?
А если можешь, нафига завёл топик?


А как ты думал, когда задаешь такие задачки предполагается что можешь сделать какую то экспертизу решения.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39926888
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а, ну раз конь, то вот вам "писча для коня"
на 36:00 тут занятная тема, может получится куда-то прикрутить
YouTube Video
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927100
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30


В первую очередь об этом подумал. И писал уже выше про частный случай, когда НОК(A, B) = A * B, на больших числах придётся выбирать очень много значений из потока. Математически, задача решена. Практически -- страдает большими проблемами избыточности.


Alibek B.
Любые. На каждой итерации остатки накопляются и добавляются к текущему значению, после чего сбрасываются.
Если считать, что случайные данные распределены равномерно и количество итераций велико, то и итоговые данные будут распределены равномерно.


А нужно, чтобы вероятность была применима к каждому следующему числу на выходе, а не на больших объёмах статистически.


Имя пользователя1
ставилась задача не о равномерном распределении на множестве итераций, а о равновероятности каждого конкретного результата


+

Речь о вероятности, а не о распределении. Статистика на больших выборках просто показывает эту вероятность.

Т.е. это значит, что если на вход придёт 10 одинаковых цифр, значит на выходе должно быть тоже что-то такое. А превращение любого входа в равномерное распределение по рейнджу :)

Короче я не математик и можете закидывать камнями.

Предложенные в топике решения выглядит рабочими, на больших выборках. Но хочется же красиво )
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927102
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky
Самое простое - это просто отбрасывать все значения которые не входят в выходной диапазон и считывать следующее входное число.
Тогда оставшиеся значения тоже будут равномерно распределены.


Метод Монте-Карло.
Самый простой способ, да.

Но выходит за рамки задачи, которую хочется решить.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927103
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
полудух
может уже писали за 7 страниц, но после этих загадочных намёков есть смысл посмотреть полное условие
там наверняка ещё какие-то детали всплывут...


Там было употреблено слово "допустим" :)

Это же не ТЗ-шка для реализации за срок. А задача для размышления, для генерации интересных идей.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927104
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iOracleDev
А как ты думал, когда задаешь такие задачки предполагается что можешь сделать какую то экспертизу решения.


Ржевский (Р) пришел к Пьеру Безухову(Б) на вечеринку. Там кто-то грит:
- Шестьдесят первый!
Взрыв смеха. Другой грит:
- Двенадцатый!
Опять хохот. (Р) спрашивает у (Б): что тут у вас за приколы?
- А это мы анекдоты рассказываем. Все их уже запомнили, чтобы каждый
раз не повторять, пронумеровали их.
...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927131
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
mayton
Нам не нужен весь диапазон. Давайте представим что у нас есть отрезок от 0 до 30. Почему 30? Потому что НОК(6,10) = 30


В первую очередь об этом подумал. И писал уже выше про частный случай, когда НОК(A, B) = A * B, на больших числах придётся выбирать очень много значений из потока. Математически, задача решена. Практически -- страдает большими проблемами избыточности.

Не решена она математически, mayton уже писал об этом
mayton
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений.

На двух - незаметно. Но форма уже меняется.

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.

Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927132
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.

Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных.
Нет.

Если A - случайная величина точек на 1 кости (от 1 до 6) а B - количество точек на 2 кости то
их произведение даст линейное распределенеи от 1 до 36.

А их сумма - даст "три ступеньки". Ломаную линию разных высот. В количестве 12 полосок. И чем больше костей мы сложим
в сумму - тем ближе и ближе мы будем аппроксимировать следующий график-колокольчик.



В котором заранее мы будем знать моду, медиану, среднее квадратическое и прочее.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927135
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Dima T

пропущено...

Равновероятность исчезает. По большому счету не обязательно сумма, любая функция от нескольких случайных.

Нет.

Убедил. Только сумма. Но если ты собрался использовать НОК, то надо будет складывать, умножение тут не уместно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927141
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мой алгоритм падающих капель (Fallen Fluids) или отрезков (тоже самое) не предполагает сложения
самих случайных величин. Есть просто учёт величины жидкости в стаканах.

Есть еще один вариант. Я-бы назвал его quantum particles. Тоже самое но из 10 источников вылетает
1 электрон случайным образом. Попадает на некоторый роутер. Или мультиплексор.
Который случайным образом направляет электрон в 1 из двух возможных прёмников.
В пропорции. Приемники образуют батарею из 6 штук. Это и есть выход нашего черного ящика.

В данном алгоритме никакой кумулятивности нет. Мы получаем результат сразу.

Но честно говоря Хвост поставил меня в парадоксальную ситуацию. Для роутинга электрона
мне нужен новый ГПСЧ. Которого у меня нет. Получается рекурсия. Я строю ГПСЧ для Хвоста
но для реализации этого ГПСЧ мне нужен еще один ГПСЧ.

Вобщем ладно. Если заменить случайных роутинг электронов на простоё счет по модулю

30/6 = 5.

Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон
влево или вправо.

Это немножко сломает авто-корреляцию. Тоесть на выходе мы получим ГПСЧ который "косит"
в сторону наличия мелких монотонных последовательностей.

Хвост как тебе квантовый?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927150
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Вобщем ладно. Если заменить случайных роутинг электронов на простоё счет по модулю

30/6 = 5.

Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон
влево или вправо.

По сути ты изобрел тоже что и я 22078250 только сложнее.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927159
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Без накопления. Quantum particles выдает сразу результат.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927170
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Для роутинга электрона мне нужен новый ГПСЧ. Которого у меня нет.

да есть у тебя всё
коли уж добрался до электронов, то лови случайные фотоны из окружающей среды и юзай в кач-ве СЧ
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927180
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты понимаешь что такое "метафора" ?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927185
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
а ты понимаешь, что такое "алгоритм"?


зы: там нет слова "метафора"
поэтому в идеале - бери НЕЙТРИНО. Их тупо больше и они повсюду.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927187
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я тебя чем то обидел? Чего злой такой?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927202
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ты модер и друг Димы в одном лице.

P.S.
А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N).
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927203
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
:рука-лицо.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927208
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Ты модер и друг Димы в одном лице.

Даже не знаю что сказать. Может не стоит теории заговора искать? Забей и не заморачивайся.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927216
Фотография полудух
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Я тебя чем то обидел? Чего злой такой?

чё если без смайликов, то сразу злой?
ты как первый день замужем
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927222
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
import java.util.stream.IntStream;

import static com.google.common.base.Preconditions.checkArgument;

public class QuantumParticles {

    int[] counters = new int[5];

    public int nextQuantumFiveToThreeState(int x) {
        checkArgument(x >= 0 && x <= 5);
        // |    0    |    1    |    2    |.....
        // |  0  |  1  |  2  |  3  |  4  |.....
        int res = -1;
        switch (x) {
            case 0 :
                res = 0;
                break;
            case 1 :
                res = counters[x] % 3 < 2 ? 0 : 1;
                break;
            case 2 :
                res = 1;
                break;
            case 3 :
                res = counters[x] % 3 < 1 ? 1 : 2;
                break;
            default:
                res = 2;
                break;
        }
        counters[x]++;
        return res;
    }

    public static void main(String[] args) {

        QuantumParticles quantumParticles = new QuantumParticles();

        int feedbackHistogram[] = new int[3];
        IntStream.range(0, 3000).forEach(i -> {
            int factor = i % 5;
            int feedback = quantumParticles.nextQuantumFiveToThreeState(factor);
            feedbackHistogram[feedback]++;
            System.out.printf("input = %d, output = %d\n", factor, feedback);
        });
        
        for(int i = 0 ; i < feedbackHistogram.length;i++) {
            System.out.printf(" %d : %d\n", i, feedbackHistogram[i]);
        }
    }

}


Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
..................
input = 3, output = 1
input = 4, output = 2
input = 0, output = 0
input = 1, output = 0
input = 2, output = 1
input = 3, output = 2
input = 4, output = 2
input = 0, output = 0
input = 1, output = 1
input = 2, output = 1
input = 3, output = 2
input = 4, output = 2
 0 : 1000
 1 : 1000
 2 : 1000

BUILD SUCCESSFUL in 0s
3 actionable tasks: 2 executed, 1 up-to-date



Возможно есть плохая авто-корреляция. Но это уже надо не мне а другим. Пускай ищут и доказывают.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927244
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Но честно говоря Хвост поставил меня в парадоксальную ситуацию. Для роутинга электрона
мне нужен новый ГПСЧ. Которого у меня нет. Получается рекурсия. Я строю ГПСЧ для Хвоста
но для реализации этого ГПСЧ мне нужен еще один ГПСЧ.


Почему же? У тебя тот же самый ГПСЧ, ты можешь брать дополнительные значения оттуда. Так как мы имеем дело с вероятностью, что один вход, что несколько -- разницы-то нет :)


mayton
30/6 = 5.

Тоесть крутим счетчики по модулю 5 и в зависимости от результата швыряем электрон
влево или вправо.

Это немножко сломает авто-корреляцию. Тоесть на выходе мы получим ГПСЧ который "косит"
в сторону наличия мелких монотонных последовательностей.

Хвост как тебе квантовый?


Вообще норм. Но получается, что у тебя коллизия на конкретных пограничных значениях, что не позволяет построить стройную концепцию. Понятное дело, что это лучше, чем журавль в небе, но всё же :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927245
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Если надо смасштабировать до 10:6 - то делается всё по аналогии.


А если надо масштабировать до нескольких порядков?

Лан. У Димы алгоритм тоже рабочий :) Правда один из выступающих тут говорил, что так как на входе величина вероятностная, то что бы мы не делали с ней, на выходе получим такую же вероятностную величину.

Но у меня свербит больше из-за отсутствия математической базы.
Практически там и Монте-Карлой можно обойтись, или любой из вариаций алгоритма Димы.

Воть. Похоже придётся расчехлять тервер...
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927263
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
P.S.
А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N).

приближается, и довольно быстро ...
деление же просто масштабирование

PS: не узнаю вас в гриме
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927271
Colt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Если я правильно понял, то задачу можно сформулировать так:
На основании входной последовательности, которая состоит из чисел (вариантов чисел 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 Я ни фига не математик, потому прошу прощения, если написал хрень.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927348
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Colt,

я к тому же выводу пришёл 22078797
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927374
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Colt

Через это задачу можно решить, если нарушить «закон сохранения информации»:
Способ №1: Терять часть информации (например, в первом посте упоминался вариант с пропуском входных чисел, которые не входят в выходной диапазон)
Способ №2: Генерировать дополнительную информацию (например, квантовый алгоритм от mayton, где добавляется информация, что первые два из трех яблок из мелкой коробки №1 попадают в большую коробку №0, а третье – в №1)

PS Я ни фига не математик, потому прошу прощения, если написал хрень.

Все правильно.

+Способ №3: Отказаться от синхронизма. И накапливать энтропию. Это алгоритм падающих капель в стакан
о которых я также писал выше. У него будет задержка в выдаче информации. И потребитель информации (Consumer)
технически получит ее не сразу а по факту накопления этой самой "энтропии".

Код: java
1.
2.
3.
4.
5.
6.
7.
class FallenFluidsImplementation {

   void addConsumer(Consumer<Integer> consumer) {...}

   void fallFluid(int n) {...}

}
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927616
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Colt
...например, квантовый алгоритм от mayton, ... прошу прощения, если написал хрень.
я вас умоляю, забудьте, пож, слово "квантовый" в данном топике. Уж лучше дискретный, хоть и все они здесь дискретные.
Насчёт хрени ... она в том, что сколько мнений, столько и постановок. Тепреь ЕиМНИП, то ТС мечтал что-то вроде такого. Если 100500 раз подряд выпала "9", то и в диапазоне 2-7 доолжно быть что-то аналогичное (уверен, что смысл сохранил). И как это прикажете понимать? в чём д.б. аналогия с "9"?..
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927623
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)
exp98
P.S.
А сумма равномерных Гаусса не даст. Только среднее арифм. или по Ц.пред. теореме S/sqr(N).
приближается, и довольно быстро ...
деление же просто масштабирование
PS: не узнаю вас в гриме
Смыв грим, замечу, что простая сумма случайного ряда гуляет как хочет. В то время как ср.арифм - к матож.
Осталось ещё уточнить, какую сумму подразумевал М-н. Послед-сть частичных сумм одного ряда или послед-сть сумм независимых сл.вел? ЦПТ про предел последнего. Для послед-сти 2-х слагаемых случ.вел. спор вообще бессмысленен.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39927641
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

разговор про распределение
т.е. делается много повторений формулы. Грубо говоря, каждое значение выдаваемое формулой это куда упала очередная снежинка и смотрится куда она осела, вот полученный общий контур и будет распределение

если кидать одну равнораспределённую величину будет ровный однородный слой
если кидать сумму двух величин - будет треугольник
...
при довольно большом количестве просуммированных (естественнно независимых велечин), "распредение бросков" этой функции будет стремиться к нормальному, всё как в предельной теореме - Локальная теорема Муавра — Лапласа
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928175
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), я не использую свистипедию в качестве научно-технического ресурса. И обычно не читаю ссылки туда в кач-ве подтверждения.
Меня постоянно мучил вопрос, чего это я не помню такого знаменателя. И действительно, я ошибся с делением на корень (неверно посчитал дисперсию), нет там никакого корня - всё то же ср.арифм. В данном случае я пользуюсь заслуженным "справочником Корн" (перевод от 1984 г, подобный есть в инете).

Находим п.18.6-5. Предельные теоремы.
Увы мне, там действительно есть и случай с просто суммой. Но для схождения суммы необходимо специальное условие. Наверное поэтому мне не запомнилось или вообще мимо прошёл. Я не могу пока упрощённо его передать. Всё дело в дисперсиях. Не могут быть они быть какими угодно.
Я пока уверен, что сумма одинаковых равномерных сл.величин не будет сходитья к нормальному за просто так, нужен спец.фильтр.

Там же, п.18.8-1, табл. 18.8-3 самый конец -- предельная т. Муавра-Лапласа, но! для суммы биномиальных распр-й. Да и то со спец. условиями.

Обещаю, что покопаться на предмет "локальной ТМ-Л", потому что за просто так суммы к нормальному не сходятся. И нормальное - это не любой "колокольчик", а с определёнными св-вами.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928183
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Старый школьный боян

[spoiler]
YouTube Video
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928218
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

Я ж лекции по ММК и теории измерений сканировать не буду, по памяти теоремы гуглю.
Кто ж виноват, что википедия самый быстронаходимый ресурс.
В данном случае википедия права - во всяком случае то, что я помню и то, что написано там - сходится (гифка там довольно хорошая).
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928472
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), остаюсь при своём мнении,опираясь ещё дополнительно на Мат.энциклопедию(под ред. Виноградова), Зубков,Чистяков "Сборник задач по теор.вер"(там справочно дана теория тоже), Феллер .........
Кстати вчера ошибся, лишнее вычёркиваю:
этоЯТам же, п.18.8-1, табл. 18.8-3 самый конец -- предельная т. Муавра-Лапласа, но! для суммы биномиальных распр-й. Да и то со спец. условиями.Какая связь формулы М_Л с суммой случ.распределений?

По поводу всё же суммы снова Яп.18.6-5. Предельные теоремы. Тут интерпретация достаточного условия в моей вольной трактовке: отклонения должны оч-чень хорошо уменьшать при n-->беск-ти (а не просто даже наличие одной такой подпослед-сти). Собственно римерно так я и представлял проблему достаточ. усл.

Кроме того, неформальные рекомендации по применению ФМ-Л к биноминальному распр-ю
npq>20, и желательно р достаточно близко к 1/2. Иначе (маленькое р) рекомендуется приближение распределением Пуассона.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928474
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Старый школьный боян
Школьный? даже просто случайная величина вне школьной программы (старой, во всяк).
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928500
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Старый школьный боян
Посмотрел картинку, ну и что?
Конус, изготовленный с намерением получить "горку" (трения там всякие, вес горошин и т.д. мешают им разлететься). Послед-сть фильтров для исходной выборки. Пуассон тоже горкой. Где сумма независимых распределений?
И наверное там говорят, мол, клянусь, получился Гаусс! следует верить?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928524
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
mayton
Старый школьный боян
Посмотрел картинку, ну и что?
Конус, изготовленный с намерением получить "горку" (трения там всякие, вес горошин и т.д. мешают им разлететься). Послед-сть фильтров для исходной выборки. Пуассон тоже горкой. Где сумма независимых распределений?
И наверное там говорят, мол, клянусь, получился Гаусс! следует верить?

Давай порассуждаем что происходит с шариком когда он ударяется о колышек.
Наверное пофиг на его траекторию. И даже пофиг куда он полетит после 1 колышка.
Важно что мы не можем (реально не можем) спрогнозировать его попадание на колышки 2-го
уровня. Мы можем просто предположить что его вектор направления впаво и влево - случаен.

Далее - гистограмма просто моделирует сумму случайных величин. Суть которых - векторы
левый или правый.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928529
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

тут видишь на этом факте построена вся теория измерений и расчёта погрешностей косвенных измерений

более хороший тынц по предельным теоремам
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928652
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), авторВ этой статье не хватает ссылок на источники информации.
Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена.
Вы можете отредактировать эту статью, добавив ссылки на авторитетные источники.
Эта отметка установлена 15 мая 2011 года.И я с этим роботом полностью согласен.

Мне очень странно. Я могу понять поколение вики. Для них не имеется большей реальности, чем виртуальная. Но неужели мои ссылки на заслуженные, речензируемые, с ответственными редакторами и корректорами не имеют веса?

Вспоминаю не столь давнюю комедию с "совершенными числами", когда выяснилось ( как? не может быть!), что в свистипедии оказыается тоже бывают опечатки.

kealon, ты хотя бы пытался разобраться в условии применимости т.н.(по свистипедии) "ЦПТ Линдеберга"? Там, где предел -->1 (И пусть выполняется условие Линдеберга:). При каком условии? Да там чушью по белому написано |X-mu|>eps*Sn. Больше, Карл! Больше!!!
Что это означает? Сумма сходится при сколь угодно больших или малых отклонениях от среднего!

Я же вам всем дал перевод Американского издания Справочника, Корн. В нём чистым русским языком написано, что при сколь угодно меньших отклонениях. Меньше,Карл! Меньше!!! Ну да, подумаешь - опечатка! Ну и чему будем верить? или голосование?
Что это означает? Вот скорее всего, что квадраты отклонений д.б. сколь угодно маленькими на бесконечности! Вот эту мою трактовку и стоит опровергать.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928654
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вы хотя бы прониклись тем, что, если ваши отклонения(их квадраты) будут на бесконечности больше любого заранее числа, то ни о каком предельном распределении с КОНЕЧНОЙ дисперсией не м.б и речи?
Я не оспариваю других букв в этой "хорошей ссылке". С условием применимости у этих знатоков точно проблемы. Одно это говорит о качестве вашей любимой свистипедии.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928658
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, я впервые пытаюсь разгадать принцип теорвера пусть даже простого физического устр-ва. Я не вижу здесь суммы (тем более независимых) случайных величин. Больше склоняюсь, что реализовано либо биномиальное распределение при р=1/2 и показано, что оно стремится к горбу. И тогда я верю, что горб Гауссов со скоростью О(1/корень(N)) согласно ЛокТМ-Л.
Либо тут как-то соединено оно же с законом больших чисел (для распр. тоже при р=1/2). ЗБЧ - это когда для каждой отдельной случ.вел. ср.арифм. --> к мат.ож. Но у каждой своя скорость и для одного N отклонения у горошин будут разные, но в целом вокруг середины как мишень.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928669
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
kealon, ты хотя бы пытался разобраться в условии применимости т.н.(по свистипедии) "ЦПТ Линдеберга"? Там, где предел -->1 (И пусть выполняется условие Линдеберга:). При каком условии? Да там чушью по белому написано |X-mu|>eps*Sn. Больше, Карл! Больше!!!
Что это означает? Сумма сходится при сколь угодно больших или малых отклонениях от среднего!

Я же вам всем дал перевод Американского издания Справочника, Корн. В нём чистым русским языком написано, что при сколь угодно меньших отклонениях. Меньше,Карл! Меньше!!! Ну да, подумаешь - опечатка! Ну и чему будем верить? или голосование?
Что это означает? Вот скорее всего, что квадраты отклонений д.б. сколь угодно маленькими на бесконечности! Вот эту мою трактовку и стоит опровергать.
да, это ограничение многие упускают, но с физической стороны, погрешность больше скольки-то процентов от исходной величины просто бессмыслена, т.е. бред сразу отсекается как недостоверный.
Эта теория даёт очень удобный матаппарат для расчёта погрешностей аналитическими методами. Для практического применения этого достаточно.

Для более правдивого приближения есть ММК

Кроме того, в ссылке приводится более сильное утверждение, чем то, что привёл я изначально. С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли. А уж как там это обосновывать, мне как практику тяжело лезть в эти дебри.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928670
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я ещё раз повторюсь. У меня есть заслуженные печатные издания. К прежнему списку добавю детализацию.
Мат-я энциклопедия, гл.ред. Виноградов, в 5-ти томах (каждый том в свой год ~1980)
редколлегия: Адян, Александров, Бахвалов, ..., Кудрявцев, Мищенко, Свешников, Тихонов, ..., Яблонский.
Конкретно про сумму слex.вел. статья Петрова.

про ЦПТ см. т.5, с.804-806
про условие Линдеберга-Феллера (необх.и достаточное для суммы) см. т.3, с.285, "Линдеберга-Феллера теорема". Записаное в этой форме условие более чем прозрачное. Для схождения частичных сумм к нормальному н. и д. условия Линдеберга . Т.е. чтобы нормированная центрированная вероятность сколь угодно малых и больших больших отклонений -->0. В частности наверное поэтому тоже ср.арифм. одинаковых величин сходится к нормальному. У них как раз суммарные квадраты дисперсии -->0.

Дополнительно см. Петров В.В., Суммы независимых случ-х вел-н, М. 1972.

P.S. Я уже лет 30 часто замечаю пренебрежения к условиям применимости тех или иных теоретических утверждений к практике.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928671
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), я много забыл и ещё больше не знаю.
Трудно вспомнить будет схему поверки?
С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928689
[quote=mayton]Старый школьный боян

[spoiler]
YouTube Video
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928690
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Алексей Роза, там кстати должно двух-модовое получиться в конце. Просто ящик такого мелкого размера
что эти два холмика сливаются в волну и это не очевидно.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928692
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По моему предложению по Бернулли.

Для 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.
def combinations(k: BigInt, n: BigInt): BigInt = {
    if (k > n || n < 1 || k < 1) throw new IllegalArgumentException
    if (k == n) return BigInt(1)
    // TODO: Refactor. Optimize
    fact(n) / ( fact(k) * fact(n - k) )
  }

  def bernully(k: BigInt, n: BigInt, p : Double) : Double = {
    combinations(k, n).toDouble * pow(p, k.toDouble) * pow(1.0 - p, (n-k).toDouble)
  }

    val p = 0.66666666666

    printf(" |")
    for(n <- 1 to 10) {
      printf("%d |".format(n))
    }
    printf("\n")

    for(k <- 1 to 10) {
      printf("%d |".format(k))
      for(n <- 1 to 10) {
        if (k <= n) {
          val b = bernully(k, n, p)
          printf("%f | ".format(b))
        } else {
          printf("%f | ".format(0.0))
        }
      }
      printf(s"\n")
    }
  }


Вроде нигде не ошибся. Если криво - поправте.

По практике. Я так и не решил что делать с длинной серией испытаний которые уже использованы?
Можно ли их выбросить (5 штук) или сделать сдвиг на 1 испытание и считать предыдущие - независимыми.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928731
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
kealon(Ruslan), я много забыл и ещё больше не знаю.
Трудно вспомнить будет схему поверки?
С равномерными величинами мы его, кстати, на ММК экспериментально и проверяли
элементарная проверка, так же как и для любой другой гипотезы на распределение

пусть есть функция f(), которая даёт значение в интервале (a,b]
делим интервал на равные промежутки (количество из целесообразности задаём)
заводим массив для подсчёта
много-много раз запускаем функцию и смотрим в какой интервал попало, увеличивая элемент массива

в итоге, в массиве получается контур функции распределения: c y *F(x) - можно нарисовать для наглядности

Совпадение проверяем методом наименьших квадратов:
Имеем предполагаемое распределение (в данном случае нормальное) и посчитанное: F'(x i ) и c y *F(x i ) соответственно. Для линейного уравнения находим коэффициент c y и коэффициент корреляции Пирсона (в том же экселе стандартная функция, при построении графика, если кто не знает как его считать)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928942
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan)
Кроме того, в ссылке приводится более сильное утверждение , чем то, что привёл я изначально.
- Они обманут тебя. Уплывут, а потом вернутся.
- Ну-у, это вряд ли. (цэ)

Условия Линдеберга-Феллера-Леви необх и достат. Если что-то более сильное, то оно для более спец случаев.
Скорее всего имеет место путаница. Если утверждать про голую сумму, то см. условия Л-Ф-Л. Если про неким образом "нормализованную" случ величину, являющуюся ф-цией от суммы независ случ величин, то нет ничего невозможного. В кач-ве "нормализации" обычно рассматривают Sn/n либо (Sn - nMi)/Sum Dn. Об них и есть ЗБЧ, ЦПТ, ТМ-Л и ЛокТМ-Л.
Судя по всему "нормализация" и стала причиной взаимонепонимания.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928952
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, насчёт сдвинуть ли не скажу. Вообще-то можно проверить гипотезу о независимости.

А насчёт аналогий с Паскаля тругольником вы мне не оставили вчера возможности.
Не сумел высказаться вчера, что сумма равновероятностных просто провоцирует на заблуждения.
Уже для 2-х дискретных слагаемых понятно, что в суммарном распределении более центральные значения могут комбинироваться большим кол-вом способов, нежели краевые. Что и показывал треугольник. Отсюда делался перенос с ошибкой на предельный случай. Забывая, что дисперсия суммы независимых == сумме дисперсий. И, в случае одинаковых Д, D sum --> беск.
Имено поэтому в теоремах делается "нормировка" в терминах энного кол-ва сигм. Но это уже будет функцией от суммы случайных величин, а не сама сумма. И теоремы - для функции.

P.S.
За последние месяцы уже 2-й случай, когда я читаю свистипедию и по ссылке, а там оказывается путаница, отсутствие источников и вообще бардак. Может это тенденция?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39928975
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton, появилось мнение, что 1 сдвиг недостаточен. Если подразумевается конечно, что есть датчик, и из его потока последвательно выбираются серии. Тогда сдвинутые последовательности будут просто напросто коррелировать, что даст их ковариационную матрицу <>0, хорошо не равной. Получится Д(а+б)=Д(а)+Д(б)+cov(а,б). А для независимых cov() = 0.
Примерно так.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39929044
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
mayton, появилось мнение, что 1 сдвиг недостаточен. Если подразумевается конечно, что есть датчик, и из его потока последвательно выбираются серии. Тогда сдвинутые последовательности будут просто напросто коррелировать, что даст их ковариационную матрицу <>0, хорошо не равной. Получится Д(а+б)=Д(а)+Д(б)+cov(а,б). А для независимых cov() = 0.
Примерно так.

Да. Согласен надо сдвигать на величину которая даст 100% независимость от предыдущего измерения.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39929081
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
kealon(Ruslan)
Кроме того, в ссылке приводится более сильное утверждение , чем то, что привёл я изначально.
- Они обманут тебя. Уплывут, а потом вернутся.
- Ну-у, это вряд ли. (цэ)

Условия Линдеберга-Феллера-Леви необх и достат. Если что-то более сильное, то оно для более спец случаев.
Скорее всего имеет место путаница. Если утверждать про голую сумму, то см. условия Л-Ф-Л. Если про неким образом "нормализованную" случ величину, являющуюся ф-цией от суммы независ случ величин, то нет ничего невозможного. В кач-ве "нормализации" обычно рассматривают Sn/n либо (Sn - nMi)/Sum Dn. Об них и есть ЗБЧ, ЦПТ, ТМ-Л и ЛокТМ-Л.
Судя по всему "нормализация" и стала причиной взаимонепонимания.
ещё раз повторю: деление на константу это просто сжатие оси X
т.е.:
Summ(rnd(), k) / k - диапазон (0, 1]
и
Summ(rnd(), k) - диапазон (0, k]

оба приближаются к нормальному
только у второго сигма и матожидание больше в k раз
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39929168
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), если не считать того, что в последнем случае на каждой итерации всего лишь суммы нормальные, каждый раз с бесконечно возрастающими М и Д, и т.о. не может быть речи о сходимости.
Короче говоря, есть теорема Линденберга-Феллера-Леви о необх. и достаточном условии сходимости суммы. Можно их опровергать сколько влезет, от них не убудет.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39929234
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98,

простые вопросы:

в проверке 22083479

r^2 будет приближаться к 1 при увеличении k ?
r и c y зависят от того выберем мы 1-й или 2-й вариант?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39930761
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kealon(Ruslan), вы не тот тезис отстаиваете. Аккуратнее читайте например здесь .
это уже будет функцией от суммы случайных величин , а не сама сумма. И теоремы - для функции.

Упрямый компутер хорошо лечит от инерции мышления. Одна таблетка. Вычислить 20 итераций суммы и записать данные в файл. Затем то же самое для ср.арифм. Затем сравнить результаты и ответить на вопрос: равны ли значения? и задуматься почему.

Вторая таблетка теоретическая. Нужно ответить на 2 вопроса
а) можно ли конечным числом сумм получить чистое теоретическое Нормальное распределение? (для одинаковых равномерных)
б) тот же вопрос для ср.арифм.
Ответы(не подглядывать): а) и б) - оба нет.
И тоже задуматься почему.

Я больше этот вопрос не обсуждаю.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39930771
kealon(Ruslan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
exp98
Упрямый компутер хорошо лечит от инерции мышления. Одна таблетка. Вычислить 20 итераций суммы и записать данные в файл. Затем то же самое для ср.арифм. Затем сравнить результаты и ответить на вопрос: равны ли значения? и задуматься почему.

20 раз???? какой в этом смысл?

распределения проверяются массовым рассчётом - 22083479
что бы хотя бы картинку визуально получить, интервальчиков на 100, нужно хотя бы миллиончик раз прогнать тестовую функцию
...
Рейтинг: 0 / 0
223 сообщений из 223, показаны все 9 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]