Foster's theorem

<h2 id="theorem">Theorem</h2>
<p>Consider an irreducible discrete-time Markov chain on a countable state space 
  
    
      
        S
      
    
    {\displaystyle S}
  
 having a <a href="/facts/Stochastic_matrix/2cRWAqC3">transition probability matrix</a> 
  
    
      
        P
      
    
    {\displaystyle P}
  
 with elements 
  
    
      
        
          p
          
            i
            j
          
        
      
    
    {\displaystyle p_{ij}}
  
 for pairs 
  
    
      
        i
      
    
    {\displaystyle i}
  
, 
  
    
      
        j
      
    
    {\displaystyle j}
  
 in 
  
    
      
        S
      
    
    {\displaystyle S}
  
. Foster's theorem states that the Markov chain is positive recurrent if and only if there exists a <a href="/facts/Lyapunov_function/RB590Utb">Lyapunov function</a> 
  
    
      
        V
        :
        S
        →
        
          R
        
      
    
    {\displaystyle V:S\to \mathbb {R} }
  
, such that 
  
    
      
        V
        (
        i
        )
        ≥
        0
        
           
        
        ∀
        
           
        
        i
        ∈
        S
      
    
    {\displaystyle V(i)\geq 0{\text{ }}\forall {\text{ }}i\in S}
  
 and
</p>
<ol><li>
  
    
      
        
          ∑
          
            j
            ∈
            S
          
        
        
          p
          
            i
            j
          
        
        V
        (
        j
        )
        <
        
          ∞
        
      
    
    {\displaystyle \sum _{j\in S}p_{ij}V(j)<{\infty }}
  
 for 
  
    
      
        i
        ∈
        F
      
    
    {\displaystyle i\in F}
  
</li>
<li>
  
    
      
        
          ∑
          
            j
            ∈
            S
          
        
        
          p
          
            i
            j
          
        
        V
        (
        j
        )
        ≤
        V
        (
        i
        )
        −
        ε
      
    
    {\displaystyle \sum _{j\in S}p_{ij}V(j)\leq V(i)-\varepsilon }
  
 for all 
  
    
      
        i
        ∉
        F
      
    
    {\displaystyle i\notin F}
  
</li></ol>
<p>for some finite set 
  
    
      
        F
      
    
    {\displaystyle F}
  
 and strictly positive 
  
    
      
        ε
      
    
    {\displaystyle \varepsilon }
  
.<a class="footnote-ref" id="fnref:2" href="#fn:2"><sup>2</sup></a>
</p>
<h2 id="related-links">Related links</h2>
<ul><li><a href="/facts/Lyapunov_optimization/zAXmbrsI">Lyapunov optimization</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Foster, F. G. (1953). "On the Stochastic Matrices Associated with Certain Queuing Processes". The Annals of Mathematical Statistics. 24 (3): 355–360. doi:10.1214/aoms/1177728976. JSTOR 2236286. <a href="https://doi.org/10.1214%2Faoms%2F1177728976" target="_blank">https://doi.org/10.1214%2Faoms%2F1177728976</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>Brémaud, P. (1999). "Lyapunov Functions and Martingales". Markov Chains. pp. 167. doi:10.1007/978-1-4757-3124-8_5. ISBN 978-1-4419-3131-3. <a href="978-1-4419-3131-3" target="_blank">978-1-4419-3131-3</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
</ol>

Foster's theorem open-in-new

Foster's theorem