LINUX.ORG.RU
ФорумTalks

задача


0

0

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

Есть n изначально пустых урн, и в них кидают шарики

Процесс продолжается до тех пор, пока есть пустые урны.

Попадание в любые урны равновероятны

f(n) - мат ожидание количества бросаний

Найти асимптотику f(n) с точностью до O большого

очевидно n = O(f(n)),

немного подумав f(n)=O(n^2)

А точнее можно?

★★

Re: задача

Можно.. ты сначала найди этих идитов, что шарики в урны кидать будут..

MiracleMan ★★★★★ ()
Ответ на: Re: задача от MiracleMan

Re: задача

>Можно.. ты сначала найди этих идитов, что шарики в урны кидать будут..

хорошо, автоматизируем процесс:

bool flag;
cont int n = xxx;
bool a[n+1];
int N = 0;

for i in [1..n] do a[i] = false; done

do {
   N = N + 1;
   a[random от 1 до n] = true;
   flag = true;
   for i in [1..n] do 
       flag = flag and a[i];
   done
} until flag;

print N;

ival ★★ ()
Ответ на: Re: задача от MiracleMan

Re: задача

+1, в урны нужно кидать виндовсь. Чтобы экологию не нарушать.

bugmaker ★★★★☆ ()
Ответ на: Re: задача от bugmaker

Re: задача

>+1, в урны нужно кидать виндовсь. Чтобы экологию не нарушать.

хорошо s/шарики/дистрибутивы с пиратской или лицензионной вындой/

ival ★★ ()
Ответ на: Re: задача от ival

Re: задача

Это чё такое? Это не Лисп. Скобок зажилили, жмоты :E

bugmaker ★★★★☆ ()
Ответ на: Re: задача от ival

Re: задача

Когда весь виндовсь в урны перекидают, настанет Век Всеобщего Благоденствия и такие мелочные вопросы перестанут волновать человечество.

bugmaker ★★★★☆ ()
Ответ на: Re: задача от bugmaker

Re: задача

>Это чё такое? Это не Лисп. Скобок зажилили, жмоты :E

Специально ни на каком, что бы не придирались

ival ★★ ()
Ответ на: Re: задача от ival

Re: задача

И всё равно придрались :P луче бы сразу на Лиспе.

bugmaker ★★★★☆ ()
Ответ на: Re: задача от bugmaker

Re: задача

> И всё равно придрались :P луче бы сразу на Лиспе.

+1

Е.В.Л.

anonymous ()

Re: задача

f(n) -- сумма n независимых случайных величин, с геометрическим распределением с параметрами соответственно 1, (n-1)/n, (n-2)/n, ... , 2/n, 1/n.

дальше посчитать -- упражнение нехитрое

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

>сумма n независимых случайных величин, с геометрическим распределением

А можно немного по подробнее

ival ★★ ()
Ответ на: Re: задача от anonymous

Re: задача

>дальше посчитать -- упражнение нехитрое

Погуглил. Нашел что такое геометрическое распределение и сумма случайных величин

Асилил нехитрое упражнение.

ответ n+n^2*(n-1)/n!

если в вычислениях не накосячил (утром проверю)

Спасибо

ival ★★ ()
Ответ на: Re: задача от anonymous

Re: задача

> f(n) -- сумма n независимых случайных величин, с геометрическим распределением с параметрами соответственно 1, (n-1)/n, (n-2)/n, ... , 2/n, 1/n.

Прости брат анонимус, но ты бред сказал. Как может момент быть равен случайной величине?

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

> Как может момент быть равен случайной величине?

посчитай первый момент распределения коши (плотность f(x) = 1/pi*1/(1 + x^2). область определения --- вся числовая прямая)

hatefu1_dead ()
Ответ на: Re: задача от hatefu1_dead

Re: задача

> посчитай первый момент распределения коши

Если ты про центральный, то он не существует. А причем тут это?

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

То есть, первый _начальный_ не существует.

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

> А причем тут это?

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

в общем, оффтоп это.

hatefu1_dead ()
Ответ на: Re: задача от hatefu1_dead

Re: задача

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

Но моменты в любом случае детерминированы.

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

>> f(n) -- сумма n независимых случайных величин,

> Как может момент быть равен случайной величине?

ну имелась в виду не f(n) а сл. величина от которой f(n) -- матожидание

anonymous ()
Ответ на: Re: задача от ival

Re: задача

правильный ответ
f(n) = sum( (n-k)/k, k=1..n ) = n*ln(n) - (1-gamma)*n + 1/2 + O(1/n);
(gamma = .577... -- постоянная Эйлера)

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

потерял единицу -- должно быть
f(n) = sum( n/k, k=1..n )
асимптотика n*ln(n)

anonymous ()
Ответ на: Re: задача от anonymous

Re: задача

>f(n) = sum( n/k, k=1..n )

Я пересчитал. У меня тоже столькоже получилось

ival ★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.