# Random Early Discard Markov Chain

I'm trying to sketch the Markov chain for a Random Early Discard queueing policy where customers arrive to the queue of infinite size according to a Poisson process with rate $\lambda$. Customers that arrive are entered into the queue with probability $\alpha_{n} = \frac{1}{n+1}$ and are blocked from the queue with rate $1-\alpha_{n}$. The service time is exponentially distributed with mean $\frac{1}{\mu}$.

I think the jumps from state 0 -> 1 -> 2 -> ... -> n -> n+1 should be $\alpha_{n}\lambda$ and arrows going to the same state, say 0 to 0, should be $(1-\alpha_{n})\lambda$, and arrows going successively backward between states would be $\mu$. Is this correct or am I misunderstanding how this works? I learned some introductory stuff about Markov chains in probability, but the arrows were always labeled as probabilities that added to 1 instead of rates of arrivals per second.

Your thoughts are correct, although the notion of $n \to n$ transition rate is superfluous for the continuous time Markov process. One could think of a discrete time-step Markov chain, in which case the "arrows" probabilities do need to add to $1$, but for this continuous-time model, the concept of probability rates is the applicable one.
One thing to point out: Since the rates depend on the size of the queue, your usual queueing theory results do not hold. In particular, for $\lambda > \mu$ an ordinary queue ($\forall n : \alpha_n = 1$) almost surely grows to infinity; but for your example $\alpha_n$ the queue will not grow indefinitely; its asymptotic distribution for large $t$ is largest near $$\frac{1}{n+1}\lambda = \mu \implies n = \frac{\lambda}{\mu}-1$$ The actual asymptotic distribution is interesting and non-trivial.
• Some authors have $n=0$ as the lowest state, in which case you need to do all the ins and outs from state $1$ (but not from state $0$. Some have $n=1$ as the lowest state, in which case, you only need the ins and outs to state $2$. – Mark Fischler Feb 22 '16 at 1:05
• @Larry The rate going into and coming out of a set of states is equal. One author probably takes the set $\{i\}$ and then computes all the rates going into the state (from $i - 1$ and from $i + 1$) and out of that state (from $i$ to all other states). On the other hand, if you take the set of states to be $\{0,1,\ldots,i\}$, then the rate going into that set of states is only from state $i + 1$ and the rate of leaving that set of states is from $i$ to $i + 1$. – Ritz Feb 26 '16 at 8:15