В одной из вершин равностороннего треугольника сидит черепаха. Черепаха может попасть в одну из соседних вершин с вероятностью 1/2. Черепаха ходит по вершинам треугольника пока не оказывается в начальной вершине. Посчитать матожидание данной случайной величины.

GD Star Rating
loading...

18 Responses to Посчитать матожидание случайной величины

  1. Peels:

    Тьфу.
    Речь о длине пути? 3?

  2. NoBig:

    длина пути, да. какой у вас ряд получился?

  3. Peels:

    Рядами не считал. Просто знаю, чему равно среднее геометрического распределения. 🙂
    Если бы рядами, то был бы конечно ряд \sum k/2^k, суммирование которого обычно делается через интегрирование. Однако чем рядами считать проще решить элементарное рекуррентное соотношение.

  4. NoBig:

    Хорошо, а теперь решите ту же задачу для произвольного графа на n вершинах, где для каждого ребра известна его переходная вероятность. Вероятности прохождения в обе стороны одного ребра одинаковы. Сумма вероятностей рёбер прилегающих к одной вершине равна единице.

  5. Mvxr:

    Это же элементарно: дважды количество ребер в графе, деленная на степень вершины, где сидит черепаха.

  6. Peels:

    Я щас мозг сломаю, ничего элементарнее, чем (не очень помогающее) суммирование матричного ряда интегрированием не рождается.
    Подскажи, с какого угла элементарно.

  7. BoBotanik:

    1) нумеруй вершины
    2) пиши матрицу вероятностей переходов с i–той на j–тую вершину — P
    3) используй марковость процесса (M_возвращения = \sum {nP^n})
    4) реши проблему того, что интересует только первичное возвращение черепахи в исходное состояние (как понимаю, тут нужна формула включения исключения).
    5) profit.

  8. Peels:

    Пункты 1–4 это именно то, что привело меня к суммированию матричных рядов и сломанному мозгу, профита не наблюдал.
    Пункт 4 кстати решается не формулой включения исключения, а чуть покорявив матрицу Р.

  9. BoBotanik:

    честно, не углублялся в пункт 4. просто прикинул, как избежать учета повторных возвращений.

    Матричные ряды там не особо нужны. мат ожидание возвращения в первую вершину равно \sum {np_11(n)} (учитывая повторные возвращения). Ответ вполне красивый, потому что другое решение этой задачи, что я знаю существует заключается в лобовом подходе и честном рекурсивном расписывании, и получаются ряды не лучше.

  10. Peels:

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

  11. BoBotanik:

    ну нужно суммировать такую штуку, чтобы исключить повторные возвращения:

    \sum_{n=1}^{n=\inf}
    {
    n*p_11(n)*\mul_{k=1}^{k=n–1}
    {
    (1–p_11(k))
    }
    }

    кол–во шагов*вероятность возвращения ровно за n шагов*вероятность, что не вернемся за предыдущие шаги.

  12. BoBotanik:

    я криво отвечаю._.

  13. Peels:

    p_11(n) — это вероятность, что ты будешь находиться в первой точке после n шагов.
    (1–p_11(k)) — это вероятность, что ты будешь находиться в первой точке после k шагов.

    p_11(n)*(1–p_11(k)) — это вероятность что при двух независимых прогулках длинами n и k каждая ты закончишь первую в точке 1, а вторую — не в ней. Это НЕ вероятность, что за одну прогулку длиной n ты окажешься в конце в точке 1 а на шаге k не в точке 1.

    Это первый глюк. Второй глюк в том, что p_11(n) — это не просто число, а вообще–то P^n_11, т.е. от матричного ряда ты тут не избавляешься.

  14. BoBotanik:

    не совсем.
    p_11(n) это вероятность возвращения в первую точку за n шагов.
    (1–p_11(k)) — вероятность невозвращения в первую точку за k шагов.
    (подразумевается то, что, изначально находясь в первой точке, через n (во втором случае — k) шагов ты окажешься в первой точке)
    p_11(n)*(1–p_11(k)) — вероятность того, что на k–том шаге ты не возвратился в первую точку, а на n–том шаге — возвратился.

    p_11(n) это, конечно же, P^n_11, и матрицы возводить в степень все же, действительно, придется.

  15. Peels:

    p_11(n) — это, для одного *случайно взятого прохода*, вероятность вернуться за n шагов в точку 1.
    p_11(n)p_11(k) — это вероятность, для *двух независимо случайно взятых проходов*, вернуться в первом проходе в точку 1 за н шагов, а во втором проходе — в точку 1 за к шагов.

    Аналогично с p_11(n)*(1–p_11(k)) — это вероятность для *двух независимо случайно взятых проходов*. На свойства одного и того же прохода это не транслируется.

  16. BoBotanik:

    не забывай марковость цепи.

  17. Peels:

    Не забываю.

    Ну смотри, p_11(n) по сути считает среди всех проходов длиной n, пропорцию тех, которые заканчиваются в вершине 1. Теперь положим из этих проходов мне нужно выделить отдельно часть таких, которые на пятом шаге не были в вершине 1. Я знаю что из всех проходов пропорция тех, кто на пятом шаге не были в вершине 1 равна (1–p_11(5)). Я бы мог теперь получить интересующее меня число перемножением вероятностей если бы события «проход не был на пятом шаге в вершине 1» и «проход был на n шаге в вершине 1» были бы независимыми, но они таковыми очевидно не являются, и марковость цепи тут никак не помогает.

Добавить комментарий