Рандом.
От: WolfHound  
Дата: 24.03.03 10:20
Оценка:
Вот придумалось.

Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.
Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?
A, B, X, Y — Действительные числа.
N — Натуральное.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Рандом.
От: UgN  
Дата: 24.03.03 11:32
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?
WH>A, B, X, Y — Действительные числа.
WH>N — Натуральное.


   (Y - X) 
N  -------
   (B - A)
Re: Рандом.
От: Кодт Россия  
Дата: 24.03.03 11:38
Оценка: 14 (2)
Здравствуйте, WolfHound, Вы писали:

WH>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?
WH>A, B, X, Y — Действительные числа.
WH>N — Натуральное.

Можно избавиться от A и B.

Генератор чисел [0,1]
Какова вероятность того, что сумма N чисел попадет в [x,y],
x = (X-N*A)/(B-A)
y = (Y-N*A)/(B-A)

Очевидно, что сумма N чисел в [0,1] лежит на отрезке [0,N]. Также очевидно, что плотность вероятности симметрична относительно центра этого отрезка.

Еще раз модифицируем задачу.
Генератор чисел [-1,+1]. Сумма s лежит на отрезке [-N,+N]
x = (X-N*(A+B)/2)/(B-A)*2
y = аналогично
Теперь плотность вероятности симметрична относительно s=0.

График ее — кривая порядка N-1, (в случае нечетных степеней — есть перелом в точке 0)
Следовательно, вероятность попадания на [x,y] — интеграл от плотности вероятности — есть функция степени N.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[2]: Рандом.
От: WolfHound  
Дата: 24.03.03 15:11
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>
UgN>   (Y - X) 
UgN>N  -------
UgN>   (B - A)
UgN>

Неверно.
A=1000
B=1001
X=1
Y=2
N=1000000
И что получаем?
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: Рандом.
От: UgN  
Дата: 24.03.03 16:46
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH> Неверно.

Sorry, я условие невнимательно прочитал
Re[2]: Рандом.
От: WolfHound  
Дата: 24.03.03 16:57
Оценка:
Здравствуйте, Кодт, Вы писали:
У меня по проще


Если (B*N<X)||(Y<A*N) то вероятность 0
Если (X<A*N)&&(B*N<Y) то вероятность 1
Если (A*N<X)&&(Y<B*N) то вероятность (Y-X)/(B*N-A*N)
Если (A*N<X)&&(B*N<Y) то вероятность (B*N-X)/(B*N-A*N)
Если (X<A*N)&&(Y<B*N) то вероятность (Y-A*N)/(B*N-A*N)
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Рандом.
От: UgN  
Дата: 24.03.03 16:58
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?
WH>A, B, X, Y — Действительные числа.
WH>N — Натуральное.

Если генератор равномерный, то, при достаточно большом N,
сумма чисел будет стремиться к

A + B
----- * N
  2



А вот вероятность будет зависеть от заданных Х и Y.
Как посчитать не знаю.

В целом, имхо, график будет похож на нормальное распределение...


Я сильно заблуждаюсь?
Re[2]: Рандом.
От: Кодт Россия  
Дата: 24.03.03 20:05
Оценка:
Здравствуйте, UgN, Вы писали:

UgN>В целом, имхо, график будет похож на нормальное распределение...


Именно оно.
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[3]: Рандом.
От: Les Россия  
Дата: 25.03.03 11:02
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Кодт, Вы писали:

WH> У меня по проще
но не правильно

WH>

WH>
...
WH>Если (A*N<X)&&(Y<B*N) то вероятность (Y-X)/(B*N-A*N)
...
WH>


Во-первых, в условии имеет место интервал, так что при X=Y p не 0. Мелочь, но .

Во-вторых, бросаем две игральные кости:
A=1
B=6
N=2

Считаем по вашей формуле
a) вероятность суммы 3
б) вероятность суммы 7

Получаем одинаковые результаты. Надо объяснять, что это неправильно?
Re[4]: Рандом.
От: WolfHound  
Дата: 25.03.03 17:12
Оценка:
Здравствуйте, Les, Вы писали:

Les>но не правильно


Les>Во-первых, в условии имеет место интервал, так что при X=Y p не 0. Мелочь, но .
Задача в действительных числах. При X=Y мы получаем точку. На любом отрезке бесконечное количество точек. Итого 1/oo=0.

Les>Во-вторых, бросаем две игральные кости:

Les>A=1
Les>B=6
Les>N=2
А где X, Y?
Les>Считаем по вашей формуле
Les>a) вероятность суммы 3
Les>б) вероятность суммы 7
Какой суммы? В чем вероятность?
Les>Получаем одинаковые результаты.
Чтоб я понял какие результаты? ты условие хорошо прочитал?
Les>Надо объяснять, что это неправильно?
Потрудись пожалуйста.

