Attempt on getting a closed-form formula of state probabilities from the Markov Chain model

[MichalisPanayides]

• Initial Approach
  • write πQ
  • recursion that moves from (0,0) to bottom-right
  • P_n = P_0
  • Use sympy to get π and P_i's
  • If nothing else works: Guess a general form of the formula and fit model

[MichalisPanayides]

UPDATE:

• Got symbolic formulas for small models
  • rate of a state: all possible paths to it such that every state has exactly 1 out-arrow
  • EVERY path's power = (#states - 1)

Markov Chain Tree Theorem: π_i = sum of the weight of all directed spanning trees rooted at that state

[MichalisPanayides]

UPDATE of Everything:

1. Initial Approach:

   • Used sympy to get symbolic formulas and solved using sympy.solve_linear_system_LU
   • Used sympy.simplify() to simpify expressions
   • Examples calculated:
     • Markov 1321
     • Markov 1431
     • Markov 1121
     • Markov 1321
     • Markov 2121
     • Markov 1222
   • Markov Chain Tree Theorem: UNNORMALIZED π_i = sum of the weight of all directed spanning trees rooted at state i
     • Verified examples: Markov 1341, MARKOV 1122
   • Examined recursive ratio between adjacent states i and j: π_i/ π_j
   • Recursive ratio example:

2. Attempt of getting π_0,0 formula by completing the power:

   • Created modularised functions that return symbolic rate at state (0,0) and recursive ratios (nbs/other/closed_form_formula_of_pi/state_probabilities_example)

   • Adding rows: when having k rows at the model, the rate is equivalent to (one-row model)^k:

   • Adding columns: more complicated - after some point terms get harder to predict

3. Attempt of getting π_0,0 formula using combinatorics

   • Tried looking at the spanning trees problem from a combinatorics point of view

   • Turned Markov chain model into a graph theoretic model

   • Possible (λ^A) (λ^o) μ terms:

     • p₁ + p₂ + p₃ = C
     • If p₁ = 0, then p₂ = 0 and p₃ = C

   • Managed to get coefficient for terms (λ^A)^p₁ (λ^o)^p₂ μ^p₃ where one of p₁, p₂ or p₃ was raised to a power of 1 or 0.

   • i.e. coefficients of the form [(λ ^A)²] [(λ ^o)³] [μ²] (where p₁, p₂,p₃ > 1) could not be calculated

   • As problem gets bigger more cases of spanning trees appear and such cases were not found

   • Matrix-tree theorem: Laplacian of graph can be used to get the number of spanning trees at state i

4. Successful attempt of getting π_0,0 formula using permutation algorithm

   • Translating the problem into a permutation problem:

     • The problem of finding all spanning trees becomes a problem of finding all possible permutations of an array with elements the characters "D", "R" and "L".

     • Arrays that represent valid spanning trees are the ones that don't end in "R" and don't have an "R" followed by an "L"

     • Note that such algorithm works for cases of parking_capacity = 1 (i.e. one additional row in the Markov chain model)

     • For parking_capacity > 1, apply (one-row model)^{parking_capacity} described earlier

     • Based on that notion closed-form formula is calculate as:

Pull requests:

• 29 Investigate close form of pi

  • 30 Graph Theoretic approach to get pi

• 31 Get python code to generate tikz figure

• 34 Spanning trees tikz code for python

• 35 Write up everything on close form formula

  • 36 Update on close form formula

Files:

• (nbs/other/closed_form_formula_of_pi/investigate-close-form-of-pi.ipynb)
  • Contains initial attempt of symbolic procedure to get symbolic rate
• (nbs/other/closed_form_formula_of_pi/investigate_P00.ipynb)
  • Closer look at different examples
• (nbs/other/closed_form_formula_of_pi/graph-theoretic-approach-to-calculate-pi.ipynb)
  • Looking at the problem from a more graph theoretic perspective
• (nbs/other/closed_form_formula_of_pi/Permutations_algorithm.ipynb)
  • Building the actual closed-form formula using the permutations algorithm

To be done:

• Further investigate integer division in permutations formula ( // )

  • Investigate the difference between integer division, floor division and normal division

• Generalise formula for general threshold T

• Generalise formula for general number of servers C

• Find recursive formula for π_i based on π_0,0 OR find formula for π_i using spanning trees

[drvinceknight]

This is exactly what I was hoping you'd write up @11michalis11. :+1: