Expected value of random variable with "slanted" binomial distribution. Lisa is addicted to a game of chance.
The game works like this: Every time Lisa plays she has a probability of $p_{win}$ to get two points and then she can play again in $d_{win}$ seconds, but she can also lose with $1-p_{win}$ probability. If she loses she only gets one point and can play again in $d_{loss}$ seconds ($d_{loss} > d_{win}$).
If lisa plays for $s$ seconds, how many points is Lisa expected to get?
That's easy! Just take the binomial and multip... Not so fast there partner! It's not straight binomial because the number of trials changes depending on which outcomes Lisa gets. If you imagine a binomial graph of outcomes, the graph is slanted because of the delay difference between attempts.
Edit: The direct recursive solution is computationally too slow as $s/d_{win}$ is very large. See below.
What is this about?
I'm working on my open source project and I need to optimize a statistical tool as it has become intractable to use with new inputs.
Previously I would recursively evaluate all the possible outcomes and tally up the weighted result. However with new inputs I overflow the stack, and using a non-recursive method by building the tree in memory quickly exhausted over 1G of memory and was still too slow (gave up after 30 seconds, it needs to be in the 10-100s of ms range). My attempts at using memoization to optimize the graph didn't bear fruit and the code was too complex.
I felt that explaining the problem in terms of ultra autocannon double fire, jam probabilities and cooldowns, jam times, etc just served to make the problem formulation unnecessarily complicated so I reworded it as a game of chance while keeping applicability to the original problem.
I have a solution that gives seemingly correct answers asymptotically but it involves a disgusting over unity probability sum that is used to normalize the result in the end. I'm not convinced that the solution I have is correct or even the best one, which is why I'm asking here. I'm not sure if I should share it, and risk conditioning the answers or keep it hidden to avoid bias.
 A: Iterative solution
Idea
Assume for a moment that instead of a time limit Lisa had a fixed number of trials, $n$, then the binomial distribution would be usable to compute the solution directly: $$n+\sum_{k=0}^{n}Bin(k,n, p_{win})\cdot k.$$
I.e. she gets 1 point per trial so she has at least $n$ points, and for each possible number of wins we compute the probability of that happening times the additional points she would have gotten.
Lisa's game is a Bernoulli Process where the number of remaining trials depends on the prior outcomes. We can visualise the probability of each sequence of outcomes as a graph where each node represents an outcome, the probability, $p_i$, to have the sequence up to that node (from the root), and has two children for each possible outcome. Each path from the root to a leaf represents one possible sequence of events, and the probability in each leaf represents how likely that sequence is.
Now we realise that the sum probability of all the branches from one node, is the probability of that node by definition.
In the case of Lisa's game this means that even if the tree is not complete and fully filled at each level as in the binomial distribution, the sum of the probabilities of each leaf node will sum to unity. Thus by iterating through all leaf nodes and computing the sum: $\sum_{i \in  leaves}p_i\cdot(n_{wins}\cdot 2 + n_{losses}\cdot 1)$, where $n_{wins}$ and $n_{losses}$ are the number of losses and wins on that branch respectively, we get the expected point value for Lisa.
However this requires iterating over $O(2^n)$ nodes and storing them in memory, less than ideal.
However we can directly enumerate the outcomes without building the graph...
Detailed solution
Assume Lisa is incredibly lucky and wins every game. She will then have played $n_{max}=\lceil\frac{s}{d_{win}}\rceil$ games (she doesn't have to wait out the delay from the last attempt to get the points, hence we need ceil here). The probability of this happening is of course ${p_{win}}^n_{max}$ and she would have had $2n_{max}$ points.
It then follows that if we iterate over all $n\in [0, n_{max}]$ and for each iteration we assume Lisa had exactly $n$ wins. If at every $n$ we carefully count all the ways she could have won exactly $n$ times, while playing a new game at every opportunity, then we enumerate all leaf nodes and we can calculate their probabilities. Summing the expected points from each branch weighted by branch probability gives us our expected points for Lisa.
Some caution is required though as Lisa is not required to wait out the delay of $d_{win}$ or $d_{loss}$ at the end of the game. We can partition all the possible branches into three disjoint categories:

*

*The game ended exactly before Lisa could play again, i.e. $s=n_{win}d_{win}+n_{loss}d_{loss}$

*The game ended with a win

*The game ended with a loss

These need to be treated carefully:
If for a given $n$, (1) above is true after trivially computing $n_{loss}$ from the knowns, then the sum probability of all branches with exactly $n$ wins is $P_{branch}(n) = Bin(n_{loss}, n_{win} + n_{loss}, p_{win})$. Obviously (2) and (3) are impossible for these branches. We add $P_{branch}(n)\cdot(2n_{win} + n_{loss})$ to our expected points sum.
On the other hand, if (1) is false for a given $n$ and $n<n_{max}$, then it's always possible to arrange the wins and losses in the sequence so that a loss is last. I.e. category (3) games always exist under these conditions. The number of ways in which one can do this is $P_{branch}(n) = Bin(n_{loss}-1, n_{win} + n_{loss}-1, p_{win})$, i.e. one loss is fixed at the end. The total number of losses for these branches is computed as $n_{loss}=\lfloor \frac{s-n_{win}d_{win}}{d_{loss}} \rfloor+1$ where the floor computes the number of losses where Lisa waited out the $d_{loss}$ delay and the $+1$ is the one at the end where she did not. Again, we add $P_{branch}(n)\cdot(2n_{win} + n_{loss})$ to our expected points sum.
If (1) is false, it is also possible for branches from category (2) to exist but only under strict conditions: $n>0$ AND $\chi=s-(n_{win}-1)d_{win} + n_{loss}d_{loss} \ge d_{loss}$. The last condition shall be read as: If a win were to occur at the very last moment, would there opportunity to add another loss to the sequence? Note that the result of the expression is limited to $d_{win} < \chi < d_{loss}+d_{win}$ due to how the parameters are computed. If the above evaluate to true, then it's possible that a win occurred at as the last outcome and we must add one additional jam, i.e. we compute $P_{branch}(n) = Bin(n_{loss}+1, n_{win} + n_{loss} + 1 - 1, p_{win})$ where we add one additional loss, and remove one win from the binomial as it is now fixed at the end of the sequence. Again, we add $P_{branch}(n)\cdot(2n_{win} + n_{loss}+1)$ to our expected points sum.
After completing the above procedure we're left with the expected number of points that Lisa got in the expected points sum.
Verification
I have implemented and verified the solution by testing the asymptotic behaviour for many different parameter combinations, and by verifying that all $\sum_{\forall n}P_{branch}(n)=1$ in all my tests meaning that all branches were covered in our analysis.
Performance
When naively implemented this is $O(n_{max} {n_{max} \choose n_{loss}})$ but by computing all the ${n \choose k}$ instances using memoized factorials the runtime becomes $O(n_{max})$. Memory is also $O(n_{max})$ in my implementation because I use the accurate method of summing many small floating point numbers and the memoization of the factorials. This is much better than the $O(2^{n_{max}})$ of the recursive and tree based approaches and fast enough for my application.
I don't think the problem could be solved faster than $O(n_{max})$ but I'd love to be wrong.
Closing words
This is pretty much the idea I alluded to in OP; But I found the problems that were causing $\sum_{\forall n}P_{branch}(n)\ne 1$, I had failed to consider category (2) type branches and had some off-by one bugs.
