# Finite state machine with gamma distributed waiting times

I have a state machine with positive and negative inputs. The time between positive inputs follows a gamma distribution ($X_+ \sim \Gamma(k_+, \theta_+)$), and the time between negative inputs follows a different gamma distribution ($X_- \sim \Gamma(k_-, \theta_-)$). Hence, the probabilities of receiving $K$ positive and negative inputs over some interval of time are exactly known for all $K$. The state machine is shown below: The blue boxes represent achievable states in the machine, and the solid and dashed lines represent a positive and negative input, respectively. So for instance, if the machine is in state 3 and a positive input arrives, the machine yields a positive output and resets to state 2. If the machine then receives a negative input, it moves to state 1 without producing any output.

Is it possible to find the PMF for positive outputs? That is, what is the probability of getting $K$ positive outputs over the same interval of time for all $K$?

• The problem with presenting a toy version of your real problem is that you may not be abstracting it in the way that will be most helpful for you. (Nonstatisticians are often surprised about what details are statistically important.) So describe the real problem instead. – Kodiologist Apr 30 '18 at 15:49
• Thanks. I don't know much about this domain, but it looks like you could probably represent the system as a Markov chain. – Kodiologist Apr 30 '18 at 16:34
• I have been looking at continuous time Markov chains, and it doesn't look like my state machine satisfies the Markov property since the time spent in each state does not follow an exponential distribution. Am I dead in the water, or is there something else I could try? – mwoods May 1 '18 at 20:11
• (+1) Are all waiting times are independent of each other, ie, the positive inputs and negative inputs form two independent renewal processes? (This, if a negative input occurs at time $t$, the time to next negative input is independent of all previous occurrences of positive and negative inputs? and the state?) This is most likely intended since no dependence is specified (but needs to be assumed since the description as written does not guarantee this) – Juho Kokkala May 5 '18 at 6:18
• @JuhoKokkala, the answer is yes, they are independent of each other. If a negative input arrives at time t, the time to the next negative input does not depend on previous inputs or the current state. – mwoods May 5 '18 at 20:05

Note that this is NOT an attempt to fully answer the problem, but to show how to overcome the lack of the Markov property for a special case that may not apply - one that is far too long to put in comments.

Unfortunately, as you have realized, this is not a Markov process, but a semi-Markov process. If you a) have integer $k_+$ and $k_-$, and b) are willing to expand your state space, you can transform this to a Markov process using the fact that the Gamma distributions become Erlang distributions and the Erlang variates are a sum of i.i.d. Exponential variates with the same scale parameter as the original Erlang variate.

We can expand the state space to include two new variables, the "+ state" and "- state", which record "how far along" we are in generating the next positive or negative arrival. For concreteness, assume $k_+ = 5$; the next positive arrival occurs when the fifth of five consecutive Exponential arrivals has occurred, so the "+ state" records how many positive arrivals have occurred since the last positive input. The sequence of "+ state" values is $\{0, 1, 2, 3, 4, 0, 1, ...\}$; state $0$ can only transition to $0$ or $1$, state $4$ can only transition to $4$ or $0$, and so forth.

Your state space becomes $[\text{BoxID},+,-]$ recording which box the process is in, how many positive arrivals have occurred modulus $k_+$, and how many negative arrivals have occurred modulus $k_-$.

We now have two random variates - the time until the next "+ state" transition and the time until the next "- state" transition - both of which are Exponentially distributed. As the minimum of two independent Exponential variates is itself Exponential, the time until the next transition (of any type) is Exponential with rate equal to the sum of the two component rates ($\theta_+ + \theta_-$ or $1/\theta_+ + 1/\theta_-$ depending on how your Gamma distributions are parameterized). The probability that the next transition is a "+ state" transition is just $\theta_+/(\theta_+ + \theta_-)$, or $1/\theta_+ / (1/\theta_+ + 1/\theta_-)$, again depending on how your Gamma distributions are parameterized. Given that the time to the next transition now has an Exponential distribution, you have a CTMC (Continuous Time Markov Chain), which can be analyzed in standard ways.

For a concrete example, assume positive arrivals occur at a rate of $0.5/$unit of time and negative arrivals occur at the rate of $0.25/$unit of time. The time until the next transition is Exponential with a rate of $0.75/$unit of time and the probability that the transition is triggered by a positive arrival is $0.5/(0.5+0.25) = 2/3$.

Now you have a much-enlarged state space, with each box in your initial diagram having $k_+k_-$ states interior to it, but at least you have the Markov property and can find the steady-state probabilities of being in box 3 and the states with "+ state" = $k_+-1$, i.e., one of the states from which you can experience a transition that results in a positive output. Combining those steady state probabilities with the transition matrix and the mean time between transitions gives you the long run average rate of seeing a positive output. You can also calculate the desired probability distribution using the steady state probabilities, the transition matrix, and the fact that the time between transitions has an Exponential distribution with known rate.

• This is exactly what I needed. I have very large $k_+$ and $k_-$ (on the order of ten thousand), so the transition matrix will be quite large. The saving grace is that the matrix is also very sparse. Thank you very much! – mwoods May 14 '18 at 16:23
• Well with your shape parameters that large, the distinction between integer and non-integer values is moot! Yes, sparsity will indeed be your saving grace... – jbowman May 14 '18 at 16:31