# Computing the probability of reaching any leaf of an $n$-ary infinite probability tree

Suppose you have two players $X$ and $Y$ fighting, both of which have $n\in \mathbb{N}, n\geq1$ life.

Each player has a probability $p_i$ of doing $i$ damage for all $i\in[0, n]$. Note that $p_0$ is the probability of doing no damage, and all $p_i$ should sum to 1. $X$ and $Y$ both share probabilities, so all $p_i$ for $X$ equals $p_i$ for $Y$.

Now play the game as follows (each step is one turn):

1. Player $X$ attacks, and randomly deals $i$ damage to player $Y$ according to the distribution $p_i$. This means that $Y$ decreases their life by $i$.
2. Player $Y$ attacks, and randomly deals $i$ damage to player $X$ according to the distribution $p_i$. This means that $X$ decreases their life by $i$.

The game ends when a player's life is $\leq 0$.

Now a person watching this game would like for it to end after about $t\in \mathbb{N}, t\geq 1$ turns. In what ways can they assign the probabilities $p_i$ such that the expected number of turns is $t$?

Edit: To be clear I am looking for all possible $p_i$ such that the expected number of turns is $t$.

• Set $p_{n/t}=1$? I guess you want to rule that out... Sep 18 '15 at 5:33
• Another simple example is $p_n=1/t$ and $p_0=1-1/t$ (if by "turn" you mean a single attack - if "turn" means a pair of attacks one by each player, then you can adjust appropriately). Sep 18 '15 at 12:24
• So I'm looking for a description of the set of all possible $p_i$'s, not just one example. Sep 18 '15 at 12:32
• You're asking for the expected damage each turn to be $n/t$. This condition is $\sum_{i=0}^n i\cdot p_i = n/t$. That exactly characterizes distributions you want.
– usul
Sep 18 '15 at 13:41
• How is this unclear what I am asking? It is presented formally and has a precise answer. Sep 19 '15 at 4:56

Let $A(x,y)$ be the expected length of the game (counting each player's turn as $1$) if you start with the players having life points $x$ and $y$ respectively, the player with $x$ going next. Conditioning on the result of the first player's turn,

$$A(x,y) = 1 + \sum_{i < y} p_i A(y-i, x)$$

You're interested in $A(n,n)$, which this recursion will determine as a rather complicated rational function in the $p_i$. For example, I get

$$A({2,2})={\frac {{p_{{0}}}^{3}-{p_{{0}}}^{2}p_{{1}}-{p_{{0}}}^{2}+{p _{{1}}}^{2}-p_{{0}}+p_{{1}}+1}{ \left( p_{{0}}+1 \right) \left(1 - p_{{0 }} \right) ^{3}}}$$ while $A(3,3)$ is of the form $P(p_0, p_1, p_2)/((1+p_0)^3 (1-p_0)^5)$ where $P$ is a polynomial in $p_0, p_1, p_2$ of total degree $7$ with $39$ terms. The condition $A(n,n) = t$ then determines a surface in $(p_0, \ldots, p_{n-1})$ space.

EDIT: For example, here are the curves $A(2,2) = t$ in $(p_0,p_1)$ space for $t = 2$ to $10$ (from left to right). Note that in this case any damage $\ge 2$ is immediately lethal, and $\sum_{i \ge 2} p_i = 1 - p_0 - p_1$. For $A(2,2) = 1$ you'd need $p_0 = p_1 = 0$.

• So recursive probability is really cool, I didn't know you could do that. And yes, I was manually playing with A(2, 2) and the solutions weren't pretty and I was confused. This fully describes all of them though, thanks =) Sep 18 '15 at 18:33
• However to be fair, this does have one flaw. My question didn't assume that a player can only deal lethal damage, they might do more than lethal damage, since the condition is simply that life is $\leq 0$. Sep 18 '15 at 18:36
• That's taken into account. The sum is over $i < y$ precisely because any $i \ge y$ ends the game. Sep 18 '15 at 18:39
• Also it's fun because this can easily be expanded to any number of players to get a very unhealthy function. Sep 18 '15 at 18:52