({{, (RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution])[mproc,f]
represents the distribution of times for the Markov process mproc to pass from the initial state to final states f for the first time. }})

OpenersNotesSection(Spacer1)Details

(RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) is also known as first hitting time.

The Markov process mproc can be a (RefLink[DiscreteMarkovProcess, paclet:ref/DiscreteMarkovProcess]) or (RefLink[ContinuousMarkovProcess, paclet:ref/ContinuousMarkovProcess]).

The probability for time t in a (RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) is equivalent to (RefLink[Probability, paclet:ref/Probability])[x[t]∈f∧(Subscript[∀, τ,0<τ<t])x[τ]∉f\[Conditioned]x[0]==i,x\[Distributed]mproc], where i is the initial state.

If mproc is already in the target state, (RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) gives a distribution for the mean recurrence time.

If the chain is absorbing and the target states are non-absorbing, (RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) gives a distribution conditional on reaching the target states.

(RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) represents a discrete phase-type distribution for discrete-time Markov processes and a continuous phase-type distribution for continuous-time Markov processes.

(RefLink[FirstPassageTimeDistribution, paclet:ref/FirstPassageTimeDistribution]) can be used with such functions as (RefLink[Mean, paclet:ref/Mean]), (RefLink[Quantile, paclet:ref/Quantile]), (RefLink[PDF, paclet:ref/PDF]), and (RefLink[RandomVariate, paclet:ref/RandomVariate]).

OpenersPrimaryExamplesSection(Spacer1)Examples  (16)

OpenersExampleSection0(Spacer1)Basic Examples  (1)

Compute the mean, variance, and PDF for the number of steps needed to go to state 3:

𝒫=DiscreteMarkovProcess[{1,0,0},(({{0, 1/2, 1/2}, {1/2, 0, 1/2}, {1/2, 1/2, 0}}))];

𝒟=FirstPassageTimeDistribution[𝒫,3];

Probability density function:

PDF[𝒟,k]

DiscretePlot[%,{k,0,5},ExtentSize->1/2]

Cumulative distribution function:

CDF[𝒟,k]

DiscretePlot[%,{k,0,5},ExtentSize->Right]

Mean time to first passage and variance:

Mean[𝒟]

Variance[𝒟]

OpenersExampleSection1(Spacer1)Scope  (3)

First passage time distribution for a continuous Markov process:

𝒫=ContinuousMarkovProcess[1,{{-2,1,1,0},{2,-6,2,2},{3,3,-9,3},{0,0,0,0}}];

𝒟=FirstPassageTimeDistribution[𝒫,4];

Probability density function:

PDF[𝒟,t]

Plot[PDF[𝒟,t],{t,0,10}]

Mean of the distribution:

Mean[𝒟]

N[%]

Compare with the result from simulation:

paths=Select[RandomFunction[𝒫,{0,10^5},4*10^4]["Paths"],#[[-1,1]]==10^5&];

Mean[paths[[All,-2,1]]]

Characteristic function:

CharacteristicFunction[𝒟,s]//Together

Compute the probability of an event:

Probability[time<1,time\[Distributed]𝒟]

N[%]

Find the mean and the variance of the first passage time through target states, conditional on reaching them:

𝒫=DiscreteMarkovProcess[3,{{1/2,1/2,0,0},{1/2,1/2,0,0},{1/3,1/4,13/60,1/5},{0,0,0,1}}];

MarkovProcessProperties[𝒫,"Absorbing"]

𝒟=FirstPassageTimeDistribution[𝒫,{1,2}];

{Mean[𝒟],Variance[𝒟]}//N

Compare against a process simulation:

sample=RandomFunction[𝒫,{0,128},10^5,Method->{Automatic,"StoppingFunction"->Function[{len,pos},pos==3]}];
times=Cases[sample["Paths"],{__,{t_,1|2}}:>t];

{Mean[times],Variance[times]}//N

Generate a set of pseudorandom numbers from the distribution:

dist=FirstPassageTimeDistribution[ContinuousMarkovProcess[{0.1,0.9,0,0},{{-6.2,2,0,4.2},{2,-9,1,6},{1,0,-3,2},{0,0,0,0}}],4];

data=RandomVariate[dist,10^4];

Compare its histogram to the PDF:

hist=Histogram[data,Automatic,"PDF"];

pdf=Plot[PDF[dist,x],{x,0,10},PlotRange->All,PlotStyle->Thick];

Show[hist,pdf,ImageSize->Medium]

OpenersExampleSection3(Spacer1)Applications  (7)

A taxi is located either at the airport or in the city. From the city, the next trip is to the airport with probability 1/4, or to somewhere else in the city with probability 3/4. From the airport, the next trip is always to the city. Model the taxi, using a discrete Markov process, with state 1 representing the city and state 2 representing the airport, starting at the airport:

taxi=DiscreteMarkovProcess[2,{{3/4,1/4},{1,0}}];

Find the expected number of trips until the taxi's next visit to the airport:

Mean[FirstPassageTimeDistribution[taxi,2]]

A gambler, starting with 3 units, places a 1-unit bet at each step, with a winning probability of 0.4 and a goal of winning 7 units before stopping. Find the expected playing time until the gambler achieves his goal or goes broke. The gambling process can be modeled as a discrete Markov process, where state i represents the gambler having i-1 units:

m=(({{1, 0, 0, 0, 0, 0, 0, 0}, {0.6, 0, 0.4, 0, 0, 0, 0, 0}, {0, 0.6, 0, 0.4, 0, 0, 0, 0}, {0, 0, 0.6, 0, 0.4, 0, 0, 0}, {0, 0, 0, 0.6, 0, 0.4, 0, 0}, {0, 0, 0, 0, 0.6, 0, 0.4, 0}, {0, 0, 0, 0, 0, 0.6, 0, 0.4}, {0, 0, 0, 0, 0, 0, 0, 1}}));

gambler=DiscreteMarkovProcess[4,m];

Simulate some typical gambling scenarios:

ListLinePlot[RandomFunction[gambler,{0,20},5]["ValueList"]-1]

The expected playing time:

𝒟=FirstPassageTimeDistribution[gambler,{1,8}];

Mean[𝒟]

The full distribution for playing time:

DiscretePlot[PDF[𝒟,k],{k,0,15},ExtentSize->1/2]

The probability that playing time is 10 or less:

NProbability[k≤10,k\[Distributed]𝒟]

Find how many times, on average, you have to roll a die until you have seen all six faces:

dierolls=DiscreteMarkovProcess[1,With[{numfaces=6},SparseArray[{{i_,i_}->(i-1)/numfaces,{i_,j_}/;(j-i-1==0)->(numfaces-(i-1))/numfaces},{numfaces+1,numfaces+1}]]];

Mean[FirstPassageTimeDistribution[dierolls,7]]//N

When flipping an unbiased coin, on average it takes longer for HHT to occur than for HTT:

proc=DiscreteMarkovProcess[1,{{1/2,1/2,0,0,0,0},{0,0,1/2,1/2,0,0},{0,0,1/2,0,1/2,0},{0,1/2,0,0,0,1/2},{0,0,0,0,1,0},{0,0,0,0,0,1}}];

Graph[{"Start","H","HH","HT","HHT","HTT"},proc,ImageSize->Medium]

Mean[FirstPassageTimeDistribution[proc,5]]//N

Mean[FirstPassageTimeDistribution[proc,6]]//N

A particle moves between the eight vertices of a cube by a symmetric random walk. Let i be the initial vertex and o be the opposite vertex. Compute:

• the expected number of steps until the particle returns to i

• the expected number of steps until the first visit to o

proc=DiscreteMarkovProcess[1,HypercubeGraph[3]];

Graph[proc]

Expected number of steps before returning to i, if starting at i:

Mean[FirstPassageTimeDistribution[proc,1]]

Expected number of steps until first visit to o, if starting at i:

Mean[FirstPassageTimeDistribution[proc,8]]

Use the mean hitting time to bound the expected cover time for an irreducible process:

sm=With[{n=7},AdjacencyMatrix[CompleteGraph[n]]/(n-1)];

irredproc=DiscreteMarkovProcess[i,sm];

MarkovProcessProperties[irredproc,"Irreducible"]

With[{numstates=Length[sm]},With[{maxhittingtime=Max[Outer[Mean[FirstPassageTimeDistribution[DiscreteMarkovProcess[#1,sm],#2]]&,Range[numstates],Range[numstates]]]},maxhittingtime≤(Subscript[t, cov])≤maxhittingtime*HarmonicNumber[numstates]]]

The Hubble space telescope carries six gyroscopes, with a minimum of three required for full accuracy. The operating times of the gyroscopes are independent and exponentially distributed with failure rate λ. If a fourth gyroscope fails, the telescope goes into sleep mode, in which further observations are suspended. It requires an exponential time with mean 1/μ to put the telescope into sleep mode, after which the base station on Earth receives a sleep signal and a shuttle mission is prepared. It takes an exponential time with mean 1/η before the repair crew arrives at the telescope and has repaired the stabilizing unit with the gyroscopes. In the meantime, the other two gyroscopes may fail. If the last gyroscope fails, the telescope will crash. Suppose λ==0.1, μ==100, and η==5, all with units of inverse years:

qm={{-6λ,6λ,0,0,0,0,0,0,0},{0,-5λ,5λ,0,0,0,0,0,0},{0,0,-4λ,4λ,0,0,0,0,0},{0,0,0,-3λ,3λ,0,0,0,0},{0,0,0,0,-2λ-μ,2λ,μ,0,0},{0,0,0,0,0,-λ-μ,0,μ,λ},{η,0,0,0,0,0,-2λ-η,2λ,0},{η,0,0,0,0,0,0,-λ-η,λ},{ν,0,0,0,0,0,0,0,-ν}};

With[{vert={"6","5","4","3","2","1","Sleep2","Sleep1","Crash"}},Graph[vert,ContinuousMarkovProcess[1,qm]/.{ν->0},VertexSize->{"Scaled", 0.08},VertexStyle->Thread[vert->{Green,Green,Green,Green,Orange,Orange,LightBlue,LightBlue,Red}],GraphLayout->{"SpringElectricalEmbedding","Rotation"->Pi},ImageSize->Medium]]

proc=ContinuousMarkovProcess[1,qm]/.{λ->1/10,μ->100,η->5};

Find the probability that the telescope will crash in the next 10 years:

CDF[FirstPassageTimeDistribution[proc,9],10]//N

Find the probability that sleep mode is not reached (no shuttle mission is required) in 10 years:

1-CDF[FirstPassageTimeDistribution[proc,{7,8}],10]/.ν->1.

OpenersExampleSection4(Spacer1)Properties & Relations  (4)

The average number of steps to go from state 1 to state 3 is 2:

proc=DiscreteMarkovProcess[1,{{0,1,0},{0,0,1},{1,0,0}}];

Graph[proc]

Mean[FirstPassageTimeDistribution[proc,3]]

Since the process is deterministic, the variance is zero:

Variance[FirstPassageTimeDistribution[proc,3]]

The mean and variance for a continuous process with acyclic bidiagonal transition rate matrix:

dist=FirstPassageTimeDistribution[ContinuousMarkovProcess[1,{{-λ1,λ1,0},{0,-λ2,λ2},{0,0,0}}],3];

Mean[dist]

Variance[dist]

When the target is one of the absorbing states, a conditional distribution is returned:

proc=DiscreteMarkovProcess[2,{{1, 0, 0,0}, {0.45, 0, 0.55,0}, {0, 0.2, 0,0.8},{0,0,0,1}}];

Graph[proc]

The assumption is that the process reaches the target state and does not get stuck in state 1:

Mean[FirstPassageTimeDistribution[proc,4]]

Autosimplification to (RefLink[ExponentialDistribution, paclet:ref/ExponentialDistribution]) or other phase-type distributions:

FirstPassageTimeDistribution[ContinuousMarkovProcess[1,{{-3,3},{0,0}}],2]

(RefLink[ErlangDistribution, paclet:ref/ErlangDistribution]):

qm=With[{k=3,la=5},Join[RotateRight[PadRight[{-la,la},k+1],#]&/@Range[0,k-1],{ConstantArray[0,k+1]}]]

FirstPassageTimeDistribution[ContinuousMarkovProcess[1,qm],4]

(RefLink[HyperexponentialDistribution, paclet:ref/HyperexponentialDistribution]):

qm=With[{muvec={7,4,5}},SparseArray[Flatten@MapThread[{{#1,#1}->-#2,{#1,Length[muvec]+1}->#2}&,{Range[Length[muvec]],muvec}],{Length[muvec]+1,Length[muvec]+1}]]

FirstPassageTimeDistribution[ContinuousMarkovProcess[{1/3,2/3,0,0},qm],4]

(RefLink[CoxianDistribution, paclet:ref/CoxianDistribution]):

qm=With[{alvec={2/3,1/3},muvec={5,1,3}},Join[Transpose[Join[Transpose[DiagonalMatrix[-muvec]+ArrayFlatten[{{0,DiagonalMatrix[alvec*Most[muvec]]},{{{0}},0}}]],{muvec PadRight[1-alvec,Length[muvec],1]}]],{ConstantArray[0,Length[muvec]+1]}]]

FirstPassageTimeDistribution[ContinuousMarkovProcess[1,qm],4]

OpenersExampleSection5(Spacer1)Possible Issues  (1)

Here, a closed form is not available for the moments of arbitrary order r:

𝒟=FirstPassageTimeDistribution[DiscreteMarkovProcess[1,{{0.3,0.7},{0.6,0.4}}],2];

Moment[𝒟,r]

Obtain a moment by specifying the value of r:

Moment[𝒟,2]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[DiscreteMarkovProcess, paclet:ref/DiscreteMarkovProcess])  ▪  (RefLink[ContinuousMarkovProcess, paclet:ref/ContinuousMarkovProcess])  ▪  (RefLink[ExponentialDistribution, paclet:ref/ExponentialDistribution])  ▪  (RefLink[ErlangDistribution, paclet:ref/ErlangDistribution])  ▪  (RefLink[GammaDistribution, paclet:ref/GammaDistribution])  ▪  (RefLink[CoxianDistribution, paclet:ref/CoxianDistribution])  ▪  (RefLink[HyperexponentialDistribution, paclet:ref/HyperexponentialDistribution])  ▪  (RefLink[HypoexponentialDistribution, paclet:ref/HypoexponentialDistribution])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Finite Markov Processes, paclet:guide/MarkovProcesses])}})}})