A 4-dimensional Markov chain

Question

Consider a 4-dimensional Markov chain with states $(a,b,c,d) \in \mathbb{N}^4$.

The transition rule is the following: \begin{align}(a,b,c,d) \rightarrow \begin{cases} (a+1,b,c,d) \;\;\;\; \text{ with probability }p_x &\text{ if }ad>bc\\ (a,b,c+1,d) \;\;\;\; \text{ with probability }1-p_x &\text{ if }ad>bc\\ (a,b+1,c,d) \;\;\;\; \text{ with probability }p_y &\text{ if }ad\leq bc\\ (a,b,c,d+1) \;\;\;\; \text{ with probability }1-p_y &\text{ if }ad\leq bc\\ \end{cases} \end{align}

Denote $P_t$ the probability distribution at time $t$, and assume $P_0(a,b,c,d) = \delta(1,1,1,1)$, i.e. the initial state is $(1,1,1,1)$ with probability 1.

I'm trying to describe $P_t$ but am having some trouble.

What i've done: I was thinking to define a recursive relation (denoting $(a-1)$ instead of $(a-1,b,c,d)$ for simplicity):

$$P_t(a,b,c,d) = P_{t-1}(ad>bc)\big[p_x P_{t-1}(a-1) + (1-p_x)P_{t-1}(c-1)\big] + P_{t-1}(ad\leq bc) \big[p_y P_{t-1}(b-1) + (1-p_y)P_{t-1}(d-1)\big]$$ but am not sure how to compute $P_t(ad>bc)$.

$f(a,b,c,d) = ad-bc$ seems to me like a Lyapunov function, and I know vaguely that Lyapunov functions are used to determine whether states are transient/recurrent. Is this useful here?

Ultimately, my goal is to describe the usual quantities of interest (stationary states, distribution of hitting times, etc.) for this process. So if $P_t$ isn't the way to go, I'm happy to use other methods.

Answer 1

This is by no means a complete answer. If anything, it may be empirical evidence that this is a hard problem.

I've been trying to get some computational results for the problem of determining the probability that some state $(a,b,c,d)$ is ever reached. If this step is reached, the first coordinate was increased $a-1$ times, the second $b-1$ times, and so on, so each path to the state has the same probability, and the problem is reduced to the problem of counting the paths.

Now to get to $(a,b,c,d)$ the last step may have increased the first coordinated, and we came from state $(a-1,b,c,d)$. Since we increased the first coordinate, it must be the case that $$(a-1)d-bc>0\iff ad-bc>d$$ The last step may have increased the second coordinate, so we came from $(a,b-1,c,d)$ and $$ad-(b-1)c\leq0\iff ad-bc<-c$$ If the last step increased the third coordinate, we came from $(a,b,c-1,d)$ and $$ad-b(c-1)>0\iff ab-cd>-b$$ If the last step increased the fourth coordinate, we came from $(a,b,c,d-1)$ and $$a(d-1)-bc>0\iff ab-cd\leq a$$

I wrote a little python script to do compute the number of paths:

from functools import lru_cache

@lru_cache 
def paths(a,b,c,d):
    if min(a,b,c,d)==0:
        return 0
    if (a,b,c,d) == (1,1,1,1):
        return 1
    answer = 0
    D = a*d-b*c
    if D > d:
        answer += paths(a-1,b,c,d)
    if D <= -c:
        answer += paths(a,b-1,c,d)
    if  D > -b:
        answer += paths(a,b,c-1,d)
    if D <= a:
        answer += paths(a,b,c,d-1)
    return answer
 
for a in range(1,5):
    for b in range(1,5):
        for c in range(1,5):
            for d in range(1,5):
                p = paths(a,b,c,d)
                if p > 0:
                    print(f'({a},{b},{c},{d}): {p} path{"s" if p>1 else ""}')

The output is listed at the end of this answer. There seems to be a complete lack of symmetry. For example, there are $10$ paths to $(4,3,4,4)$, but only $4$ paths to $(3,4,4,4)$ and no paths at all to either $(4,4,3,4)$ or $(4,4,4,3)$. At time $t$ there are $2^t$ paths that can have been followed, and since the sum of the coordinates is $t+4$, there are only $\binom{t+3}3$ states that the chain can be in. We might expect that for large $t$ a substantial fraction for such states have a positive probability of being visited, but I have no idea how to attack even this question.

