5162:
5246:
5325:
27:
1532:
6376:
is an equilibrium distribution of the Markov chain. Such can occur in Markov chain Monte Carlo (MCMC) methods in situations where a number of different transition matrices are used, because each is efficient for a particular kind of mixing, but each matrix respects a shared equilibrium distribution.
267:
steps in the future can be calculated. A Markov chain's state space can be partitioned into communicating classes that describe which states are reachable from each other (in one transition or in many). Each state can be described as transient or recurrent, depending on the probability of the chain
1190:
6595:
6391:
The hitting time is the time, starting in a given set of states until the chain arrives in a given state or set of states. The distribution of such a time period has a phase type distribution. The simplest such distribution is that of a single exponentially distributed transition.
272:
is like a discrete-time Markov chain, but it moves states continuously through time rather than as discrete time steps. Other stochastic processes can satisfy the Markov property, the property that past behavior does not affect the process, only the present state.
4842:
gives a necessary and sufficient condition for a Markov chain to be reversible directly from the transition matrix probabilities. The criterion requires that the products of probabilities around every closed loop are the same in both directions around the loop.
549:
2470:
4486:
6064:
5494:
3605:
5950:
4111:
1527:{\displaystyle {\begin{aligned}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})\\={}&\Pr(X_{n}=x_{n}\mid X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{n-m}=x_{n-m}){\text{ for }}n>m\end{aligned}}}
5842:. Extending these distributions to the overall chain, setting all values to zero outside the communication class, yields that the set of invariant measures of the original chain is the set of all convex combinations of the
5319:
5240:
6341:
6462:
6197:
3947:
2649:
2249:
1153:
6131:
1716:
3833:
4823:
2970:
6682:
3701:
640:
4495:
receives (including from himself) during the time-step equals the amount of money he pays others, which equals all the money he initially had because it was assumed that all money is spent (that is,
2017:
3472:
1831:
4858:
is a steady-state distribution. Even with time-inhomogeneous Markov chains, where multiple transition matrices are used, if each such transition matrix exhibits detailed balance with the desired
4227:
6467:
1195:
2109:
3614:
is recurrent (or persistent) if it is not transient. Recurrence and transience are class properties, that is, they either hold or do not hold equally for all members of a communicating class.
4303:
1917:
755:
3378:
4917:
894:
5725:
5776:
5581:
4992:
3096:
4676:
4621:
359:
347:
153:
6708:
6374:
6231:
5675:
822:
4346:
each person has remains the same after the time-step, since every dollar spent is balanced by a corresponding dollar received. This can be shown more formally by the equality
5534:
2299:
58:, in which the value of the next variable depends only on the value of the current variable, and not any variables in the past. For instance, a machine may have two states,
988:
5126:
5647:
5614:
5403:
4957:
4352:
6442:
5867:
5840:
5680:
If a Markov chain is irreducible then it has a stationary distribution if and only if it is positive recurrent, in which case the unique such distribution is given by
1608:
1575:
3211:
207:
5813:
5153:
5043:
4340:
of it. The detailed balance condition states that upon each payment, the other person pays exactly the same amount of money back. Clearly the total amount of money
2993:
921:
180:
5974:
5354:
5063:
5016:
2763:
A Markov chain is said to be irreducible if its state space is a single communicating class; in other words, if it is possible to get to any state from any state.
765: + 1. However, Markov chains are frequently assumed to be time-homogeneous (see variations below), in which case the graph and matrix are independent of
3185:
7051:
A. A. Markov (1971). "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in
Appendix B of: R. Howard.
5411:
5374:
5083:
4696:
3271:
3251:
3231:
3156:
3136:
3116:
3037:
3017:
2873:
2849:
2829:
2809:
2789:
3495:
1014:
5876:
3976:
5255:
5176:
263:, which lists the probabilities of moving to each state from any individual state. From this matrix, the probability of being in a particular state
4846:
Reversible Markov chains are common in Markov chain Monte Carlo (MCMC) approaches because the detailed balance equation for a desired distribution
6590:{\displaystyle {\begin{aligned}k_{i}^{A}=0&{\text{ for }}i\in A\\-\sum _{j\in S}q_{ij}k_{j}^{A}=1&{\text{ for }}i\notin A.\end{aligned}}}
6239:
6211:
A Markov chain need not necessarily be time-homogeneous to have an equilibrium distribution. If there is a probability distribution over states
2729:
by inheriting the arrows from the original state space. A communicating class is closed if and only if it has no outgoing arrows in this graph.
7092:
7197:. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973)
6136:
3875:
2540:
2140:
1038:
7059:
Markov, A. A. (2006). "An
Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains".
6997:
6939:
6079:
1621:
3732:
4704:
7136:
2881:
6623:
6851:
3635:
558:
7202:
6983:
6933:
6906:
6866:
6802:
1928:
353:, namely that the probability of moving to the next state depends only on the present state and not on the previous states:
3389:
1748:
4145:
268:
ever returning to that state. Markov chains can have properties including periodicity, reversibility and stationarity. A
2028:
5785:
If a chain has more than one closed communicating class, its stationary distributions will not be unique (consider any
4506:). The assumption is a technical one, because the money not really used is simply thought of as being paid from person
4238:
1842:
19:
This article is about the mathematical properties of discrete-time Markov chains. For the general field of study, see
7186:
7181:
E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge
University Press, 1984, 2004.
7176:
7132:
7117:
7099:
7031:
6830:
2999:) provided that this set is not empty. Otherwise the period is not defined. Note that even though a state has period
683:
3313:
6952:
A. Nielsen, M. Weber. Online publication in
Numerical Linear Algebra with Applications, DOI:10.1002/nla.1967, 2015.
4881:
831:
5683:
2119:
6788:
6771:
5730:
5539:
772:
These descriptions highlight the structure of the Markov chain that is independent of the initial distribution
5161:
4962:
4828:
The left- and right-hand sides of this last equation are identical except for a reversing of the time indices
544:{\displaystyle \Pr(X_{n+1}=x\mid X_{1}=x_{1},X_{2}=x_{2},\ldots ,X_{n}=x_{n})=\Pr(X_{n+1}=x\mid X_{n}=x_{n}),}
3042:
7151:(1st ed.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841.
4626:
4571:
287:
269:
93:
6687:
6357:
6214:
2760:
is inessential if it is not essential. A state is final if and only if its communicating class is closed.
220:
An example of a stochastic process which is not a Markov chain is the model of a machine which has states
5652:
2465:{\displaystyle \Pr(X_{n}=j)=\sum _{r\in S}p_{rj}\Pr(X_{n-1}=r)=\sum _{r\in S}p_{rj}^{(n)}\Pr(X_{0}=r).}
775:
7218:
5321:, then the closest reversible Markov chain according to the Frobenius norm is approximately given by
4839:
6609:, the ergodic theorem for states that for an irreducible aperiodic Markov chain, for any two states
5503:
6898:
4481:{\displaystyle \sum _{i}\pi _{i}p_{ij}=\sum _{i}\pi _{j}p_{ji}=\pi _{j}\sum _{i}p_{ji}=\pi _{j}\,,}
926:
6794:
896:
of the machine's state can be analyzed as the statistical behavior of the machine with an element
6386:
5088:
2996:
828:
assigning a probability of hopping from each vertex or state to an adjacent one. The probability
552:
244:). This is because the behavior of the machine depends on the whole history—if the machine is in
5619:
5586:
5379:
4922:
6415:
3953:
2726:
5845:
5818:
6963:
6923:
6059:{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ij}^{(n)}=C{\tfrac {f_{ij}}{M_{j}}}.}
3853:
is null recurrent (or null persistent). Positive and null recurrence are classes properties.
2262:
1580:
1547:
923:
of the state space as input, or as the behavior of the machine with the initial distribution
7145:
6890:
3190:
185:
6993:
5791:
5131:
5021:
2978:
2705:
A communicating class is closed if the probability of leaving the class is zero, namely if
2695:
899:
825:
158:
5489:{\displaystyle \forall j\in \mathbb {S} :\sum _{i\in \mathbb {S} }\pi _{i}p_{ij}=\pi _{j}}
5339:
5048:
5001:
8:
6891:
6889:(July 1976) . "Ch. 3: Absorbing Markov Chains". In Gehring, F. W.; Halmos, P. R. (eds.).
4995:
3600:{\displaystyle \Pr(T_{i}<\infty \mid X_{0}=i)=\sum _{n=1}^{\infty }f_{ii}^{(n)}<1.}
3164:
213:
describing its state after 10 transitions. The process continues forever, indexed by the
5170:
7076:
5359:
5068:
4681:
3256:
3236:
3216:
3141:
3121:
3101:
3022:
3002:
2858:
2834:
2814:
2794:
2774:
55:
7142:
5945:{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{jj}^{(n)}={\tfrac {C}{M_{j}}}}
993:
7198:
7182:
7172:
7128:
7113:
7095:
7080:
7027:
6979:
6929:
6902:
6862:
6826:
6798:
6767:
6759:
4106:{\displaystyle \pi _{i}\Pr(X_{n+1}=j\mid X_{n}=i)=\pi _{j}\Pr(X_{n+1}=i\mid X_{n}=j)}
2852:
2699:
260:
90:. The sequence of states of the machine is a Markov chain. If we denote the chain by
7068:
7019:
6971:
4129:
3865:
is called absorbing if it is impossible to leave this state. Therefore, the state
7164:
7023:
7011:
6989:
6886:
6847:
3711:
Even if the hitting time is finite with probability 1, it need not have a finite
3294:
1017:
350:
282:
253:
214:
210:
6206:
1029:
Time-homogeneous Markov chains (or stationary Markov chains) are processes where
7160:
6897:(Second ed.). New York Berlin Heidelberg Tokyo: Springer-Verlag. pp.
6882:
6606:
6445:
3964:
A Markov chain is said to be reversible if there is a probability distribution
3712:
3622:
2480:
1610:
which has the 'classical' Markov property by taking as state space the ordered
665:
7143:
Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959).
7072:
6975:
5314:{\displaystyle \pi =\left({\frac {1}{4}},{\frac {1}{4}},{\frac {1}{2}}\right)}
5235:{\displaystyle \pi =\left({\frac {1}{3}},{\frac {1}{3}},{\frac {1}{3}}\right)}
7212:
7191:
5245:
655:
6336:{\displaystyle \pi _{j}=\sum _{i\in S}\pi _{i}\,\Pr(X_{n+1}=j\mid X_{n}=i)}
20:
6818:
4568:
If the Markov chain begins in the steady-state distribution, that is, if
3952:
If every state can reach an absorbing state, then the Markov chain is an
43:
5815:
in the chain; each one will have its own unique stationary distribution
5356:
is a stationary distribution of the Markov chain with stochastic matrix
7105:
4852:
necessarily implies that the Markov chain has been constructed so that
757:
The same information is represented by the transition matrix from time
2293:). The evolution of the process through one time step is described by
6192:{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(kn+r)}}
3942:{\displaystyle p_{ii}=1{\text{ and }}p_{ij}=0{\text{ for }}i\not =j.}
3039:
steps. For example, suppose it is possible to return to the state in
2644:{\displaystyle \Pr(X_{n_{ij}}=j\mid X_{0}=i)=p_{ij}^{(n_{ij})}>0.}
2244:{\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}}
1148:{\displaystyle \Pr(X_{n+1}=x\mid X_{n}=y)=\Pr(X_{n}=x\mid X_{n-1}=y)}
5324:
5155:
can be computed by solving a quadratic-convex optimization problem.
4878:
For any time-homogeneous Markov chain given by a transition matrix
2484:
6126:{\displaystyle \lim \nolimits _{n\rightarrow \infty }p_{ii}^{(n)}}
1711:{\displaystyle Y_{n}=\left(X_{n},X_{n-1},\ldots ,X_{n-m+1}\right)}
3828:{\displaystyle M_{i}=E=\sum _{n=1}^{\infty }n\cdot f_{ii}^{(n)}.}
3233:. Periodicity is a class property—that is, if a state has period
672:
are labeled by the probabilities of going from one state at time
4818:{\displaystyle \Pr(X_{n}=i,X_{n+1}=j)=\Pr(X_{n+1}=i,X_{n}=j)\,.}
26:
4491:
which essentially states that the total amount of money person
4232:
the detailed balance equation can be written more compactly as
3289:, there is a non-zero probability that we will never return to
2965:{\displaystyle k=\gcd\{n>0:\Pr(X_{n}=i\mid X_{0}=i)>0\}}
240:
before (leaving a 50% or 80% chance that the machine moves to
7139:. Second edition to appear, Cambridge University Press, 2009.
7091:. Original edition published by Addison-Wesley; reprinted by
6207:
Steady-state analysis and the time-inhomogeneous Markov chain
252:, depending on its past values. Hence, it does not have the
6677:{\displaystyle p_{i,j}^{(n)}\rightarrow {\frac {1}{M_{j}}}}
3696:{\displaystyle \sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .}
635:{\displaystyle \Pr(X_{1}=x_{1},\ldots ,X_{n}=x_{n})>0.}
5786:
3285:
is said to be transient if, given that we start in state
824:
When time-homogeneous, the chain can be interpreted as a
232:
from either state with 50% chance if it has ever visited
3253:
then every state in its communicating class has period
2515:
has a non-zero probability of transitioning into state
2490:
2012:{\displaystyle p_{ij}^{(n)}=\Pr(X_{k+n}=j\mid X_{k}=i)}
1172:
A Markov chain with memory (or a Markov chain of order
7053:
6025:
5924:
5169:
This Markov chain is not reversible. According to the
1163:. The probability of the transition is independent of
6928:. Springer Science & Business Media. p. 37.
6690:
6626:
6465:
6418:
6360:
6242:
6217:
6139:
6082:
5977:
5879:
5848:
5821:
5794:
5733:
5686:
5655:
5622:
5589:
5542:
5506:
5414:
5382:
5362:
5342:
5258:
5179:
5134:
5091:
5071:
5051:
5024:
5004:
4965:
4925:
4884:
4707:
4684:
4629:
4574:
4355:
4241:
4148:
3979:
3878:
3735:
3638:
3498:
3467:{\displaystyle f_{ii}^{(n)}=\Pr(T_{i}=n\mid X_{0}=i)}
3392:
3316:
3259:
3239:
3219:
3213:), the state is said to be periodic with period
3193:
3187:, then the state is said to be aperiodic. Otherwise (
3167:
3144:
3124:
3104:
3045:
3025:
3005:
2981:
2884:
2861:
2837:
2817:
2797:
2777:
2543:
2302:
2143:
2031:
1931:
1845:
1826:{\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)}
1751:
1624:
1583:
1550:
1540:
In other words, the future state depends on the past
1193:
1041:
996:
929:
902:
834:
778:
686:
561:
362:
290:
188:
161:
96:
5963:
be the probability that the chain ever visits state
4870:
is a steady-state distribution of the Markov chain.
4698:
and the detailed balance equation can be written as
4222:{\displaystyle p_{ij}=\Pr(X_{n+1}=j\mid X_{n}=i)\,,}
6452:that the chain enters one of the states in the set
2686:. A communicating class is a maximal set of states
664:Markov chains are often described by a sequence of
7144:
6702:
6676:
6589:
6436:
6368:
6335:
6225:
6191:
6125:
6058:
5944:
5861:
5834:
5807:
5770:
5719:
5669:
5641:
5608:
5575:
5528:
5488:
5397:
5368:
5348:
5313:
5234:
5158:For example, consider the following Markov chain:
5147:
5120:
5077:
5057:
5037:
5010:
4986:
4951:
4911:
4873:
4817:
4690:
4670:
4615:
4480:
4297:
4221:
4105:
3941:
3842:is positive recurrent (or non-null persistent) if
3827:
3695:
3599:
3466:
3372:
3265:
3245:
3225:
3205:
3179:
3150:
3130:
3110:
3090:
3031:
3011:
2987:
2964:
2867:
2843:
2823:
2803:
2783:
2694:communicates with each other. Communication is an
2643:
2464:
2243:
2104:{\displaystyle p_{ij}=\Pr(X_{k+1}=j\mid X_{k}=i).}
2103:
2011:
1911:
1825:
1710:
1602:
1569:
1526:
1147:
1008:
982:
915:
888:
816:
749:
634:
543:
341:
201:
174:
147:
6758:
5173:the closest reversible Markov chain according to
7210:
6283:
5252:If we choose the probability vector randomly as
4761:
4708:
4630:
4575:
4316: + 1 can be thought of as each person
4298:{\displaystyle \pi _{i}p_{ij}=\pi _{j}p_{ji}\,.}
4165:
4053:
3990:
3499:
3420:
3330:
2982:
2909:
2891:
2544:
2434:
2360:
2303:
2048:
1959:
1912:{\displaystyle p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).}
1862:
1779:
1354:
1201:
1095:
1042:
930:
835:
779:
687:
562:
481:
363:
54:) is a sequence of random variables, known as a
6921:
3019:, it may not be possible to reach the state in
750:{\displaystyle \Pr(X_{n+1}=x\mid X_{n}=x_{n}).}
248:, it may have a 50% or 20% chance of moving to
236:before, and 20% chance if it has never visited
7093:Society for Industrial and Applied Mathematics
6845:
3373:{\displaystyle T_{i}=\inf\{n\geq 1:X_{n}=i\}.}
281:A discrete-time Markov chain is a sequence of
70:, there is a 40% chance of it moving to state
4912:{\displaystyle P\in \mathbb {R} ^{n\times n}}
4528:, and therefore for reversible Markov chains
182:is the state which the machine starts in and
7014:(1997). "Continuous-time Markov chains II".
6766:(second ed.). Oxford University Press.
5323:
5244:
5160:
4864:distribution, this necessarily implies that
4534:is always a steady-state distribution of Pr(
4524:was arbitrary, this reasoning holds for any
3364:
3333:
3276:
3085:
3046:
2959:
2894:
2736:is said to be essential or final if for all
1544:states. It is possible to construct a chain
889:{\displaystyle \Pr(X_{n}=x\mid X_{1}=x_{1})}
6881:
6786:
5720:{\displaystyle \pi _{i}={\frac {1}{M_{i}}}}
5331:
3477:is the probability that we return to state
2725:. The set of communicating classes forms a
2118:-step transition probabilities satisfy the
6915:
6456:) is the minimal non-negative solution to
5018:, there exists a unique transition matrix
3959:
2278:) is the distribution over states at time
74:and a 60% chance of it remaining in state
7067:(4). Translated by Link, David: 591–600.
6395:
6282:
5771:{\displaystyle M_{i}=\mathbb {E} (T_{i})}
5748:
5663:
5576:{\displaystyle (X_{n},n\in \mathbb {N} )}
5566:
5444:
5425:
4968:
4893:
4811:
4474:
4329:dollars initially and paying each person
4291:
4215:
769:and are thus not presented as sequences.
6964:"Basics of Applied Stochastic Processes"
4987:{\displaystyle \mathbb {R} ^{n\times n}}
2258:is the state space of the Markov chain.
82:, there is a 70% chance of it moving to
25:
7195:Non-negative matrices and Markov chains
6961:
6362:
6219:
4132:condition (or local balance equation).
3091:{\displaystyle \{6,~8,~10,~12,\dots \}}
7211:
7125:Markov Chains and Stochastic Stability
7058:
7010:
7004:
6817:
6754:
6752:
6750:
6748:
6746:
6744:
3706:
2499:is said to be accessible from a state
6942:from the original on 6 February 2017.
6811:
6742:
6740:
6738:
6736:
6734:
6732:
6730:
6728:
6726:
6724:
4671:{\displaystyle \Pr(X_{n}=i)=\pi _{i}}
4616:{\displaystyle \Pr(X_{0}=i)=\pi _{i}}
1922:For a time-homogeneous Markov chain:
1722:
661:called the state space of the chain.
342:{\displaystyle X_{0},X_{1},X_{2},...}
259:A Markov chain can be described by a
148:{\displaystyle X_{0},X_{1},X_{2},...}
7123:S. P. Meyn and R. L. Tweedie (1993)
6823:Introduction to Stochastic Processes
6703:{\displaystyle n\rightarrow \infty }
6369:{\displaystyle {\boldsymbol {\pi }}}
6226:{\displaystyle {\boldsymbol {\pi }}}
3715:. The mean recurrence time at state
2698:, and communicating classes are the
2491:Communicating classes and properties
1730:The probability of going from state
6839:
6133:does not exist, although the limit
4135:Considering a fixed arbitrary time
3856:
1185:is finite, is a process satisfying
13:
6925:Essentials of Stochastic Processes
6875:
6721:
6697:
6600:
6199:does exist for every integer
6151:
6094:
5989:
5891:
5415:
3787:
3687:
3655:
3562:
3518:
3303:be the first return time to state
2690:such that every pair of states in
2658:is said to communicate with state
1836:and the single-step transition is
86:and a 30% chance of it staying in
14:
7230:
6861:. American Mathematical Society.
6076: > 1 then the limit
5670:{\displaystyle n\in \mathbb {N} }
5045:which is reversible according to
4128:. This condition is known as the
3625:the expected number of visits to
2282:. The initial distribution is Pr(
817:{\displaystyle \Pr(X_{1}=x_{1}).}
7112:. New York: John Wiley and Sons
6968:Probability and Its Applications
6764:Probability and Random Processes
6762:; Stirzaker, D. R. (1992). "6".
6412:of hitting times (where element
6380:
30:A Markov chain with two states,
7000:from the original on 2015-03-19
6922:Richard Durrett (19 May 2012).
5778:is the mean recurrence time of
4874:Closest reversible Markov chain
2519:at some point. Formally, state
2511:) if a system started in state
7147:Finite Mathematical Structures
6955:
6946:
6790:Markov chains and mixing times
6780:
6694:
6654:
6649:
6643:
6330:
6286:
6184:
6169:
6148:
6118:
6112:
6091:
6013:
6007:
5986:
5915:
5909:
5888:
5765:
5752:
5570:
5543:
5536:and hence if the Markov chain
5529:{\displaystyle \pi P^{n}=\pi }
5111:
5106:
5098:
5093:
4945:
4940:
4932:
4927:
4808:
4764:
4755:
4711:
4652:
4633:
4597:
4578:
4212:
4168:
4100:
4056:
4037:
3993:
3817:
3811:
3765:
3752:
3679:
3673:
3586:
3580:
3540:
3502:
3461:
3423:
3412:
3406:
3158:does not appear in this list.
2950:
2912:
2766:
2630:
2614:
2595:
2547:
2456:
2437:
2429:
2423:
2388:
2363:
2325:
2306:
2236:
2224:
2206:
2200:
2163:
2157:
2095:
2051:
2006:
1962:
1951:
1945:
1903:
1865:
1820:
1782:
1771:
1765:
1597:
1584:
1564:
1551:
1503:
1357:
1338:
1204:
1142:
1098:
1089:
1045:
1003:
997:
977:
958:
952:
933:
883:
838:
808:
782:
741:
690:
623:
565:
555:are well defined, that is, if
535:
484:
475:
366:
1:
7153:Classical text. cf Chapter 6
7044:
4998:, and any probability vector
1023:
983:{\displaystyle \Pr(X_{1}=y)=}
276:
7024:10.1017/CBO9780511810633.005
5500:This condition implies that
3869:is absorbing if and only if
3849:is finite; otherwise, state
3719:is the expected return time
2721:is not accessible from
676:to the other states at time
270:continuous-time Markov chain
7:
6859:Introduction to Probability
6825:(2nd ed.). CRC Press.
6787:Asher Levin, David (2009).
6141:
6084:
5979:
5881:
5121:{\displaystyle ||\cdot ||.}
2831:must occur in multiples of
2527:if there exists an integer
2126:such that 0 <
2120:Chapman–Kolmogorov equation
668:, where the edges of graph
10:
7235:
7171:, D. van Nostrand Company
7127:. London: Springer-Verlag
6384:
5787:closed communicating class
5649:(in distribution) for any
5642:{\displaystyle X_{n}=\pi }
5609:{\displaystyle X_{0}=\pi }
5405:. This can be written as:
5398:{\displaystyle \pi P=\pi }
4952:{\displaystyle ||\cdot ||}
4517:is not necessarily zero).
4308:The single time-step from
3970:over its states such that
2851:time steps. Formally, the
990:of states as input, where
48:discrete-time Markov chain
18:
7073:10.1017/s0269889706001074
6976:10.1007/978-3-540-89332-5
6962:Serfozo, Richard (2009),
6437:{\displaystyle k_{i}^{A}}
5869:'s). However, if a state
5583:has initial distribution
3481:for the first time after
3277:Transience and recurrence
2534: ≥ 0 such that
2523:is accessible from state
553:conditional probabilities
6714:
6072:is periodic with period
5952:and for any other state
5862:{\displaystyle \pi _{i}}
5835:{\displaystyle \pi _{i}}
5332:Stationary distributions
5065:and which is closest to
4139:and using the shorthand
3485:steps. Therefore, state
6852:"Ch. 11: Markov Chains"
6846:Grinstead, Charles M.;
6400:For a subset of states
6387:Phase-type distribution
5085:according to the norm
3960:Reversible Markov chain
2997:greatest common divisor
2811:if any return to state
2727:directed, acyclic graph
1603:{\displaystyle (X_{n})}
1570:{\displaystyle (Y_{n})}
645:The possible values of
7055:. John Wiley and Sons.
6704:
6678:
6591:
6438:
6396:Expected hitting times
6370:
6337:
6227:
6193:
6127:
6060:
5946:
5863:
5836:
5809:
5772:
5721:
5671:
5643:
5610:
5577:
5530:
5490:
5399:
5370:
5350:
5328:
5315:
5249:
5236:
5166:
5149:
5122:
5079:
5059:
5039:
5012:
4994:which is induced by a
4988:
4953:
4913:
4840:Kolmogorov's criterion
4819:
4692:
4672:
4617:
4482:
4299:
4223:
4107:
3954:absorbing Markov chain
3943:
3829:
3791:
3697:
3659:
3601:
3566:
3468:
3374:
3307:(the "hitting time"):
3267:
3247:
3227:
3207:
3206:{\displaystyle k>1}
3181:
3152:
3132:
3112:
3092:
3033:
3013:
2989:
2966:
2869:
2845:
2825:
2805:
2785:
2645:
2466:
2245:
2105:
2013:
1913:
1827:
1712:
1604:
1571:
1528:
1149:
1010:
984:
917:
890:
818:
751:
636:
545:
343:
203:
202:{\displaystyle X_{10}}
176:
149:
78:. When it is in state
66:. When it is in state
39:
6705:
6679:
6592:
6439:
6371:
6338:
6228:
6194:
6128:
6061:
5967:if it starts at
5947:
5864:
5837:
5810:
5808:{\displaystyle C_{i}}
5773:
5722:
5672:
5644:
5611:
5578:
5531:
5491:
5400:
5371:
5351:
5327:
5316:
5248:
5237:
5164:
5150:
5148:{\displaystyle P^{*}}
5123:
5080:
5060:
5040:
5038:{\displaystyle P^{*}}
5013:
4989:
4954:
4914:
4820:
4693:
4673:
4618:
4510:to himself (that is,
4483:
4300:
4224:
4108:
3944:
3830:
3771:
3698:
3639:
3602:
3546:
3469:
3375:
3268:
3248:
3228:
3208:
3182:
3153:
3133:
3113:
3093:
3034:
3014:
2990:
2988:{\displaystyle \gcd }
2967:
2870:
2846:
2826:
2806:
2786:
2748:it is also true that
2646:
2467:
2263:marginal distribution
2246:
2106:
2014:
1914:
1828:
1713:
1605:
1572:
1529:
1150:
1011:
985:
918:
916:{\displaystyle x_{1}}
891:
819:
752:
637:
546:
344:
204:
177:
175:{\displaystyle X_{0}}
150:
29:
7169:Finite Markov Chains
7155:Finite Markov Chains
7110:Stochastic Processes
7087:Leo Breiman (1992)
7018:. pp. 108–127.
6893:Finite Markov Chains
6688:
6624:
6463:
6448:, starting in state
6416:
6358:
6240:
6215:
6137:
6080:
5975:
5877:
5846:
5819:
5792:
5731:
5684:
5653:
5620:
5587:
5540:
5504:
5412:
5380:
5360:
5349:{\displaystyle \pi }
5340:
5256:
5242:can be computed as
5177:
5165:Simple Markov chain.
5132:
5089:
5069:
5058:{\displaystyle \pi }
5049:
5022:
5011:{\displaystyle \pi }
5002:
4963:
4923:
4882:
4705:
4682:
4627:
4572:
4353:
4239:
4146:
3977:
3876:
3733:
3636:
3496:
3390:
3314:
3293:. Formally, let the
3257:
3237:
3217:
3191:
3165:
3142:
3122:
3102:
3043:
3023:
3003:
2979:
2882:
2859:
2835:
2815:
2795:
2775:
2696:equivalence relation
2541:
2300:
2141:
2029:
1929:
1843:
1749:
1622:
1581:
1548:
1191:
1039:
994:
927:
900:
832:
776:
684:
559:
360:
288:
186:
159:
94:
6653:
6557:
6484:
6433:
6188:
6122:
6017:
5919:
5873:is aperiodic, then
3821:
3707:Positive recurrence
3683:
3590:
3416:
3180:{\displaystyle k=1}
2700:equivalence classes
2634:
2433:
2240:
2210:
2167:
1955:
1775:
16:Probability concept
7061:Science in Context
6819:Lawler, Gregory F.
6700:
6674:
6627:
6587:
6585:
6543:
6529:
6470:
6434:
6419:
6366:
6333:
6271:
6223:
6189:
6156:
6123:
6099:
6056:
6051:
5994:
5942:
5940:
5896:
5859:
5832:
5805:
5768:
5717:
5667:
5639:
5606:
5573:
5526:
5486:
5449:
5395:
5366:
5346:
5329:
5311:
5250:
5232:
5167:
5145:
5118:
5075:
5055:
5035:
5008:
4984:
4949:
4909:
4815:
4688:
4668:
4613:
4478:
4447:
4401:
4365:
4295:
4219:
4103:
3939:
3825:
3798:
3693:
3660:
3597:
3567:
3464:
3393:
3370:
3263:
3243:
3223:
3203:
3177:
3148:
3128:
3108:
3088:
3029:
3009:
2985:
2962:
2865:
2841:
2821:
2801:
2781:
2702:of this relation.
2641:
2601:
2475:(The superscript (
2462:
2410:
2409:
2346:
2241:
2211:
2187:
2186:
2144:
2101:
2009:
1932:
1909:
1823:
1752:
1708:
1600:
1567:
1524:
1522:
1145:
1006:
980:
913:
886:
814:
747:
632:
541:
339:
199:
172:
145:
56:stochastic process
40:
7203:978-0-387-29765-1
7102:. (See Chapter 7)
6985:978-3-540-89331-8
6935:978-1-4614-3615-7
6908:978-0-387-90192-3
6868:978-0-8218-0749-1
6804:978-0-8218-4739-8
6672:
6569:
6514:
6496:
6256:
6050:
5939:
5715:
5432:
5369:{\displaystyle P}
5304:
5291:
5278:
5225:
5212:
5199:
5078:{\displaystyle P}
4691:{\displaystyle n}
4561:) for every
4438:
4392:
4356:
3925:
3901:
3266:{\displaystyle k}
3246:{\displaystyle k}
3226:{\displaystyle k}
3151:{\displaystyle 2}
3131:{\displaystyle 2}
3111:{\displaystyle k}
3075:
3066:
3057:
3032:{\displaystyle k}
3012:{\displaystyle k}
2868:{\displaystyle i}
2844:{\displaystyle k}
2824:{\displaystyle i}
2804:{\displaystyle k}
2784:{\displaystyle i}
2394:
2331:
2171:
1726:-step transitions
1509:
261:stochastic matrix
7226:
7219:Markov processes
7152:
7150:
7084:
7038:
7037:
7008:
7002:
7001:
6959:
6953:
6950:
6944:
6943:
6919:
6913:
6912:
6896:
6887:Snell, J. Laurie
6879:
6873:
6872:
6856:
6848:Snell, J. Laurie
6843:
6837:
6836:
6815:
6809:
6808:
6784:
6778:
6777:
6756:
6709:
6707:
6706:
6701:
6683:
6681:
6680:
6675:
6673:
6671:
6670:
6658:
6652:
6641:
6596:
6594:
6593:
6588:
6586:
6570:
6567:
6556:
6551:
6542:
6541:
6528:
6497:
6494:
6483:
6478:
6443:
6441:
6440:
6435:
6432:
6427:
6375:
6373:
6372:
6367:
6365:
6346:for every state
6342:
6340:
6339:
6334:
6323:
6322:
6304:
6303:
6281:
6280:
6270:
6252:
6251:
6232:
6230:
6229:
6224:
6222:
6198:
6196:
6195:
6190:
6187:
6167:
6155:
6154:
6132:
6130:
6129:
6124:
6121:
6110:
6098:
6097:
6065:
6063:
6062:
6057:
6052:
6049:
6048:
6039:
6038:
6026:
6016:
6005:
5993:
5992:
5951:
5949:
5948:
5943:
5941:
5938:
5937:
5925:
5918:
5907:
5895:
5894:
5868:
5866:
5865:
5860:
5858:
5857:
5841:
5839:
5838:
5833:
5831:
5830:
5814:
5812:
5811:
5806:
5804:
5803:
5777:
5775:
5774:
5769:
5764:
5763:
5751:
5743:
5742:
5726:
5724:
5723:
5718:
5716:
5714:
5713:
5701:
5696:
5695:
5676:
5674:
5673:
5668:
5666:
5648:
5646:
5645:
5640:
5632:
5631:
5615:
5613:
5612:
5607:
5599:
5598:
5582:
5580:
5579:
5574:
5569:
5555:
5554:
5535:
5533:
5532:
5527:
5519:
5518:
5495:
5493:
5492:
5487:
5485:
5484:
5472:
5471:
5459:
5458:
5448:
5447:
5428:
5404:
5402:
5401:
5396:
5375:
5373:
5372:
5367:
5355:
5353:
5352:
5347:
5320:
5318:
5317:
5312:
5310:
5306:
5305:
5297:
5292:
5284:
5279:
5271:
5241:
5239:
5238:
5233:
5231:
5227:
5226:
5218:
5213:
5205:
5200:
5192:
5154:
5152:
5151:
5146:
5144:
5143:
5127:
5125:
5124:
5119:
5114:
5109:
5101:
5096:
5084:
5082:
5081:
5076:
5064:
5062:
5061:
5056:
5044:
5042:
5041:
5036:
5034:
5033:
5017:
5015:
5014:
5009:
4993:
4991:
4990:
4985:
4983:
4982:
4971:
4958:
4956:
4955:
4950:
4948:
4943:
4935:
4930:
4918:
4916:
4915:
4910:
4908:
4907:
4896:
4868:
4862:
4856:
4850:
4836: + 1.
4824:
4822:
4821:
4816:
4801:
4800:
4782:
4781:
4748:
4747:
4723:
4722:
4697:
4695:
4694:
4689:
4677:
4675:
4674:
4669:
4667:
4666:
4645:
4644:
4622:
4620:
4619:
4614:
4612:
4611:
4590:
4589:
4532:
4487:
4485:
4484:
4479:
4473:
4472:
4460:
4459:
4446:
4437:
4436:
4424:
4423:
4411:
4410:
4400:
4388:
4387:
4375:
4374:
4364:
4344:
4323:
4304:
4302:
4301:
4296:
4290:
4289:
4277:
4276:
4264:
4263:
4251:
4250:
4228:
4226:
4225:
4220:
4205:
4204:
4186:
4185:
4161:
4160:
4130:detailed balance
4112:
4110:
4109:
4104:
4093:
4092:
4074:
4073:
4052:
4051:
4030:
4029:
4011:
4010:
3989:
3988:
3968:
3948:
3946:
3945:
3940:
3926:
3923:
3915:
3914:
3902:
3899:
3891:
3890:
3857:Absorbing states
3834:
3832:
3831:
3826:
3820:
3809:
3790:
3785:
3764:
3763:
3745:
3744:
3702:
3700:
3699:
3694:
3682:
3671:
3658:
3653:
3606:
3604:
3603:
3598:
3589:
3578:
3565:
3560:
3533:
3532:
3514:
3513:
3489:is transient if
3473:
3471:
3470:
3465:
3454:
3453:
3435:
3434:
3415:
3404:
3379:
3377:
3376:
3371:
3357:
3356:
3326:
3325:
3272:
3270:
3269:
3264:
3252:
3250:
3249:
3244:
3232:
3230:
3229:
3224:
3212:
3210:
3209:
3204:
3186:
3184:
3183:
3178:
3157:
3155:
3154:
3149:
3137:
3135:
3134:
3129:
3117:
3115:
3114:
3109:
3097:
3095:
3094:
3089:
3073:
3064:
3055:
3038:
3036:
3035:
3030:
3018:
3016:
3015:
3010:
2994:
2992:
2991:
2986:
2971:
2969:
2968:
2963:
2943:
2942:
2924:
2923:
2874:
2872:
2871:
2866:
2850:
2848:
2847:
2842:
2830:
2828:
2827:
2822:
2810:
2808:
2807:
2802:
2790:
2788:
2787:
2782:
2650:
2648:
2647:
2642:
2633:
2629:
2628:
2612:
2588:
2587:
2569:
2568:
2567:
2566:
2471:
2469:
2468:
2463:
2449:
2448:
2432:
2421:
2408:
2381:
2380:
2359:
2358:
2345:
2318:
2317:
2250:
2248:
2247:
2242:
2239:
2222:
2209:
2198:
2185:
2166:
2155:
2130: <
2110:
2108:
2107:
2102:
2088:
2087:
2069:
2068:
2044:
2043:
2018:
2016:
2015:
2010:
1999:
1998:
1980:
1979:
1954:
1943:
1918:
1916:
1915:
1910:
1896:
1895:
1877:
1876:
1858:
1857:
1832:
1830:
1829:
1824:
1813:
1812:
1794:
1793:
1774:
1763:
1717:
1715:
1714:
1709:
1707:
1703:
1702:
1701:
1671:
1670:
1652:
1651:
1634:
1633:
1609:
1607:
1606:
1601:
1596:
1595:
1576:
1574:
1573:
1568:
1563:
1562:
1533:
1531:
1530:
1525:
1523:
1510:
1507:
1502:
1501:
1483:
1482:
1458:
1457:
1439:
1438:
1420:
1419:
1401:
1400:
1382:
1381:
1369:
1368:
1349:
1337:
1336:
1324:
1323:
1305:
1304:
1286:
1285:
1267:
1266:
1248:
1247:
1229:
1228:
1216:
1215:
1197:
1154:
1152:
1151:
1146:
1135:
1134:
1110:
1109:
1082:
1081:
1063:
1062:
1015:
1013:
1012:
1009:{\displaystyle }
1007:
989:
987:
986:
981:
970:
969:
945:
944:
922:
920:
919:
914:
912:
911:
895:
893:
892:
887:
882:
881:
869:
868:
850:
849:
823:
821:
820:
815:
807:
806:
794:
793:
756:
754:
753:
748:
740:
739:
727:
726:
708:
707:
680: + 1,
641:
639:
638:
633:
622:
621:
609:
608:
590:
589:
577:
576:
550:
548:
547:
542:
534:
533:
521:
520:
502:
501:
474:
473:
461:
460:
442:
441:
429:
428:
416:
415:
403:
402:
384:
383:
348:
346:
345:
340:
326:
325:
313:
312:
300:
299:
283:random variables
208:
206:
205:
200:
198:
197:
181:
179:
178:
173:
171:
170:
154:
152:
151:
146:
132:
131:
119:
118:
106:
105:
7234:
7233:
7229:
7228:
7227:
7225:
7224:
7223:
7209:
7208:
7207:
7165:J. Laurie Snell
7157:pp. 384ff.
7047:
7042:
7041:
7034:
7009:
7005:
6986:
6960:
6956:
6951:
6947:
6936:
6920:
6916:
6909:
6883:Kemeny, John G.
6880:
6876:
6869:
6854:
6844:
6840:
6833:
6816:
6812:
6805:
6785:
6781:
6774:
6760:Grimmett, G. R.
6757:
6722:
6717:
6689:
6686:
6685:
6666:
6662:
6657:
6642:
6631:
6625:
6622:
6621:
6605:An instance of
6603:
6601:Ergodic theorem
6584:
6583:
6568: for
6566:
6564:
6552:
6547:
6534:
6530:
6518:
6508:
6507:
6495: for
6493:
6491:
6479:
6474:
6466:
6464:
6461:
6460:
6444:represents the
6428:
6423:
6417:
6414:
6413:
6398:
6389:
6383:
6361:
6359:
6356:
6355:
6350:and every time
6318:
6314:
6293:
6289:
6276:
6272:
6260:
6247:
6243:
6241:
6238:
6237:
6218:
6216:
6213:
6212:
6209:
6168:
6160:
6144:
6140:
6138:
6135:
6134:
6111:
6103:
6087:
6083:
6081:
6078:
6077:
6044:
6040:
6031:
6027:
6024:
6006:
5998:
5982:
5978:
5976:
5973:
5972:
5961:
5933:
5929:
5923:
5908:
5900:
5884:
5880:
5878:
5875:
5874:
5853:
5849:
5847:
5844:
5843:
5826:
5822:
5820:
5817:
5816:
5799:
5795:
5793:
5790:
5789:
5759:
5755:
5747:
5738:
5734:
5732:
5729:
5728:
5709:
5705:
5700:
5691:
5687:
5685:
5682:
5681:
5662:
5654:
5651:
5650:
5627:
5623:
5621:
5618:
5617:
5594:
5590:
5588:
5585:
5584:
5565:
5550:
5546:
5541:
5538:
5537:
5514:
5510:
5505:
5502:
5501:
5480:
5476:
5464:
5460:
5454:
5450:
5443:
5436:
5424:
5413:
5410:
5409:
5381:
5378:
5377:
5376:if and only if
5361:
5358:
5357:
5341:
5338:
5337:
5336:A distribution
5334:
5296:
5283:
5270:
5269:
5265:
5257:
5254:
5253:
5217:
5204:
5191:
5190:
5186:
5178:
5175:
5174:
5171:Frobenius Norm
5139:
5135:
5133:
5130:
5129:
5110:
5105:
5097:
5092:
5090:
5087:
5086:
5070:
5067:
5066:
5050:
5047:
5046:
5029:
5025:
5023:
5020:
5019:
5003:
5000:
4999:
4972:
4967:
4966:
4964:
4961:
4960:
4944:
4939:
4931:
4926:
4924:
4921:
4920:
4897:
4892:
4891:
4883:
4880:
4879:
4876:
4866:
4860:
4854:
4848:
4796:
4792:
4771:
4767:
4737:
4733:
4718:
4714:
4706:
4703:
4702:
4683:
4680:
4679:
4662:
4658:
4640:
4636:
4628:
4625:
4624:
4607:
4603:
4585:
4581:
4573:
4570:
4569:
4556:
4543:
4530:
4515:
4502:sums to 1 over
4500:
4468:
4464:
4452:
4448:
4442:
4432:
4428:
4416:
4412:
4406:
4402:
4396:
4380:
4376:
4370:
4366:
4360:
4354:
4351:
4350:
4342:
4338:
4328:
4321:
4282:
4278:
4272:
4268:
4256:
4252:
4246:
4242:
4240:
4237:
4236:
4200:
4196:
4175:
4171:
4153:
4149:
4147:
4144:
4143:
4120:and all states
4088:
4084:
4063:
4059:
4047:
4043:
4025:
4021:
4000:
3996:
3984:
3980:
3978:
3975:
3974:
3966:
3962:
3924: for
3922:
3907:
3903:
3900: and
3898:
3883:
3879:
3877:
3874:
3873:
3859:
3847:
3810:
3802:
3786:
3775:
3759:
3755:
3740:
3736:
3734:
3731:
3730:
3724:
3709:
3672:
3664:
3654:
3643:
3637:
3634:
3633:
3579:
3571:
3561:
3550:
3528:
3524:
3509:
3505:
3497:
3494:
3493:
3449:
3445:
3430:
3426:
3405:
3397:
3391:
3388:
3387:
3352:
3348:
3321:
3317:
3315:
3312:
3311:
3301:
3295:random variable
3279:
3258:
3255:
3254:
3238:
3235:
3234:
3218:
3215:
3214:
3192:
3189:
3188:
3166:
3163:
3162:
3143:
3140:
3139:
3123:
3120:
3119:
3103:
3100:
3099:
3044:
3041:
3040:
3024:
3021:
3020:
3004:
3001:
3000:
2980:
2977:
2976:
2938:
2934:
2919:
2915:
2883:
2880:
2879:
2860:
2857:
2856:
2836:
2833:
2832:
2816:
2813:
2812:
2796:
2793:
2792:
2776:
2773:
2772:
2769:
2621:
2617:
2613:
2605:
2583:
2579:
2559:
2555:
2554:
2550:
2542:
2539:
2538:
2532:
2493:
2444:
2440:
2422:
2414:
2398:
2370:
2366:
2351:
2347:
2335:
2313:
2309:
2301:
2298:
2297:
2288:
2273:
2223:
2215:
2199:
2191:
2175:
2156:
2148:
2142:
2139:
2138:
2122:, that for any
2083:
2079:
2058:
2054:
2036:
2032:
2030:
2027:
2026:
1994:
1990:
1969:
1965:
1944:
1936:
1930:
1927:
1926:
1891:
1887:
1872:
1868:
1850:
1846:
1844:
1841:
1840:
1808:
1804:
1789:
1785:
1764:
1756:
1750:
1747:
1746:
1728:
1685:
1681:
1660:
1656:
1647:
1643:
1642:
1638:
1629:
1625:
1623:
1620:
1619:
1591:
1587:
1582:
1579:
1578:
1558:
1554:
1549:
1546:
1545:
1521:
1520:
1508: for
1506:
1491:
1487:
1472:
1468:
1447:
1443:
1428:
1424:
1409:
1405:
1390:
1386:
1377:
1373:
1364:
1360:
1350:
1348:
1342:
1341:
1332:
1328:
1319:
1315:
1294:
1290:
1275:
1271:
1256:
1252:
1237:
1233:
1224:
1220:
1211:
1207:
1194:
1192:
1189:
1188:
1124:
1120:
1105:
1101:
1077:
1073:
1052:
1048:
1040:
1037:
1036:
1026:
1018:Iverson bracket
995:
992:
991:
965:
961:
940:
936:
928:
925:
924:
907:
903:
901:
898:
897:
877:
873:
864:
860:
845:
841:
833:
830:
829:
802:
798:
789:
785:
777:
774:
773:
735:
731:
722:
718:
697:
693:
685:
682:
681:
666:directed graphs
653:
617:
613:
604:
600:
585:
581:
572:
568:
560:
557:
556:
529:
525:
516:
512:
491:
487:
469:
465:
456:
452:
437:
433:
424:
420:
411:
407:
398:
394:
373:
369:
361:
358:
357:
351:Markov property
321:
317:
308:
304:
295:
291:
289:
286:
285:
279:
254:Markov property
215:natural numbers
211:random variable
193:
189:
187:
184:
183:
166:
162:
160:
157:
156:
127:
123:
114:
110:
101:
97:
95:
92:
91:
24:
17:
12:
11:
5:
7232:
7222:
7221:
7206:
7205:
7189:
7179:
7161:John G. Kemeny
7158:
7140:
7121:
7103:
7085:
7056:
7048:
7046:
7043:
7040:
7039:
7032:
7003:
6984:
6954:
6945:
6934:
6914:
6907:
6874:
6867:
6838:
6831:
6810:
6803:
6779:
6772:
6719:
6718:
6716:
6713:
6712:
6711:
6699:
6696:
6693:
6669:
6665:
6661:
6656:
6651:
6648:
6645:
6640:
6637:
6634:
6630:
6607:ergodic theory
6602:
6599:
6598:
6597:
6582:
6579:
6576:
6573:
6565:
6563:
6560:
6555:
6550:
6546:
6540:
6537:
6533:
6527:
6524:
6521:
6517:
6513:
6510:
6509:
6506:
6503:
6500:
6492:
6490:
6487:
6482:
6477:
6473:
6469:
6468:
6446:expected value
6431:
6426:
6422:
6397:
6394:
6385:Main article:
6382:
6379:
6364:
6344:
6343:
6332:
6329:
6326:
6321:
6317:
6313:
6310:
6307:
6302:
6299:
6296:
6292:
6288:
6285:
6279:
6275:
6269:
6266:
6263:
6259:
6255:
6250:
6246:
6221:
6208:
6205:
6186:
6183:
6180:
6177:
6174:
6171:
6166:
6163:
6159:
6153:
6150:
6147:
6143:
6120:
6117:
6114:
6109:
6106:
6102:
6096:
6093:
6090:
6086:
6055:
6047:
6043:
6037:
6034:
6030:
6023:
6020:
6015:
6012:
6009:
6004:
6001:
5997:
5991:
5988:
5985:
5981:
5959:
5936:
5932:
5928:
5922:
5917:
5914:
5911:
5906:
5903:
5899:
5893:
5890:
5887:
5883:
5856:
5852:
5829:
5825:
5802:
5798:
5767:
5762:
5758:
5754:
5750:
5746:
5741:
5737:
5712:
5708:
5704:
5699:
5694:
5690:
5665:
5661:
5658:
5638:
5635:
5630:
5626:
5605:
5602:
5597:
5593:
5572:
5568:
5564:
5561:
5558:
5553:
5549:
5545:
5525:
5522:
5517:
5513:
5509:
5498:
5497:
5483:
5479:
5475:
5470:
5467:
5463:
5457:
5453:
5446:
5442:
5439:
5435:
5431:
5427:
5423:
5420:
5417:
5394:
5391:
5388:
5385:
5365:
5345:
5333:
5330:
5309:
5303:
5300:
5295:
5290:
5287:
5282:
5277:
5274:
5268:
5264:
5261:
5230:
5224:
5221:
5216:
5211:
5208:
5203:
5198:
5195:
5189:
5185:
5182:
5142:
5138:
5117:
5113:
5108:
5104:
5100:
5095:
5074:
5054:
5032:
5028:
5007:
4996:scalar product
4981:
4978:
4975:
4970:
4947:
4942:
4938:
4934:
4929:
4906:
4903:
4900:
4895:
4890:
4887:
4875:
4872:
4826:
4825:
4814:
4810:
4807:
4804:
4799:
4795:
4791:
4788:
4785:
4780:
4777:
4774:
4770:
4766:
4763:
4760:
4757:
4754:
4751:
4746:
4743:
4740:
4736:
4732:
4729:
4726:
4721:
4717:
4713:
4710:
4687:
4665:
4661:
4657:
4654:
4651:
4648:
4643:
4639:
4635:
4632:
4610:
4606:
4602:
4599:
4596:
4593:
4588:
4584:
4580:
4577:
4552:
4538:
4513:
4498:
4489:
4488:
4477:
4471:
4467:
4463:
4458:
4455:
4451:
4445:
4441:
4435:
4431:
4427:
4422:
4419:
4415:
4409:
4405:
4399:
4395:
4391:
4386:
4383:
4379:
4373:
4369:
4363:
4359:
4336:
4324:
4306:
4305:
4294:
4288:
4285:
4281:
4275:
4271:
4267:
4262:
4259:
4255:
4249:
4245:
4230:
4229:
4218:
4214:
4211:
4208:
4203:
4199:
4195:
4192:
4189:
4184:
4181:
4178:
4174:
4170:
4167:
4164:
4159:
4156:
4152:
4116:for all times
4114:
4113:
4102:
4099:
4096:
4091:
4087:
4083:
4080:
4077:
4072:
4069:
4066:
4062:
4058:
4055:
4050:
4046:
4042:
4039:
4036:
4033:
4028:
4024:
4020:
4017:
4014:
4009:
4006:
4003:
3999:
3995:
3992:
3987:
3983:
3961:
3958:
3950:
3949:
3938:
3935:
3932:
3929:
3921:
3918:
3913:
3910:
3906:
3897:
3894:
3889:
3886:
3882:
3858:
3855:
3845:
3836:
3835:
3824:
3819:
3816:
3813:
3808:
3805:
3801:
3797:
3794:
3789:
3784:
3781:
3778:
3774:
3770:
3767:
3762:
3758:
3754:
3751:
3748:
3743:
3739:
3722:
3708:
3705:
3704:
3703:
3692:
3689:
3686:
3681:
3678:
3675:
3670:
3667:
3663:
3657:
3652:
3649:
3646:
3642:
3623:if and only if
3608:
3607:
3596:
3593:
3588:
3585:
3582:
3577:
3574:
3570:
3564:
3559:
3556:
3553:
3549:
3545:
3542:
3539:
3536:
3531:
3527:
3523:
3520:
3517:
3512:
3508:
3504:
3501:
3475:
3474:
3463:
3460:
3457:
3452:
3448:
3444:
3441:
3438:
3433:
3429:
3425:
3422:
3419:
3414:
3411:
3408:
3403:
3400:
3396:
3381:
3380:
3369:
3366:
3363:
3360:
3355:
3351:
3347:
3344:
3341:
3338:
3335:
3332:
3329:
3324:
3320:
3299:
3278:
3275:
3262:
3242:
3222:
3202:
3199:
3196:
3176:
3173:
3170:
3147:
3138:, even though
3127:
3107:
3087:
3084:
3081:
3078:
3072:
3069:
3063:
3060:
3054:
3051:
3048:
3028:
3008:
2984:
2973:
2972:
2961:
2958:
2955:
2952:
2949:
2946:
2941:
2937:
2933:
2930:
2927:
2922:
2918:
2914:
2911:
2908:
2905:
2902:
2899:
2896:
2893:
2890:
2887:
2875:is defined as
2864:
2840:
2820:
2800:
2780:
2768:
2765:
2652:
2651:
2640:
2637:
2632:
2627:
2624:
2620:
2616:
2611:
2608:
2604:
2600:
2597:
2594:
2591:
2586:
2582:
2578:
2575:
2572:
2565:
2562:
2558:
2553:
2549:
2546:
2530:
2492:
2489:
2473:
2472:
2461:
2458:
2455:
2452:
2447:
2443:
2439:
2436:
2431:
2428:
2425:
2420:
2417:
2413:
2407:
2404:
2401:
2397:
2393:
2390:
2387:
2384:
2379:
2376:
2373:
2369:
2365:
2362:
2357:
2354:
2350:
2344:
2341:
2338:
2334:
2330:
2327:
2324:
2321:
2316:
2312:
2308:
2305:
2286:
2269:
2252:
2251:
2238:
2235:
2232:
2229:
2226:
2221:
2218:
2214:
2208:
2205:
2202:
2197:
2194:
2190:
2184:
2181:
2178:
2174:
2170:
2165:
2162:
2159:
2154:
2151:
2147:
2112:
2111:
2100:
2097:
2094:
2091:
2086:
2082:
2078:
2075:
2072:
2067:
2064:
2061:
2057:
2053:
2050:
2047:
2042:
2039:
2035:
2020:
2019:
2008:
2005:
2002:
1997:
1993:
1989:
1986:
1983:
1978:
1975:
1972:
1968:
1964:
1961:
1958:
1953:
1950:
1947:
1942:
1939:
1935:
1920:
1919:
1908:
1905:
1902:
1899:
1894:
1890:
1886:
1883:
1880:
1875:
1871:
1867:
1864:
1861:
1856:
1853:
1849:
1834:
1833:
1822:
1819:
1816:
1811:
1807:
1803:
1800:
1797:
1792:
1788:
1784:
1781:
1778:
1773:
1770:
1767:
1762:
1759:
1755:
1742:time steps is
1727:
1721:
1720:
1719:
1706:
1700:
1697:
1694:
1691:
1688:
1684:
1680:
1677:
1674:
1669:
1666:
1663:
1659:
1655:
1650:
1646:
1641:
1637:
1632:
1628:
1599:
1594:
1590:
1586:
1566:
1561:
1557:
1553:
1537:
1536:
1535:
1534:
1519:
1516:
1513:
1505:
1500:
1497:
1494:
1490:
1486:
1481:
1478:
1475:
1471:
1467:
1464:
1461:
1456:
1453:
1450:
1446:
1442:
1437:
1434:
1431:
1427:
1423:
1418:
1415:
1412:
1408:
1404:
1399:
1396:
1393:
1389:
1385:
1380:
1376:
1372:
1367:
1363:
1359:
1356:
1353:
1351:
1347:
1344:
1343:
1340:
1335:
1331:
1327:
1322:
1318:
1314:
1311:
1308:
1303:
1300:
1297:
1293:
1289:
1284:
1281:
1278:
1274:
1270:
1265:
1262:
1259:
1255:
1251:
1246:
1243:
1240:
1236:
1232:
1227:
1223:
1219:
1214:
1210:
1206:
1203:
1200:
1198:
1196:
1178:
1177:
1169:
1168:
1157:
1156:
1155:
1144:
1141:
1138:
1133:
1130:
1127:
1123:
1119:
1116:
1113:
1108:
1104:
1100:
1097:
1094:
1091:
1088:
1085:
1080:
1076:
1072:
1069:
1066:
1061:
1058:
1055:
1051:
1047:
1044:
1031:
1030:
1025:
1022:
1005:
1002:
999:
979:
976:
973:
968:
964:
960:
957:
954:
951:
948:
943:
939:
935:
932:
910:
906:
885:
880:
876:
872:
867:
863:
859:
856:
853:
848:
844:
840:
837:
813:
810:
805:
801:
797:
792:
788:
784:
781:
746:
743:
738:
734:
730:
725:
721:
717:
714:
711:
706:
703:
700:
696:
692:
689:
649:
643:
642:
631:
628:
625:
620:
616:
612:
607:
603:
599:
596:
593:
588:
584:
580:
575:
571:
567:
564:
540:
537:
532:
528:
524:
519:
515:
511:
508:
505:
500:
497:
494:
490:
486:
483:
480:
477:
472:
468:
464:
459:
455:
451:
448:
445:
440:
436:
432:
427:
423:
419:
414:
410:
406:
401:
397:
393:
390:
387:
382:
379:
376:
372:
368:
365:
338:
335:
332:
329:
324:
320:
316:
311:
307:
303:
298:
294:
278:
275:
196:
192:
169:
165:
144:
141:
138:
135:
130:
126:
122:
117:
113:
109:
104:
100:
15:
9:
6:
4:
3:
2:
7231:
7220:
7217:
7216:
7214:
7204:
7200:
7196:
7193:
7190:
7188:
7187:0-521-60494-X
7184:
7180:
7178:
7177:0-442-04328-7
7174:
7170:
7166:
7162:
7159:
7156:
7149:
7148:
7141:
7138:
7134:
7133:0-387-19832-6
7130:
7126:
7122:
7119:
7118:0-471-52369-0
7115:
7111:
7107:
7104:
7101:
7100:0-89871-296-3
7097:
7094:
7090:
7086:
7082:
7078:
7074:
7070:
7066:
7062:
7057:
7054:
7050:
7049:
7035:
7033:9780511810633
7029:
7025:
7021:
7017:
7016:Markov Chains
7013:
7012:Norris, J. R.
7007:
6999:
6995:
6991:
6987:
6981:
6977:
6973:
6969:
6965:
6958:
6949:
6941:
6937:
6931:
6927:
6926:
6918:
6910:
6904:
6900:
6895:
6894:
6888:
6884:
6878:
6870:
6864:
6860:
6853:
6850:(July 1997).
6849:
6842:
6834:
6832:1-58488-651-X
6828:
6824:
6820:
6814:
6806:
6800:
6796:
6792:
6791:
6783:
6775:
6769:
6765:
6761:
6755:
6753:
6751:
6749:
6747:
6745:
6743:
6741:
6739:
6737:
6735:
6733:
6731:
6729:
6727:
6725:
6720:
6691:
6667:
6663:
6659:
6646:
6638:
6635:
6632:
6628:
6620:
6619:
6618:
6616:
6612:
6608:
6580:
6577:
6574:
6571:
6561:
6558:
6553:
6548:
6544:
6538:
6535:
6531:
6525:
6522:
6519:
6515:
6511:
6504:
6501:
6498:
6488:
6485:
6480:
6475:
6471:
6459:
6458:
6457:
6455:
6451:
6447:
6429:
6424:
6420:
6411:
6408:, the vector
6407:
6404: ⊆
6403:
6393:
6388:
6381:Hitting times
6378:
6353:
6349:
6327:
6324:
6319:
6315:
6311:
6308:
6305:
6300:
6297:
6294:
6290:
6277:
6273:
6267:
6264:
6261:
6257:
6253:
6248:
6244:
6236:
6235:
6234:
6204:
6202:
6181:
6178:
6175:
6172:
6164:
6161:
6157:
6145:
6115:
6107:
6104:
6100:
6088:
6075:
6071:
6066:
6053:
6045:
6041:
6035:
6032:
6028:
6021:
6018:
6010:
6002:
5999:
5995:
5983:
5970:
5966:
5962:
5955:
5934:
5930:
5926:
5920:
5912:
5904:
5901:
5897:
5885:
5872:
5854:
5850:
5827:
5823:
5800:
5796:
5788:
5783:
5781:
5760:
5756:
5744:
5739:
5735:
5710:
5706:
5702:
5697:
5692:
5688:
5678:
5659:
5656:
5636:
5633:
5628:
5624:
5603:
5600:
5595:
5591:
5562:
5559:
5556:
5551:
5547:
5523:
5520:
5515:
5511:
5507:
5481:
5477:
5473:
5468:
5465:
5461:
5455:
5451:
5440:
5437:
5433:
5429:
5421:
5418:
5408:
5407:
5406:
5392:
5389:
5386:
5383:
5363:
5343:
5326:
5322:
5307:
5301:
5298:
5293:
5288:
5285:
5280:
5275:
5272:
5266:
5262:
5259:
5247:
5243:
5228:
5222:
5219:
5214:
5209:
5206:
5201:
5196:
5193:
5187:
5183:
5180:
5172:
5163:
5159:
5156:
5140:
5136:
5115:
5102:
5072:
5052:
5030:
5026:
5005:
4997:
4979:
4976:
4973:
4936:
4904:
4901:
4898:
4888:
4885:
4871:
4869:
4863:
4857:
4851:
4844:
4841:
4837:
4835:
4831:
4812:
4805:
4802:
4797:
4793:
4789:
4786:
4783:
4778:
4775:
4772:
4768:
4758:
4752:
4749:
4744:
4741:
4738:
4734:
4730:
4727:
4724:
4719:
4715:
4701:
4700:
4699:
4685:
4663:
4659:
4655:
4649:
4646:
4641:
4637:
4608:
4604:
4600:
4594:
4591:
4586:
4582:
4566:
4564:
4560:
4557: =
4555:
4551:
4548: |
4547:
4544: =
4541:
4537:
4533:
4527:
4523:
4518:
4516:
4509:
4505:
4501:
4494:
4475:
4469:
4465:
4461:
4456:
4453:
4449:
4443:
4439:
4433:
4429:
4425:
4420:
4417:
4413:
4407:
4403:
4397:
4393:
4389:
4384:
4381:
4377:
4371:
4367:
4361:
4357:
4349:
4348:
4347:
4345:
4339:
4332:
4327:
4319:
4315:
4311:
4292:
4286:
4283:
4279:
4273:
4269:
4265:
4260:
4257:
4253:
4247:
4243:
4235:
4234:
4233:
4216:
4209:
4206:
4201:
4197:
4193:
4190:
4187:
4182:
4179:
4176:
4172:
4162:
4157:
4154:
4150:
4142:
4141:
4140:
4138:
4133:
4131:
4127:
4123:
4119:
4097:
4094:
4089:
4085:
4081:
4078:
4075:
4070:
4067:
4064:
4060:
4048:
4044:
4040:
4034:
4031:
4026:
4022:
4018:
4015:
4012:
4007:
4004:
4001:
3997:
3985:
3981:
3973:
3972:
3971:
3969:
3957:
3955:
3936:
3933:
3930:
3927:
3919:
3916:
3911:
3908:
3904:
3895:
3892:
3887:
3884:
3880:
3872:
3871:
3870:
3868:
3864:
3854:
3852:
3848:
3841:
3822:
3814:
3806:
3803:
3799:
3795:
3792:
3782:
3779:
3776:
3772:
3768:
3760:
3756:
3749:
3746:
3741:
3737:
3729:
3728:
3727:
3725:
3718:
3714:
3690:
3684:
3676:
3668:
3665:
3661:
3650:
3647:
3644:
3640:
3632:
3631:
3630:
3629:is infinite:
3628:
3624:
3621:is recurrent
3620:
3615:
3613:
3594:
3591:
3583:
3575:
3572:
3568:
3557:
3554:
3551:
3547:
3543:
3537:
3534:
3529:
3525:
3521:
3515:
3510:
3506:
3492:
3491:
3490:
3488:
3484:
3480:
3458:
3455:
3450:
3446:
3442:
3439:
3436:
3431:
3427:
3417:
3409:
3401:
3398:
3394:
3386:
3385:
3384:
3367:
3361:
3358:
3353:
3349:
3345:
3342:
3339:
3336:
3327:
3322:
3318:
3310:
3309:
3308:
3306:
3302:
3296:
3292:
3288:
3284:
3274:
3260:
3240:
3220:
3200:
3197:
3194:
3174:
3171:
3168:
3159:
3145:
3125:
3105:
3082:
3079:
3076:
3070:
3067:
3061:
3058:
3052:
3049:
3026:
3006:
2998:
2956:
2953:
2947:
2944:
2939:
2935:
2931:
2928:
2925:
2920:
2916:
2906:
2903:
2900:
2897:
2888:
2885:
2878:
2877:
2876:
2862:
2854:
2838:
2818:
2798:
2778:
2764:
2761:
2759:
2755:
2752: →
2751:
2747:
2744: →
2743:
2739:
2735:
2730:
2728:
2724:
2720:
2717:is not, then
2716:
2712:
2708:
2703:
2701:
2697:
2693:
2689:
2685:
2682: →
2681:
2677:
2674: →
2673:
2669:
2666: ↔
2665:
2661:
2657:
2638:
2635:
2625:
2622:
2618:
2609:
2606:
2602:
2598:
2592:
2589:
2584:
2580:
2576:
2573:
2570:
2563:
2560:
2556:
2551:
2537:
2536:
2535:
2533:
2526:
2522:
2518:
2514:
2510:
2507: →
2506:
2502:
2498:
2488:
2486:
2483:, and not an
2482:
2478:
2459:
2453:
2450:
2445:
2441:
2426:
2418:
2415:
2411:
2405:
2402:
2399:
2395:
2391:
2385:
2382:
2377:
2374:
2371:
2367:
2355:
2352:
2348:
2342:
2339:
2336:
2332:
2328:
2322:
2319:
2314:
2310:
2296:
2295:
2294:
2292:
2289: =
2285:
2281:
2277:
2274: =
2272:
2268:
2264:
2259:
2257:
2233:
2230:
2227:
2219:
2216:
2212:
2203:
2195:
2192:
2188:
2182:
2179:
2176:
2172:
2168:
2160:
2152:
2149:
2145:
2137:
2136:
2135:
2133:
2129:
2125:
2121:
2117:
2098:
2092:
2089:
2084:
2080:
2076:
2073:
2070:
2065:
2062:
2059:
2055:
2045:
2040:
2037:
2033:
2025:
2024:
2023:
2003:
2000:
1995:
1991:
1987:
1984:
1981:
1976:
1973:
1970:
1966:
1956:
1948:
1940:
1937:
1933:
1925:
1924:
1923:
1906:
1900:
1897:
1892:
1888:
1884:
1881:
1878:
1873:
1869:
1859:
1854:
1851:
1847:
1839:
1838:
1837:
1817:
1814:
1809:
1805:
1801:
1798:
1795:
1790:
1786:
1776:
1768:
1760:
1757:
1753:
1745:
1744:
1743:
1741:
1737:
1733:
1725:
1704:
1698:
1695:
1692:
1689:
1686:
1682:
1678:
1675:
1672:
1667:
1664:
1661:
1657:
1653:
1648:
1644:
1639:
1635:
1630:
1626:
1617:
1613:
1592:
1588:
1559:
1555:
1543:
1539:
1538:
1517:
1514:
1511:
1498:
1495:
1492:
1488:
1484:
1479:
1476:
1473:
1469:
1465:
1462:
1459:
1454:
1451:
1448:
1444:
1440:
1435:
1432:
1429:
1425:
1421:
1416:
1413:
1410:
1406:
1402:
1397:
1394:
1391:
1387:
1383:
1378:
1374:
1370:
1365:
1361:
1352:
1345:
1333:
1329:
1325:
1320:
1316:
1312:
1309:
1306:
1301:
1298:
1295:
1291:
1287:
1282:
1279:
1276:
1272:
1268:
1263:
1260:
1257:
1253:
1249:
1244:
1241:
1238:
1234:
1230:
1225:
1221:
1217:
1212:
1208:
1199:
1187:
1186:
1184:
1180:
1179:
1175:
1171:
1170:
1166:
1162:
1158:
1139:
1136:
1131:
1128:
1125:
1121:
1117:
1114:
1111:
1106:
1102:
1092:
1086:
1083:
1078:
1074:
1070:
1067:
1064:
1059:
1056:
1053:
1049:
1035:
1034:
1033:
1032:
1028:
1027:
1021:
1019:
1000:
974:
971:
966:
962:
955:
949:
946:
941:
937:
908:
904:
878:
874:
870:
865:
861:
857:
854:
851:
846:
842:
827:
826:state machine
811:
803:
799:
795:
790:
786:
770:
768:
764:
760:
744:
736:
732:
728:
723:
719:
715:
712:
709:
704:
701:
698:
694:
679:
675:
671:
667:
662:
660:
657:
656:countable set
652:
648:
629:
626:
618:
614:
610:
605:
601:
597:
594:
591:
586:
582:
578:
573:
569:
554:
538:
530:
526:
522:
517:
513:
509:
506:
503:
498:
495:
492:
488:
478:
470:
466:
462:
457:
453:
449:
446:
443:
438:
434:
430:
425:
421:
417:
412:
408:
404:
399:
395:
391:
388:
385:
380:
377:
374:
370:
356:
355:
354:
352:
336:
333:
330:
327:
322:
318:
314:
309:
305:
301:
296:
292:
284:
274:
271:
266:
262:
257:
255:
251:
247:
243:
239:
235:
231:
228:and moves to
227:
223:
218:
216:
212:
194:
190:
167:
163:
142:
139:
136:
133:
128:
124:
120:
115:
111:
107:
102:
98:
89:
85:
81:
77:
73:
69:
65:
61:
57:
53:
49:
45:
37:
33:
28:
22:
7194:
7168:
7154:
7146:
7124:
7109:
7088:
7064:
7060:
7052:
7015:
7006:
6967:
6957:
6948:
6924:
6917:
6892:
6877:
6858:
6841:
6822:
6813:
6789:
6782:
6763:
6614:
6610:
6604:
6453:
6449:
6409:
6405:
6401:
6399:
6390:
6351:
6347:
6345:
6210:
6200:
6073:
6069:
6067:
5968:
5964:
5957:
5953:
5870:
5784:
5779:
5679:
5499:
5335:
5251:
5168:
5157:
4877:
4865:
4859:
4853:
4847:
4845:
4838:
4833:
4829:
4827:
4567:
4562:
4558:
4553:
4549:
4545:
4539:
4535:
4529:
4525:
4521:
4519:
4511:
4507:
4503:
4496:
4492:
4490:
4341:
4334:
4330:
4325:
4317:
4313:
4309:
4307:
4231:
4136:
4134:
4125:
4121:
4117:
4115:
3965:
3963:
3951:
3866:
3862:
3860:
3850:
3843:
3839:
3837:
3720:
3716:
3710:
3626:
3618:
3616:
3611:
3609:
3486:
3482:
3478:
3476:
3382:
3304:
3297:
3290:
3286:
3282:
3280:
3160:
3098:time steps;
2974:
2770:
2762:
2757:
2753:
2749:
2745:
2741:
2737:
2733:
2731:
2722:
2718:
2714:
2710:
2706:
2704:
2691:
2687:
2683:
2679:
2675:
2671:
2667:
2663:
2659:
2655:
2653:
2528:
2524:
2520:
2516:
2512:
2508:
2504:
2500:
2496:
2494:
2476:
2474:
2290:
2283:
2279:
2275:
2270:
2266:
2260:
2255:
2253:
2131:
2127:
2123:
2115:
2113:
2021:
1921:
1835:
1739:
1735:
1731:
1729:
1723:
1618:values, ie.
1615:
1611:
1541:
1182:
1173:
1164:
1160:
771:
766:
762:
758:
677:
673:
669:
663:
658:
650:
646:
644:
280:
264:
258:
249:
245:
241:
237:
233:
229:
225:
221:
219:
87:
83:
79:
75:
71:
67:
63:
59:
51:
47:
41:
35:
31:
21:Markov chain
7089:Probability
6068:If a state
5128:The matrix
4919:, any norm
4333:a fraction
3713:expectation
3383:The number
2791:has period
2767:Periodicity
1614:-tuples of
44:probability
7192:Seneta, E.
7135:. online:
7106:J. L. Doob
7045:References
6793:. p.
6773:0198572220
6233:such that
2756:. A state
2740:such that
2670:) if both
1024:Variations
277:Definition
7081:144854176
6698:∞
6695:→
6655:→
6575:∉
6523:∈
6516:∑
6512:−
6502:∈
6363:π
6312:∣
6274:π
6265:∈
6258:∑
6245:π
6220:π
6152:∞
6149:→
6095:∞
6092:→
5990:∞
5987:→
5892:∞
5889:→
5851:π
5824:π
5689:π
5660:∈
5637:π
5604:π
5563:∈
5524:π
5508:π
5478:π
5452:π
5441:∈
5434:∑
5422:∈
5416:∀
5393:π
5384:π
5344:π
5260:π
5181:π
5141:∗
5103:⋅
5053:π
5031:∗
5006:π
4977:×
4937:⋅
4902:×
4889:∈
4832:and
4660:π
4605:π
4466:π
4440:∑
4430:π
4404:π
4394:∑
4368:π
4358:∑
4270:π
4244:π
4194:∣
4082:∣
4045:π
4019:∣
3982:π
3796:⋅
3788:∞
3773:∑
3688:∞
3656:∞
3641:∑
3563:∞
3548:∑
3522:∣
3519:∞
3443:∣
3340:≥
3118:would be
3083:…
2932:∣
2855:of state
2662:(written
2577:∣
2503:(written
2403:∈
2396:∑
2375:−
2340:∈
2333:∑
2231:−
2180:∈
2173:∑
2077:∣
1988:∣
1885:∣
1802:∣
1734:to state
1690:−
1676:…
1665:−
1496:−
1477:−
1463:…
1452:−
1433:−
1414:−
1395:−
1384:∣
1310:…
1299:−
1280:−
1261:−
1242:−
1231:∣
1129:−
1118:∣
1071:∣
858:∣
716:∣
595:…
510:∣
447:…
392:∣
349:with the
7213:Category
6998:archived
6940:Archived
6821:(2006).
4678:for all
3931:≠
3861:A state
3617:A state
3281:A state
2771:A state
2732:A state
2654:A state
2495:A state
2485:exponent
2479:) is an
1159:for all
761:to time
551:if both
7167:(1960)
7108:(1953)
6994:2484222
4623:, then
4320:having
2995:is the
2975:(where
1016:is the
654:form a
209:is the
7201:
7185:
7175:
7163:&
7131:
7116:
7098:
7079:
7030:
6992:
6982:
6970:: 35,
6932:
6905:
6865:
6829:
6801:
6770:
5956:, let
5727:where
3838:State
3610:State
3074:
3065:
3056:
2853:period
2709:is in
2254:where
1181:where
7077:S2CID
6855:(PDF)
6715:Notes
6354:then
5616:then
2481:index
1577:from
155:then
7199:ISBN
7183:ISBN
7173:ISBN
7137:MCSS
7129:ISBN
7114:ISBN
7096:ISBN
7028:ISBN
6980:ISBN
6930:ISBN
6903:ISBN
6863:ISBN
6827:ISBN
6799:ISBN
6768:ISBN
6613:and
4124:and
3592:<
3516:<
3198:>
2954:>
2901:>
2713:but
2678:and
2636:>
2261:The
2114:The
2022:and
1515:>
627:>
224:and
62:and
52:DTMC
46:, a
34:and
7069:doi
7020:doi
6972:doi
6899:224
6684:as
6142:lim
6085:lim
5980:lim
5882:lim
4959:on
4520:As
4312:to
3331:inf
3161:If
2983:gcd
2892:gcd
2487:).
2265:Pr(
1738:in
42:In
7215::
7075:.
7065:19
7063:.
7026:.
6996:,
6990:MR
6988:,
6978:,
6966:,
6938:.
6901:.
6885:;
6857:.
6797:.
6795:16
6723:^
6617:,
6284:Pr
6203:.
5971:,
5960:ij
5782:.
5677:.
4762:Pr
4709:Pr
4631:Pr
4576:Pr
4565:.
4542:+1
4514:jj
4499:ji
4337:ij
4166:Pr
4054:Pr
3991:Pr
3956:.
3726::
3595:1.
3500:Pr
3421:Pr
3273:.
3077:12
3068:10
2910:Pr
2639:0.
2545:Pr
2531:ij
2435:Pr
2361:Pr
2304:Pr
2134:,
2049:Pr
1960:Pr
1863:Pr
1780:Pr
1355:Pr
1202:Pr
1096:Pr
1043:Pr
1020:.
931:Pr
836:Pr
780:Pr
688:Pr
630:0.
563:Pr
482:Pr
364:Pr
256:.
217:.
195:10
7120:.
7083:.
7071::
7036:.
7022::
6974::
6911:.
6871:.
6835:.
6807:.
6776:.
6710:.
6692:n
6668:j
6664:M
6660:1
6650:)
6647:n
6644:(
6639:j
6636:,
6633:i
6629:p
6615:j
6611:i
6581:.
6578:A
6572:i
6562:1
6559:=
6554:A
6549:j
6545:k
6539:j
6536:i
6532:q
6526:S
6520:j
6505:A
6499:i
6489:0
6486:=
6481:A
6476:i
6472:k
6454:A
6450:i
6430:A
6425:i
6421:k
6410:k
6406:S
6402:A
6352:n
6348:j
6331:)
6328:i
6325:=
6320:n
6316:X
6309:j
6306:=
6301:1
6298:+
6295:n
6291:X
6287:(
6278:i
6268:S
6262:i
6254:=
6249:j
6201:r
6185:)
6182:r
6179:+
6176:n
6173:k
6170:(
6165:i
6162:i
6158:p
6146:n
6119:)
6116:n
6113:(
6108:i
6105:i
6101:p
6089:n
6074:k
6070:i
6054:.
6046:j
6042:M
6036:j
6033:i
6029:f
6022:C
6019:=
6014:)
6011:n
6008:(
6003:j
6000:i
5996:p
5984:n
5969:i
5965:j
5958:f
5954:i
5935:j
5931:M
5927:C
5921:=
5916:)
5913:n
5910:(
5905:j
5902:j
5898:p
5886:n
5871:j
5855:i
5828:i
5801:i
5797:C
5780:i
5766:)
5761:i
5757:T
5753:(
5749:E
5745:=
5740:i
5736:M
5711:i
5707:M
5703:1
5698:=
5693:i
5664:N
5657:n
5634:=
5629:n
5625:X
5601:=
5596:0
5592:X
5571:)
5567:N
5560:n
5557:,
5552:n
5548:X
5544:(
5521:=
5516:n
5512:P
5496:.
5482:j
5474:=
5469:j
5466:i
5462:p
5456:i
5445:S
5438:i
5430::
5426:S
5419:j
5390:=
5387:P
5364:P
5308:)
5302:2
5299:1
5294:,
5289:4
5286:1
5281:,
5276:4
5273:1
5267:(
5263:=
5229:)
5223:3
5220:1
5215:,
5210:3
5207:1
5202:,
5197:3
5194:1
5188:(
5184:=
5137:P
5116:.
5112:|
5107:|
5099:|
5094:|
5073:P
5027:P
4980:n
4974:n
4969:R
4946:|
4941:|
4933:|
4928:|
4905:n
4899:n
4894:R
4886:P
4867:Ď€
4861:Ď€
4855:Ď€
4849:Ď€
4834:n
4830:n
4813:.
4809:)
4806:j
4803:=
4798:n
4794:X
4790:,
4787:i
4784:=
4779:1
4776:+
4773:n
4769:X
4765:(
4759:=
4756:)
4753:j
4750:=
4745:1
4742:+
4739:n
4735:X
4731:,
4728:i
4725:=
4720:n
4716:X
4712:(
4686:n
4664:i
4656:=
4653:)
4650:i
4647:=
4642:n
4638:X
4634:(
4609:i
4601:=
4598:)
4595:i
4592:=
4587:0
4583:X
4579:(
4563:n
4559:i
4554:n
4550:X
4546:j
4540:n
4536:X
4531:Ď€
4526:n
4522:n
4512:p
4508:j
4504:i
4497:p
4493:j
4476:,
4470:j
4462:=
4457:i
4454:j
4450:p
4444:i
4434:j
4426:=
4421:i
4418:j
4414:p
4408:j
4398:i
4390:=
4385:j
4382:i
4378:p
4372:i
4362:i
4343:Ď€
4335:p
4331:j
4326:i
4322:Ď€
4318:i
4314:n
4310:n
4293:.
4287:i
4284:j
4280:p
4274:j
4266:=
4261:j
4258:i
4254:p
4248:i
4217:,
4213:)
4210:i
4207:=
4202:n
4198:X
4191:j
4188:=
4183:1
4180:+
4177:n
4173:X
4169:(
4163:=
4158:j
4155:i
4151:p
4137:n
4126:j
4122:i
4118:n
4101:)
4098:j
4095:=
4090:n
4086:X
4079:i
4076:=
4071:1
4068:+
4065:n
4061:X
4057:(
4049:j
4041:=
4038:)
4035:i
4032:=
4027:n
4023:X
4016:j
4013:=
4008:1
4005:+
4002:n
3998:X
3994:(
3986:i
3967:Ď€
3937:.
3934:j
3928:i
3920:0
3917:=
3912:j
3909:i
3905:p
3896:1
3893:=
3888:i
3885:i
3881:p
3867:i
3863:i
3851:i
3846:i
3844:M
3840:i
3823:.
3818:)
3815:n
3812:(
3807:i
3804:i
3800:f
3793:n
3783:1
3780:=
3777:n
3769:=
3766:]
3761:i
3757:T
3753:[
3750:E
3747:=
3742:i
3738:M
3723:i
3721:M
3717:i
3691:.
3685:=
3680:)
3677:n
3674:(
3669:i
3666:i
3662:p
3651:0
3648:=
3645:n
3627:i
3619:i
3612:i
3587:)
3584:n
3581:(
3576:i
3573:i
3569:f
3558:1
3555:=
3552:n
3544:=
3541:)
3538:i
3535:=
3530:0
3526:X
3511:i
3507:T
3503:(
3487:i
3483:n
3479:i
3462:)
3459:i
3456:=
3451:0
3447:X
3440:n
3437:=
3432:i
3428:T
3424:(
3418:=
3413:)
3410:n
3407:(
3402:i
3399:i
3395:f
3368:.
3365:}
3362:i
3359:=
3354:n
3350:X
3346::
3343:1
3337:n
3334:{
3328:=
3323:i
3319:T
3305:i
3300:i
3298:T
3291:i
3287:i
3283:i
3261:k
3241:k
3221:k
3201:1
3195:k
3175:1
3172:=
3169:k
3146:2
3126:2
3106:k
3086:}
3080:,
3071:,
3062:,
3059:8
3053:,
3050:6
3047:{
3027:k
3007:k
2960:}
2957:0
2951:)
2948:i
2945:=
2940:0
2936:X
2929:i
2926:=
2921:n
2917:X
2913:(
2907::
2904:0
2898:n
2895:{
2889:=
2886:k
2863:i
2839:k
2819:i
2799:k
2779:i
2758:i
2754:i
2750:j
2746:j
2742:i
2738:j
2734:i
2723:i
2719:j
2715:j
2711:C
2707:i
2692:C
2688:C
2684:i
2680:j
2676:j
2672:i
2668:j
2664:i
2660:j
2656:i
2631:)
2626:j
2623:i
2619:n
2615:(
2610:j
2607:i
2603:p
2599:=
2596:)
2593:i
2590:=
2585:0
2581:X
2574:j
2571:=
2564:j
2561:i
2557:n
2552:X
2548:(
2529:n
2525:i
2521:j
2517:j
2513:i
2509:j
2505:i
2501:i
2497:j
2477:n
2460:.
2457:)
2454:r
2451:=
2446:0
2442:X
2438:(
2430:)
2427:n
2424:(
2419:j
2416:r
2412:p
2406:S
2400:r
2392:=
2389:)
2386:r
2383:=
2378:1
2372:n
2368:X
2364:(
2356:j
2353:r
2349:p
2343:S
2337:r
2329:=
2326:)
2323:j
2320:=
2315:n
2311:X
2307:(
2291:x
2287:0
2284:X
2280:n
2276:x
2271:n
2267:X
2256:S
2237:)
2234:k
2228:n
2225:(
2220:j
2217:r
2213:p
2207:)
2204:k
2201:(
2196:r
2193:i
2189:p
2183:S
2177:r
2169:=
2164:)
2161:n
2158:(
2153:j
2150:i
2146:p
2132:n
2128:k
2124:k
2116:n
2099:.
2096:)
2093:i
2090:=
2085:k
2081:X
2074:j
2071:=
2066:1
2063:+
2060:k
2056:X
2052:(
2046:=
2041:j
2038:i
2034:p
2007:)
2004:i
2001:=
1996:k
1992:X
1985:j
1982:=
1977:n
1974:+
1971:k
1967:X
1963:(
1957:=
1952:)
1949:n
1946:(
1941:j
1938:i
1934:p
1907:.
1904:)
1901:i
1898:=
1893:0
1889:X
1882:j
1879:=
1874:1
1870:X
1866:(
1860:=
1855:j
1852:i
1848:p
1821:)
1818:i
1815:=
1810:0
1806:X
1799:j
1796:=
1791:n
1787:X
1783:(
1777:=
1772:)
1769:n
1766:(
1761:j
1758:i
1754:p
1740:n
1736:j
1732:i
1724:n
1718:.
1705:)
1699:1
1696:+
1693:m
1687:n
1683:X
1679:,
1673:,
1668:1
1662:n
1658:X
1654:,
1649:n
1645:X
1640:(
1636:=
1631:n
1627:Y
1616:X
1612:m
1598:)
1593:n
1589:X
1585:(
1565:)
1560:n
1556:Y
1552:(
1542:m
1518:m
1512:n
1504:)
1499:m
1493:n
1489:x
1485:=
1480:m
1474:n
1470:X
1466:,
1460:,
1455:2
1449:n
1445:x
1441:=
1436:2
1430:n
1426:X
1422:,
1417:1
1411:n
1407:x
1403:=
1398:1
1392:n
1388:X
1379:n
1375:x
1371:=
1366:n
1362:X
1358:(
1346:=
1339:)
1334:1
1330:x
1326:=
1321:1
1317:X
1313:,
1307:,
1302:2
1296:n
1292:x
1288:=
1283:2
1277:n
1273:X
1269:,
1264:1
1258:n
1254:x
1250:=
1245:1
1239:n
1235:X
1226:n
1222:x
1218:=
1213:n
1209:X
1205:(
1183:m
1176:)
1174:m
1167:.
1165:n
1161:n
1143:)
1140:y
1137:=
1132:1
1126:n
1122:X
1115:x
1112:=
1107:n
1103:X
1099:(
1093:=
1090:)
1087:y
1084:=
1079:n
1075:X
1068:x
1065:=
1060:1
1057:+
1054:n
1050:X
1046:(
1004:]
1001:P
998:[
978:]
975:y
972:=
967:1
963:x
959:[
956:=
953:)
950:y
947:=
942:1
938:X
934:(
909:1
905:x
884:)
879:1
875:x
871:=
866:1
862:X
855:x
852:=
847:n
843:X
839:(
812:.
809:)
804:1
800:x
796:=
791:1
787:X
783:(
767:n
763:n
759:n
745:.
742:)
737:n
733:x
729:=
724:n
720:X
713:x
710:=
705:1
702:+
699:n
695:X
691:(
678:n
674:n
670:n
659:S
651:i
647:X
624:)
619:n
615:x
611:=
606:n
602:X
598:,
592:,
587:1
583:x
579:=
574:1
570:X
566:(
539:,
536:)
531:n
527:x
523:=
518:n
514:X
507:x
504:=
499:1
496:+
493:n
489:X
485:(
479:=
476:)
471:n
467:x
463:=
458:n
454:X
450:,
444:,
439:2
435:x
431:=
426:2
422:X
418:,
413:1
409:x
405:=
400:1
396:X
389:x
386:=
381:1
378:+
375:n
371:X
367:(
337:.
334:.
331:.
328:,
323:2
319:X
315:,
310:1
306:X
302:,
297:0
293:X
265:n
250:A
246:E
242:E
238:A
234:A
230:A
226:E
222:A
191:X
168:0
164:X
143:.
140:.
137:.
134:,
129:2
125:X
121:,
116:1
112:X
108:,
103:0
99:X
88:E
84:A
80:E
76:A
72:E
68:A
64:E
60:A
50:(
38:.
36:E
32:A
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