ЗЫ Есть тут один(не будем показывать пальцем)любил к моим постам цеплятья...
ЗЗЫ Я не против критики если она обоснована.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[5]: Рандом.
От: Pushkin Россия www.linkbit.com
Дата: 26.03.03 07:02
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>

WH>ты условие хорошо прочитал?
WH>Потрудись пожалуйста.
WH>ЗЫ Есть тут один(не будем показывать пальцем)любил к моим постам цеплятья...

Как модератор этого форума указываю вам на излишнюю резкость ваших высказываний.

Как человек, в своё время изучавший теорвер и статфизику, уверяю вас, что ваши ответы неверны. Это легко увидеть в двух частных случаях — N=2 и N>>1. Первый из них легко решается геометрически, а второй — хорошо известное распределение Гаусса (в интеграл ошибок ваши формулы точно не переходят). Более того, думаю (хотя здесь я уверен меньше), что этими двумя частными случаями и исчерпывается множество точных решений — для всех остальных N похоже грозит неподъёмная мутота с интегралами.
Re[6]: Рандом.
От: Кодт Россия  
Дата: 26.03.03 08:05
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Как человек, в своё время изучавший теорвер и статфизику, уверяю вас, что ваши ответы неверны. Это легко увидеть в двух частных случаях — N=2 и N>>1. Первый из них легко решается геометрически, а второй — хорошо известное распределение Гаусса (в интеграл ошибок ваши формулы точно не переходят). Более того, думаю (хотя здесь я уверен меньше), что этими двумя частными случаями и исчерпывается множество точных решений — для всех остальных N похоже грозит неподъёмная мутота с интегралами.


Пусть известны функции p[k](x), p[m](x) распределения вероятностей суммы k и m чисел (на отрезке [0,1]) соответственно.
p[1] — ступенчатая функция, на отрезке [0,1] равна 1, за пределами — 0.

p[k+m](x) = Integral[t=0..(k+m)] p[k](x) * p[m](t-x) dt

Если p[k], p[m] — кусочно-полиномиальные, степени k-1, m-1 соответственно, то p[k+m] — кусочно-полиномиальная, степени k+m-1.

В общем, p[2] — это домик (ломаная линия)
x<=0 : p=0
x<=1 : p=x
x<=2 : p=2-x
x>=2 : p=0

p[3] получится сверткой p[1] и p[2], но мне лень выписывать... В итоге мы имеем четыре кусочка параболы.

Количество кусочков p[n] (не считая плато 0 слева и справа) равно 2^n, это несложно вывести из формулы свертки.
Поэтому, скажем, до n=4...6 еще можно , а потом
http://files.rsdn.org/4783/catsmiley.gif Перекуём баги на фичи!
Re[7]: Рандом.
От: Pushkin Россия www.linkbit.com
Дата: 26.03.03 08:14
Оценка:
Здравствуйте, Кодт, Вы писали:

К>Поэтому, скажем, до n=4...6 еще можно , а потом


Помнится, классе в пятом получил большое удовольствие, возведя ручками 2^160 (49 десятичных знаков, уместилось на развороте тетрадного листка). Думаю, здесь удовольствие для таких же маньяков Хотя возможно есть рекуррентная формула...
Re[6]: Рандом.
От: WolfHound  
Дата: 26.03.03 09:06
Оценка:
Здравствуйте, Pushkin, Вы писали:




Поставте мне нолик.
... << RSDN@Home 1.0 beta 5 >>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re: Рандом.
От: MichaelP  
Дата: 26.03.03 13:16
Оценка: 46 (3)
Здравствуйте, WolfHound, Вы писали:

WH>Вот придумалось.


WH>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?
WH>A, B, X, Y — Действительные числа.
WH>N — Натуральное.

По рабочим обстоятельствам не мог активно участвовать в обсуждении, но на досуге немного подумал.
Что свертку надо сделать, как и Кодт
Автор: Кодт
Дата: 26.03.03
, догадался быстро... Даже пошел дальше, заменил свертку произведением через преобразование Фурье. Но, когда надо было сделать обратное преобразование Фурье от sinc^n (sin(x)/x)^n — сломался.

А сегодня решил посмотреть на недавно мною найденном, но уже горячо любимом ресурсе. И нашел решение! Опять же — ближе всего оказался Кодт
Автор: Кодт
Дата: 24.03.03
.

