Здравствуйте, Cruelty, Вы писали:
C>Такая задачка: C>Подбрасывается правильная монетка, пока 2 раза подряд не выпадет орел. Какое математическое ожидание числа необходимых подбрасываний?
Где F(x) — функция Фибоначчи (F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5 ...)
Короче надо найти предел этого ряда при n --> в бесконечность.
Мне, признаться, слабо...
Могу только приблизительно...
Здравствуйте, Cruelty, Вы писали:
C>Здравствуйте, tinytjan, C>23 минуты с времени поста! Скорость ответа поражает! C>Я только текст ответа дольше бы набирал.
Если бы в условии требовалось доказательство, то пост появился бы не раньше чем завтра
Потому что честно говоря как получить строго формулу энного члена я не знаю
Здравствуйте, tinytjan, Вы писали:
T>Здравствуйте, Cruelty, Вы писали:
C>>Такая задачка: C>>Подбрасывается правильная монетка, пока 2 раза подряд не выпадет орел. Какое математическое ожидание числа необходимых подбрасываний?
T>Мдя... T>Короче получается что-то типа такого: T>
T>Где F(x) — функция Фибоначчи (F(0) = 1, F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5 ...) T>Короче надо найти предел этого ряда при n --> в бесконечность. T>Мне, признаться, слабо... T>Могу только приблизительно...
Хм, а у меня получилось СУММ(n*(n-1)/2^n). Откуда числа Фибоначчи? Что-то я упустил...
Здравствуйте, tinytjan, Вы писали:
T>Если бы в условии требовалось доказательство, то пост появился бы не раньше чем завтра T>Потому что честно говоря как получить строго формулу энного члена я не знаю
Я на все доказательство наверное минут 40 потратил в спокойной обстановке, а ето задача из телефонного интервью. Звери.
Здравствуйте, Cruelty, Вы писали:
C>Подбрасывается правильная монетка, пока 2 раза подряд не выпадет орел. Какое математическое ожидание числа необходимых подбрасываний?
Я уже подзабыл терминологию, но предположу что спрашивалось "сколько в среднем раз надо подбросить монетку, что дождаться пока выпадет подряд два орла"
С вероятностью 0 они выпадут на 1м подбрасывании
С вероятностью 1/4 они выпадут на 2м подбрасывании
С вероятностью 1/8 они выпадут на 3м подбрасывании
С вероятностью 2/16 они выпадут на 4м подбрасывании
С вероятностью 3/32 они выпадут на 5м подбрасывании
С вероятностью 5/64 они выпадут на 6м подбрасывании
С вероятностью 8/128 они выпадут на 7м подбрасывании
В числителе числа фибоначчи в знаменателе степени двойки.
Считаем на калькуляторе Visual Studio .Net 2003
double f1 = 0;
double f2 = 1;
double f3 = f1 + f2;
double d = 2;
double s = 0;
for (double index = 2.0; index < 1000.0; index += 1.0)
{
f3 = f1 + f2;
f1 = f2;
f2 = f3;
d *= 2;
s += index*f1/d;
}
Здравствуйте, hemmul, Вы писали:
H>Здравствуйте, adontz, Вы писали:
A>>
H>
H>P.S. однако занятно, что при N->oo вероятность оказывается не стремится к 1...
Вероятность того, что к n-ому шагу уже выпадет два подряд орла, стремится к 1.
Здравствуйте, _DAle_, Вы писали:
H>>P.S. однако занятно, что при N->oo вероятность оказывается не стремится к 1...
_DA>Вероятность того, что к n-ому шагу уже выпадет два подряд орла, стремится к 1.
скорее так:
Вероятность того, что к n-ому шагу уже выпадет по крайней мере два подряд орла, стремится к 1.
Здравствуйте, tinytjan, Вы писали:
T>Здравствуйте, Cruelty, Вы писали:
C>>Здравствуйте, tinytjan, C>>23 минуты с времени поста! Скорость ответа поражает! C>>Я только текст ответа дольше бы набирал.
T>Если бы в условии требовалось доказательство, то пост появился бы не раньше чем завтра T>Потому что честно говоря как получить строго формулу энного члена я не знаю
Доказательство примерно следующее.
Мат ожидание = СУММА(n * P(n)/2^n), где P(n) — количество 0-1 векторов длины n, в которых последние два бита единицы, и не существует собственного префикса этого вектора, содержащего две подряд идущие единицы.
Обозначим
Pi(j) — количество векторов длины i, в которых нет двух подряд идущих единиц, заканчивающиеся на бит j. Тогда
Pi(0) = Pi-1(0)+Pi-1(1)
Pi(1) = Pi-1(0) =>
Pi(0) = Pi-1(0)+Pi-2(0) (числа Фибоначчи)
Pi(1) = Pi-2(0)+Pi-3(0)
P(i) = Pi-1(1) — добавляем единицы ко всем этим векторам.
Здравствуйте, Cruelty, Вы писали:
C>Я сам до сих пор не знаю как получить ответ 6 без программки, а именно ето и требовалось сказать по телефону
Похоже задачу свели к сумме ряда Sum(n>=2, n*F(n-2)/2^n)
Вот как считается сумма похожего ряда (только попроще).
S=Sum(n>=0,F(n)/2^n)
S=1+1/2+Sum(n>=2,(F(n-1)+F(n-2))/2^n)=3/2+1/2*Sum(n>=1,F(n)/2^n)+1/4*Sum(n>=0,F(n)/2^n)=3/2+1/2*(S-1)+1/4*S
1/4*S=1
S=4
Здесь можно сделать тоже самое, только будет это раза в 3 подлинее
P.S. а всё таки как-то некрасиво с рядом, может можно как-нибудь ещё?
Здравствуйте, Константин, Вы писали:
К>Здравствуйте, Cruelty, Вы писали:
C>>Я сам до сих пор не знаю как получить ответ 6 без программки, а именно ето и требовалось сказать по телефону
К>Похоже задачу свели к сумме ряда Sum(n>=2, n*F(n-2)/2^n)
К>Вот как считается сумма похожего ряда (только попроще). К>S=Sum(n>=0,F(n)/2^n) К>S=1+1/2+Sum(n>=2,(F(n-1)+F(n-2))/2^n)=3/2+1/2*Sum(n>=1,F(n)/2^n)+1/4*Sum(n>=0,F(n)/2^n)=3/2+1/2*(S-1)+1/4*S К>1/4*S=1 К>S=4
К>Здесь можно сделать тоже самое, только будет это раза в 3 подлинее
К>P.S. а всё таки как-то некрасиво с рядом, может можно как-нибудь ещё?
Sum(n>=0,F(n)/2^n)=4
Посчитал аналогично
S=Sum(n>=0,n*F(n)/2^n)=16
S=1/2+1/4*Sum(n>=0,F(n)*(n+2)/2^n)+1/2*Sum(n>=0,F(n)*(n+1)/2^n)=1/2+1/4*(8+S)+1/2*(4-1+S)=4+3/4*S
S=16
Тогда
Sum(n>=2, n*F(n-2)/2^n)=1/2*Sum(n>=0,F(n)/2^n)+1/4*Sum(n>=0,n*F(n)/2^n)=1/2*4+1/4*16=6, что и требовалось
Здравствуйте, Cruelty, Вы писали:
C>Такая задачка: C>Подбрасывается правильная монетка, пока 2 раза подряд не выпадет орел. Какое математическое ожидание числа необходимых подбрасываний?
Матожидание двух подряд выпавших орлов(00) равно матожиданию двух решек(11), а также равно матожиданию орел-решка(01) и матожиданию решка-орел(10).
Совершив N+1 подбасывание мы получим N пар: пусть результатом подбрасываний является последовательность abcdef парами будут — ab,bc,cd,de,ef. Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11. То есть N=4, отсюда следует, что матожидание числа подбрасываний равно 5.
Здравствуйте, Slime, Вы писали:
S>Каждая из этих пар с равной вероятностью принимает значение и множества {00,01,10,11}. Это значит, что в среднем, из четырех подряд идущих пар, одна будет равна 11.
Так, идём и читаем про цепи Маркова, потом возвращаемся и сами себе ставим минус
