I am working on Markov Chain for a computer science project. The problem is based on the gunshot in "The Good The Bad and the Ugly". Three shooters have a certain chance to hit their target and a certain chance to choose one of the other two shooters. So the Good has a chance g to hit his target, The Bad has a chance b and The Ugly a chance u.
I want to show that each shooter should target the best gunslinger when they shoot to maximize their likelihood to survive. For this I introduce gu, the probability for G to choose U, bu the probability for B to choose U and ub the probability for U to choose B.
I've built my Markov chain, I implemented my transition matrix, identified the fundamental matrix F and the Absorbtion matrix A. So I just have to look at the first column of A to know that to go from the initial state (GBU everyone is alive and G starts shooting) to the absorbing states G,B,U I have a probability of respectively A11, A21 and A31.
So my question is, how can I find a way to maximize those last three probabilities. I've considered setting g, b and u and find optimal values of gu, bu and ub but I don't see how I could do that. Should I consider A as a function of gu, bu and ub and find the critical points such that ∇A=0 ? But considering that A is a very long expression it seems very unpractical.
https://i.stack.imgur.com/TXR6f.jpg (The Markov chain and the transition matrix).
Thanks in advance for your help.
Small update: the question accepted answered in a mathematical point of view to the question, however I am still looking for an approach using Markov chain and the absorbing matrix! So feel free to comment!
I'll do this from the point of view of $G$, but it's easy to see that the same analysis applies to the other two.
The crux is that $G$'s strategy only comes into play in the state GBU, where it only influences the probability of entering state BG or UG depending on if $G$ aims at $U$ or $B$ respectively.
Intuitively, $G$ would prefer to end up in a one-on-one duel with whichever of $U$ and $G$ is worse as shooting, so $G$ should always shoot at the better shot.
To show this formally, we compute the probability of $B$ surviving from state BG. This happens if $B$ misses; then either $G$ kills $B$ or $G$ misses and we're back in state BG. Setting up the relevant equations: \begin{align*} \Pr(G\text{ survives} | BG) &= \Pr(BG \rightarrow GB \rightarrow G) + \Pr(BG \rightarrow GB \rightarrow BG)\Pr(G\text{ survives} | BG) \\ &= (1-b)g + (1-b)(1-g) \Pr(G\text{ survives} | BG), \\ \Pr(G\text{ survives} | BG) &= \frac{(1-b)g}{1 - (1 - b)(1 - g)} \\ &= \frac{g}{(1-b)^{-1} - (1-g)}, \end{align*} which is decreasing in $b$.
Similarly, the probability of $G$ surviving from state UG is \begin{align*} \Pr(G\text{ survives} | UG) = \frac{g}{(1-u)^{-1} - (1-g)}. \end{align*}
You can verify from this that when $b > u$, we have that $\Pr(G\text{ survives} | BG) < \Pr(G\text{ survives} | UG)$ and vice versa if $b < u$. Therefore, $G$'s probability of survival are maximised by aiming at the better shot.
This analysis assumes that $G$ must shoot at either $B$ or $U$. Somewhat famously, if $G$ is allowed to shoot into the air, they might prefer to do so if they are the worst shot.
This is because the state BUG may preferable to UG or BG for $G$. If $G$ is worst, while there are $3$ remaining people, $U$ and $B$ will prefer to shoot at each other, and when one of the hits, they system will enter state GU or GB depending on who hits, which $G$ prefers to UG or BG respectively since it's $G$'s turn to shoot.