P.S. Прошу извинить меня, если кто еще хотел решить эту задачу самостоятельно.
Re[2]: Рандом.
От: Pushkin Россия www.linkbit.com
Дата: 26.03.03 13:31
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>По рабочим обстоятельствам не мог активно участвовать в обсуждении, но на досуге немного подумал.

MP>А сегодня решил посмотреть на недавно мною найденном, но уже горячо любимом ресурсе. И нашел решение!

Знать, где найти — самое ценное знание

А кстати (раз уж зашёл ), может подумаешь (немного ) и ещё над одним вопросом Кодта а именно №7
Автор: Кодт
Дата: 25.03.03
Re[5]: Рандом.
От: Les Россия  
Дата: 26.03.03 13:39
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Здравствуйте, Les, Вы писали:


Les>>но не правильно

WH>
Les>>Во-первых, в условии имеет место интервал, так что при X=Y p не 0. Мелочь, но .
WH> Задача в действительных числах. При X=Y мы получаем точку. На любом отрезке бесконечное количество точек. Итого 1/oo=0.

Сорри. И ведь специально посмотрел, какие A, B, X, Y. Вижу "действительные" а в голове отпечаталось "целые". Слишком долго дискреткой занимался.

Les>>Во-вторых, бросаем две игральные кости:

Les>>A=1
Les>>B=6
Les>>N=2
WH>А где X, Y?
Les>>Считаем по вашей формуле
Les>>a) вероятность суммы 3
Les>>б) вероятность суммы 7
WH>Какой суммы? В чем вероятность?
Les>>Получаем одинаковые результаты.
WH>Чтоб я понял какие результаты? ты условие хорошо прочитал?
Les>>Надо объяснять, что это неправильно?
WH>Потрудись пожалуйста.

Ох-ох-ох. Потружусь. Хотя пример с игральными костями неприменим из-за дискретности, суть не меняется. Посчитанная вами формула для вероятности (Если (A*N<X)&&(Y<B*N) то вероятность (Y-X)/(B*N-A*N)) Зависит только от разности Х и У. В то же время, при N>1 вероятность получить среднее (от A*N и B*N) выше чем получить краевое, вблизи A*N и B*N. Попробую нарисовать график плотности вероятности для
>A=0
>B=1
>N=2
|
|  /\
| /  \ 
|/    \
--------------
0  1  2

Сравни случаи [0,1] и [.5,1.5]. Площадь под графиком разная, а по твоей формуле должна быть одинаковая. Что касается решения задачи, то про это Кодт написал.
Re: Ещё похожая задача
От: Pushkin Россия www.linkbit.com
Дата: 01.04.03 08:05
Оценка:
Здравствуйте, WolfHound, Вы писали:

WH>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?

Если последовательно брать случайные числа равномерно из [0,1] то сколько в среднем их потребуется, чтобы в сумме преодолеть 1?


Ответ забавный — e.
Решения не знаю
Re[2]: Ещё похожая задача
От: MichaelP  
Дата: 01.04.03 09:26
Оценка:
Здравствуйте, Pushkin, Вы писали:

P>Здравствуйте, WolfHound, Вы писали:


WH>>Есть генератор случайных чисел с равномерным рапределением в промежутке [A, B]. С его помощью получают N чисел.

WH>>Вопрос: Какова вероятность того что сумма этих чисел попадет в промежуток [X, Y]?

P>

P>Если последовательно брать случайные числа равномерно из [0,1] то сколько в среднем их потребуется, чтобы в сумме преодолеть 1?


P>Ответ забавный — e.

P>Решения не знаю

Не самое красивое, но решение:

Обозначим P(n) — вероятность того, что сумма n равномерно распрделенных на [0,1] меньше 1.
Если напрячь гиперпространственное воображение и представить гиперкуб рассеченный гиперплоскостью, то можно получить следующее соотношение P(n) = P(n-1)/n. Т.е. P(n) = 1/n!.
Обозначим P'(n) — вероятность того, что сумма первых n-1 членов < 1, а сумма n членов больше. Т.к. из того, что сумма n членов < 1, однозначно следует, что сумма n-1 членов < 1, получаем, что P'(n) = P(n-1)-P(n).
Искомая величина равна SUM[n=2, n=...](n*P'(n)) = SUM[n=2, n=...](n*(1/(n-1)! — 1/n!)) = SUM[n=2, n=...](1/(n-2)!) = e
Re[3]: Ещё похожая задача
От: Pushkin Россия www.linkbit.com
Дата: 01.04.03 10:31
Оценка:
Здравствуйте, MichaelP, Вы писали:

MP>Если напрячь гиперпространственное воображение и


Нет, туго у меня с ним
Имхо уж лучше аккуратно проинтегрировать найденное тобой представление для функции распределения.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.