Balance equation

<h2 id="global-balance">Global balance</h2>
The global balance equations (also known as full balance equations<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>) are a set of equations that characterize the <a href="/facts/Equilibrium_distribution/5oP5hntk">equilibrium distribution</a> (or any stationary distribution) of a Markov chain, when such a distribution exists. 
For a <a href="/facts/Continuous_time_Markov_chain/h7ytJ6p3">continuous time Markov chain</a> with state space 
 
 
 
 
 
 S
 
 
 
 
 {\displaystyle {\mathcal {S}}}
 
, transition rate from state 
 
 
 
 i
 
 
 {\displaystyle i}
 
 to 
 
 
 
 j
 
 
 {\displaystyle j}
 
 given by 
 
 
 
 
 q
 
 i
 j
 
 
 
 
 {\displaystyle q_{ij}}
 
 and equilibrium distribution given by 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
, the global balance equations are given by<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a>

π
          
            i
          
        
        =
        
          ∑
          
            j
            ∈
            S
          
        
        
          π
          
            j
          
        
        
          q
          
            j
            i
          
        
        ,
      
    
    {\displaystyle \pi _{i}=\sum _{j\in S}\pi _{j}q_{ji},}

or equivalently

π
          
            i
          
        
        
          ∑
          
            j
            ∈
            S
            ∖
            {
            i
            }
          
        
        
          q
          
            i
            j
          
        
        =
        
          ∑
          
            j
            ∈
            S
            ∖
            {
            i
            }
          
        
        
          π
          
            j
          
        
        
          q
          
            j
            i
          
        
        .
      
    
    {\displaystyle \pi _{i}\sum _{j\in S\setminus \{i\}}q_{ij}=\sum _{j\in S\setminus \{i\}}\pi _{j}q_{ji}.}

for all 
 
 
 
 i
 ∈
 S
 
 
 {\displaystyle i\in S}
 
. Here 
 
 
 
 
 π
 
 i
 
 
 
 q
 
 i
 j
 
 
 
 
 {\displaystyle \pi _{i}q_{ij}}
 
 represents the probability flux from state 
 
 
 
 i
 
 
 {\displaystyle i}
 
 to state 
 
 
 
 j
 
 
 {\displaystyle j}
 
. So the left-hand side represents the total flow from out of state i into states other than i, while the right-hand side represents the total flow out of all states 
 
 
 
 j
 ≠
 i
 
 
 {\displaystyle j\neq i}
 
 into state 
 
 
 
 i
 
 
 {\displaystyle i}
 
. In general it is computationally intractable to solve this system of equations for most queueing models.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>

<h2 id="detailed-balance">Detailed balance</h2>
See also: <a href="/facts/Detailed_balance/qVpGh7HW">Detailed balance</a>
For a <a href="/facts/Continuous_time_Markov_chain/h7ytJ6p3">continuous time Markov chain</a> (CTMC) with <a href="/facts/Transition_rate_matrix/6m9Tjrby">transition rate matrix</a> 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
, if 
 
 
 
 
 π
 
 i
 
 
 
 
 {\displaystyle \pi _{i}}
 
 can be found such that for every pair of states 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}

π
          
            i
          
        
        
          q
          
            i
            j
          
        
        =
        
          π
          
            j
          
        
        
          q
          
            j
            i
          
        
      
    
    {\displaystyle \pi _{i}q_{ij}=\pi _{j}q_{ji}}

holds, then by summing over 
 
 
 
 j
 
 
 {\displaystyle j}
 
, the global balance equations are satisfied and 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 is the stationary distribution of the process.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> If such a solution can be found the resulting equations are usually much easier than directly solving the global balance equations.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
A CTMC is reversible if and only if the detailed balance conditions are satisfied for every pair of states 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}
 
.
A <a href="/facts/Discrete_time_Markov_chain/u4qADb4z">discrete time Markov chain</a> (DTMC) with transition matrix 
 
 
 
 P
 
 
 {\displaystyle P}
 
 and equilibrium distribution 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 is said to be in detailed balance if for all pairs 
 
 
 
 i
 
 
 {\displaystyle i}
 
 and 
 
 
 
 j
 
 
 {\displaystyle j}
 
,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

π
          
            i
          
        
        
          p
          
            i
            j
          
        
        =
        
          π
          
            j
          
        
        
          p
          
            j
            i
          
        
        .
      
    
    {\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}.}

When a solution can be found, as in the case of a CTMC, the computation is usually much quicker than directly solving the global balance equations.

<h2 id="local-balance">Local balance</h2>
In some situations, terms on either side of the global balance equations cancel. The global balance equations can then be partitioned to give a set of local balance equations (also known as partial balance equations,<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> independent balance equations<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> or individual balance equations<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>).<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> These balance equations were first considered by <a href="/facts/Peter_Whittle_(mathematician)/eGoN2BdP">Peter Whittle</a>.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a><a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> The resulting equations are somewhere between detailed balance and global balance equations. Any solution 
 
 
 
 π
 
 
 {\displaystyle \pi }
 
 to the local balance equations is always a solution to the global balance equations (we can recover the global balance equations by summing the relevant local balance equations), but the converse is not always true.<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> Often, constructing local balance equations is equivalent to removing the outer summations in the global balance equations for certain terms.<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a>
