Discrete-time queue with random service time The following is an exercise in Karlin and Pinsky's An Introduction to Stochastic Modeling:



Here is my question: 
This problem seems to assume that the Markov Chain is time-homogeneous. But I cannot make sense of it. Let $(X_n)$ be the Markov chain in the model. How would one expect that the following is true?
$$
P(X_4=0\mid X_3=1)=P(X_2=0\mid X_1=1)
$$

[Added:] To make my question clearer, all I concern now are 


*

*(1)how to calculate this particular transition probability


$$P(X_4=0|X_3=1)$$


*

*(2) why is
$$
P(X_4=0\mid X_3=1)=P(X_2=0\mid X_1=1)
$$
true. 


For (1), denote $A$ as the event that "no customer arrive in a period" 
and $B$ as the event that "a taxi comes at the 4th period" (namely "service for the people at the 3rd period is done at the 4th period"). By independence of $A$ and $B$, one has
$$
P(X_4=0|X_3=1)=P(AB|X_3=1)=P(A|X_3=1)P(B|X_3=1)=P(A)P(B|X_3=1)    \tag{*}
$$
where the last equality is given by the independence of the events $A$ and $X_3=1$. Now $P(A)=1-\beta$ is given. One needs $P(B|X_3=1)$ in order to calculate ($*$). What I was really worrying about is the question — "when did this people get on the bus?" — which should determine the "service time" $Z$. More generally, how should one expect that $P(B|X_n=1)$ is independent of $n$, in the case of which one might have
$$
P(B|X_n=1)=P(Z=1)?
$$ 
 A: I'm not sure I understand your problem. In the Markov process the queue length increases by $1$ with probability $\beta$ at each step. If the queue length isn't $0$ then it decreases as specified with $\alpha$. That should be sufficient information to write the matrix.
For example, 
$$
P(X_4 = 0 | P(X_3 = 1) = \alpha  (1-\beta)
$$
since this state transition can happen just one way: no customer arrives and the one there departs.
That happens to be the same computation as $P(X_2 = 0 | P(X_1 = 1)$, not because of the previous history (which can't matter in a Markov process) but because it's the only way to empty the queue when there's just one customer.
In general, the queue increases by $1$ with probability $\beta$ independent of its current value, but the decrease is proportional to the number present, since each customer gets independent service.
Time isn't continuous; it's measured in discrete time periods. (You know that.)
I haven't addressed your expression using explicit conditional probabilities because that's not how I think. I'm sure it's possible to frame the argument that way too.