(1,1,1,1): 1 path
(1,1,1,2): 1 path
(1,1,2,2): 1 path
(1,1,2,3): 1 path
(1,1,3,3): 1 path
(1,1,3,4): 1 path
(1,1,4,4): 1 path
(1,2,1,1): 1 path
(1,2,1,2): 1 path
(1,2,1,3): 1 path
(1,2,2,2): 1 path
(1,2,2,3): 2 paths
(1,2,2,4): 2 paths
(1,2,3,3): 1 path
(1,2,3,4): 1 path
(1,2,4,4): 1 path
(1,3,1,1): 1 path
(1,3,1,2): 2 paths
(1,3,1,3): 2 paths
(1,3,1,4): 2 paths
(1,3,2,2): 1 path
(1,3,2,3): 3 paths
(1,3,2,4): 7 paths
(1,3,3,3): 1 path
(1,3,3,4): 2 paths
(1,3,4,4): 1 path
(1,4,1,1): 1 path
(1,4,1,2): 3 paths
(1,4,1,3): 5 paths
(1,4,1,4): 5 paths
(1,4,2,2): 1 path
(1,4,2,3): 4 paths
(1,4,2,4): 11 paths
(1,4,3,3): 1 path
(1,4,3,4): 3 paths
(1,4,4,4): 1 path
(2,1,1,2): 1 path
(2,1,2,2): 1 path
(2,1,2,3): 1 path
(2,1,3,2): 1 path
(2,1,3,3): 1 path
(2,1,3,4): 1 path
(2,1,4,2): 1 path
(2,1,4,3): 2 paths
(2,1,4,4): 1 path
(2,2,1,3): 1 path
(2,2,2,3): 1 path
(2,2,3,3): 1 path
(2,2,3,4): 1 path
(2,2,4,2): 1 path
(2,2,4,3): 1 path
(2,2,4,4): 2 paths
(2,3,1,4): 2 paths
(2,3,2,4): 2 paths
(2,3,3,3): 1 path
(2,3,3,4): 3 paths
(2,3,4,2): 1 path
(2,3,4,3): 2 paths
(2,3,4,4): 4 paths
(2,4,3,3): 1 path
(2,4,3,4): 4 paths
(2,4,4,2): 1 path
(2,4,4,3): 3 paths
(2,4,4,4): 7 paths
(3,1,1,2): 1 path
(3,1,2,2): 2 paths
(3,1,2,3): 1 path
(3,1,3,2): 3 paths
(3,1,3,3): 2 paths
(3,1,3,4): 1 path
(3,1,4,2): 3 paths
(3,1,4,3): 4 paths
(3,1,4,4): 2 paths
(3,2,1,3): 1 path
(3,2,2,3): 2 paths
(3,2,3,3): 2 paths
(3,2,3,4): 1 path
(3,2,4,3): 2 paths
(3,2,4,4): 1 path
(3,3,1,4): 2 paths
(3,3,2,4): 4 paths
(3,3,3,4): 4 paths
(3,3,4,4): 4 paths
(3,4,4,4): 4 paths
(4,1,1,2): 1 path
(4,1,2,2): 3 paths
(4,1,2,3): 1 path
(4,1,3,2): 6 paths
(4,1,3,3): 3 paths
(4,1,3,4): 1 path
(4,1,4,2): 9 paths
(4,1,4,3): 7 paths
(4,1,4,4): 3 paths
(4,2,1,3): 1 path
(4,2,2,3): 3 paths
(4,2,3,3): 5 paths
(4,2,3,4): 1 path
(4,2,4,3): 7 paths
(4,2,4,4): 2 paths
(4,3,1,4): 2 paths
(4,3,2,4): 6 paths
(4,3,3,4): 10 paths
(4,3,4,4): 10 paths

Answer 2

Q) What are the recurrent states?

Once you leave a state, you can't get back to it. Therefore the states don't communicate. Therefore no state is recurrent, ie all states are transient.

Q) What are the stationary states?

The states are all transient implying no stationary states.

Q) What is the hitting time of a state given by $\{a,b,c,d\}$?

Starting at $\{0,0,0,0\}$, we can move only right or up. Therefore the process only hits parts of the $\mathbb N^4$ grid. Most states are not hit. Therefore can we describe a finite hitting time?