powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
25 сообщений из 223, страница 2 из 9
Случайный конь в вакууме
    #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
25 сообщений из 223, страница 2 из 9
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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