During the 1980s it was thought local balance was a requirement for a <a href="/facts/Product-form_solution/NC3xSFck">product-form equilibrium distribution</a>,<a class="footnote-ref" id="fnref:16" href="#fn:16">16</a><a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> but <a href="/facts/Erol_Gelenbe/9w6XrywD">Gelenbe</a>'s <a href="/facts/G-network/pXGuAIBK">G-network</a> model showed this not to be the case.<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a>

<h2 id="notes">Notes</h2>

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

<ol>
<li id="fn:1">Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. ISBN 0-201-54419-9. <a href="0-201-54419-9" target="_blank">0-201-54419-9</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Kelly, F. P. (1979). Reversibility and stochastic networks. J. Wiley. ISBN 0-471-27601-4. <a href="0-471-27601-4" target="_blank">0-471-27601-4</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Chandy, K.M. (March 1972). "The analysis and solutions for general queueing networks". Proc. Sixth Annual Princeton Conference on Information Sciences and Systems, Princeton U. Princeton, N.J. pp. 224–228. <a href="/wiki/K._Mani_Chandy" target="_blank">/wiki/K._Mani_Chandy</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Grassman, Winfried K. (2000). Computational probability. Springer. ISBN 0-7923-8617-5. <a href="0-7923-8617-5" target="_blank">0-7923-8617-5</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Bocharov, Pavel Petrovich; D'Apice, C.; Pechinkin, A.V.; Salerno, S. (2004). Queueing theory. Walter de Gruyter. p. 37. ISBN 90-6764-398-X. <a href="90-6764-398-X" target="_blank">90-6764-398-X</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Grassman, Winfried K. (2000). Computational probability. Springer. ISBN 0-7923-8617-5. <a href="0-7923-8617-5" target="_blank">0-7923-8617-5</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Norris, James R. (1998). Markov Chains. Cambridge University Press. ISBN 0-521-63396-6. Retrieved 2010-09-11. <a href="0-521-63396-6" target="_blank">0-521-63396-6</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Kelly, F. P. (1979). Reversibility and stochastic networks. J. Wiley. ISBN 0-471-27601-4. <a href="0-471-27601-4" target="_blank">0-471-27601-4</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Baskett, F.; Chandy, K. Mani; Muntz, R.R.; Palacios, F.G. (1975). "Open, closed and mixed networks of queues with different classes of customers". Journal of the ACM. 22 (2): 248–260. doi:10.1145/321879.321887. <a href="/wiki/K._Mani_Chandy" target="_blank">/wiki/K._Mani_Chandy</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Whittle, P. (1968). "Equilibrium Distributions for an Open Migration Process". Journal of Applied Probability. 5 (3): 567–571. doi:10.2307/3211921. JSTOR 3211921. <a href="/wiki/Peter_Whittle_(mathematician)" target="_blank">/wiki/Peter_Whittle_(mathematician)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. ISBN 0-201-54419-9. <a href="0-201-54419-9" target="_blank">0-201-54419-9</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">Whittle, P. (1968). "Equilibrium Distributions for an Open Migration Process". Journal of Applied Probability. 5 (3): 567–571. doi:10.2307/3211921. JSTOR 3211921. <a href="/wiki/Peter_Whittle_(mathematician)" target="_blank">/wiki/Peter_Whittle_(mathematician)</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">Chao, X.; Miyazawa, M. (1998). "On Quasi-Reversibility and Local Balance: An Alternative Derivation of the Product-Form Results". Operations Research. 46 (6): 927–933. doi:10.1287/opre.46.6.927. JSTOR 222945. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">Kelly, F. P. (1979). Reversibility and stochastic networks. J. Wiley. ISBN 0-471-27601-4. <a href="0-471-27601-4" target="_blank">0-471-27601-4</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. ISBN 0-201-54419-9. <a href="0-201-54419-9" target="_blank">0-201-54419-9</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">Boucherie, Richard J.; van Dijk, N.M. (1994). "Local balance in queueing networks with positive & negative customers". Annals of Operations Research. 48 (5): 463–492. doi:10.1007/bf02033315. hdl:1871/12327. <a href="https://www.researchgate.net/publication/225825899" target="_blank">https://www.researchgate.net/publication/225825899</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">Chandy, K. Mani; Howard, J.H. Jr; Towsley, D.F. (1977). "Product form and local balance in queueing networks". Journal of the ACM. 24 (2): 250–263. doi:10.1145/322003.322009. <a href="/wiki/K._Mani_Chandy" target="_blank">/wiki/K._Mani_Chandy</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">Gelenbe, Erol (Sep 1993). "G-Networks with Triggered Customer Movement". Journal of Applied Probability. 30 (3): 742–748. doi:10.2307/3214781. JSTOR 3214781. <a href="/wiki/Erol_Gelenbe" target="_blank">/wiki/Erol_Gelenbe</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
</ol>

Balance equation open-in-new

Balance equation