Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×

Блог пользователя maslowmw

Автор maslowmw, 16 лет назад, По-русски
Всем, привет.
Есть такая задачка:
Есть какое-то событие, которое заканчивается удачно с вероятностью 0.9
Сколько раз надо выполнить это событие, чтобы оно 121 раз подряд закончилось удачно.
Всем заранее спасибо.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

16 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится
Задача поставлена некорректно. Можно выполнить событие миллион раз, и оно каждый раз закончится неудачно. Даже если у него единичная вероятность.
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Если вероятность успеха равна 1.0, то как, простите, все миллион испытаний могут закончиться неудачей?
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +3 Проголосовать: не нравится
      Очень просто. Например, вероятность того, что две прямые, брошенные на плоскость наугад, пересекутся, равна 1. Тем не менее, я могу привести континуум примеров, когда они параллельны.
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится -15 Проголосовать: не нравится
        если у вас существует какая-то вероятность P > 0 бросить две прямые так, что они будут параллельны (видимо, существует, иначе не было бы третьего предложения), то вероятность того, что две брошенные прямые пересекутся, равна 1 - P и, следовательно, не равна единице
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +6 Проголосовать: не нравится
          Вы не правы. Событие - это элемент некоторой сигма-алгебры. Всякое такое событие, говоря неформально, "может произойти". Вероятность - это мера на этой сигма-алгебре. Она может запросто обращаться в ноль на некоторых непустых подмножествах. 

          Таким образом, "событие A не может произойти" и "вероятность события A равна нулю" - это совершенно разные вещи.
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +3 Проголосовать: не нравится
          Конечно нет. Возьмем пример попроще - пусть у нас равномерное распределение на отрезке [-1, 1]. Тогда вероятность того, что значение этой случайной величины будет каким-то конкретным числом - 0. Тем не менее каким-то числом оно окажется
  • 16 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    а по поводу этой задачи ответ может быть такой: некая функция f(n) - вероятность того, что будет серия из 121 удачного опыта при проведении n опытов
    • 16 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Я думаю, требуется найти матожидание числа проведенных экспериментов при условии, что последние 121 из них удачные и нет 121 удачного эксперимента подряд, которые не включают поледний
      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Unable to parse markup [type=CF_HTML]

      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        Unable to parse markup [type=CF_HTML]

      • 16 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится
        Если это так, то ответ - 
        Пусть mi - мат ожидание числа экспериментов описанного выше при условии, что до этого провели 1 неудачный эксперимент и i удачных. Тогда mi = 0, 9mi + 1 + 0, 1 * m0 для 0 ≤ i < 121, m121 = 0. Докажем по индукции, что m_i = m_0 - \frac18 (1 - \frac1{9^i}). База для i = 0 очевидна, переход i -> i + 1 проверяется подстановкой в уравнение для mi. Взяв этот факт для i = 121 получим требуемое так как m121 = 0
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится +6 Проголосовать: не нравится
          To Admins: удалите плиз результаты неудачных компиляций сверху, пофиксите тех компилятор и добавьте предпросмотр. Спасибо
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Спасибо огромное
        • 16 лет назад, скрыть # ^ |
           
          Проголосовать: нравится 0 Проголосовать: не нравится
          Не правильно. Во-первых тебя никак не смутило то что мат ожидание получилось меньше 1, во-вторых в твоей формуле со связью мат ожиданий надо единичку прибавить так как ты делаешь ход.
          • 16 лет назад, скрыть # ^ |
             
            Проголосовать: нравится +1 Проголосовать: не нравится
            m_i - мат ожидания количества ходов при условии что i раз событие выполнилось. Распишем:
            m_i = 1 + 0.9 * m_(i + 1) + 0.1 * m_0 для i от 0 до 120
            При этом m_121 = 0.
            Начнем расписывать это равенство с конца, выражая все m_i через m_0. Так, m_120 = 1 + 0.1 * m_0,
            m_119 = 1 + 0.9 + (1 + 0.9) * m_0 / 10.
            По индукции можно показать что m_i = (1 + m_0 / 10) * k_i, где k_120 = 1, k_i = 1 + 0.9 + ... + 0.9^(120 - i).
            Когда будем расписывать исходное равенство для i = 0, получим соотношение для m0, откуда его и найдем:
            m_0 = (1 + m_0 / 10) * k_0, где k_0 = (1 - 0.9^121) / (1 - 0.9).
            Откуда получаем m_0 = 10 * (1  - 0.9^121) / 0.9^121. Это и есть ответ.