Cat chasing mouse on a straight line coin toss I recently got keen on "brainteasers" and now I am trying to solve and code my daily one.
A cat is chasing a mouse in a 1-D space, for example, a tunnel. The mouse is Y meters away from its hole and the cat is further X meters behind the mouse. 
In every turn, with an equal probability of 1/3, the mouse moves 1 meter forward to it's hole OR the cat moves 2 meters forward OR both of them move +1 meter forward. 


*

*What is the probability of the mouse getting to its hole or not? 


*

*What I am trying is to approach by an absorbing Markov chain but I am a bit confused how exactly to formulate it and generalize it in the case of an  asymmetric dice toss each turn to determine who moves and by how far? 

*Could you please recommend any interesting graph theory basics directly applicable to the problem? 
 A: An absorbing Markov chain approach is reasonable, but I don't think you can do it by reformulating a question about a single asymmetric die, because this is a genuinely two-dimensional problem. Both the cat's and mouse's position are relevant, and it doesn't suffice to just look at the difference.
Let's make this a bit more concrete: suppose $Y = 5, X = 10$ for the sake of example. One way to set this up would be to have your Markov chain would to encode both the positions of the mouse and the cat. Specifically, your state space might look like ordered pairs of positions; for the example I outlined above, the starting position of the chain would be $(5, 15)$ (since the mouse is 5 meters from the hole and the cat is an additional 10 meters beyond that) which will move to any of three states with equal probability: $(4, 15)$, $(5, 13)$, or $(4, 14)$.
Note that your state space will need to be somewhat large (order of magnitude: $(X+Y)^2/2$) to do this. The absorbing states would be of the form $(0, x)$ (the mouse reaches the hole) or $(x, x)$ (the cat catches the mouse) or $(x, x-1)$ (the cat overshoots the mouse, which presumably means it's smart enough to stop and eat the mouse). 
I'm not sure that I have a good recommendation for graph theory basics applicable to this problem; perhaps someone else can fulfill that part of your question better than I can. However, if you haven't seen it yet, I highly recommend Random Walks on Electrical Networks by Doyle and Snell for finite Markov chain questions.
I should also note that if you're hoping to get a solution as an function of the unknowns $X$ and $Y$, I think that will be quite hard and I'm not sure how helpful my answer will be in getting there. However, for a particular $X$ and $Y$, this method should lead you to a correct answer.
