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

Probabilities, Gaussian Elimination and Markov Sequence problem (Help)
Автор Hailo, история, 8 лет назад, По-английски

Hi, I'm having trouble solving this problem. I was thinking of applying a Markov sequence property ( The average length of the cycle path of a node is the inverse of the probability of being in this node ), so the problem is reduced to an equation system. However, it's a 105 x 105 sparse matrix (at most 105 non-zero elements). I don't know if there is a gaussian elimination method for this kind of matrix or if the approach is incorrect. Thanks.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Omg, I just got accepted and I proved my solution, but I still don't believe it can be that simple. Code is like extremely short, that may be a hint.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Still, why does that work? What are your starting ideas on proving the correctness of the solution?

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      Spoilers. Revert to see them.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится
        1. Nice spoiler trick ;)
        2. This was basically the same path I went through solving the problem, which is rather funny
        3. The statement I was actually interested in was the first step. Is that like a well known fact? I have never seen it before (well, I don't have much experience in Markov networks either, that might explain it). Did you come up with a proof? If so, I'd like to know some insights or starting points. I'll think about it more thoroughly, nonetheless.
        → Ответить
        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится +10 Проголосовать: не нравится

          Yes, it is rather a well-known fact (I remember it being mentioned on my university probability course, but probably I have seen also somewhere else) and OP also mentioned it. Imagine an infinite random walk. What can you say about occurrences of v in that walk? How does it relate to average time of coming back from v to v?

          → Ответить
          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
            ← Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

            can you please tell why the answer is not for any vertex i 1/(wi) where w is a vector such that w=wp where p=transition matrix . Swistakk update- problem done.

            → Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

It's a classic property of random walks on graphs. A more strong fact for any irreducible markov chain it's explained here http://research.microsoft.com/en-us/um/people/peres/markovmixing.pdf , sections 1.4 and 1.5

→ Ответить