Consider following problem,
You are given $N$ piles, $i^{th}$ pile has size $S_i$.
Until size of all the piles become $0$, repeat the following step.
With probability $p$, size of atmost one pile will be reduced by 1.
Goal is to find the expected number of steps. It is guranteed that $N \cdot p \leq 1$
I encountred the problem while thinking of some algorithmic problem. I would like to know there exist some solution other than bruteforce (using dynamic prgramming over all possible states). Only progress I was able to make is , If there are currently $K$ piles with size greater than 0, then there is $K\cdot p$ probability of moving one step closer to goal.
Let $S=\sum S_i$. Let $P_k$ be the probability that the process ends at the $(S+k)$th step. (The minimum of number of steps is $S$.) The expected number of steps $E$ is:
$$E=\sum_{k=0}^\infty (S+k)P_k$$
$P_k$ is the product of the number of possibilities that the process ends at the $(S+k)$th step ($=A$) and the probability of each possibility ($=B$, which is a constant for fixed $k$).
$A$ would be the number of sequences that has $S+k$ elements and contains $S_i$ $i$'s and $k$ $0$'s. The $m$th element being $i$ means that the $i$th pile was reduced at the $m$th step; $0$ means no pile was reduced.
$$A= {S_1+\cdots+S_N +k \choose S_1}{S_2+\cdots+S_N+k \choose S_2}\cdots{S_N+k \choose S_N}{k \choose k} $$
$$A=\prod_{j=1}^N {\sum_{i=j}^N S_i \,+k \choose S_j}$$
$B$ would be the probability of reducing some specific pile $S$ times and doing nothing $k$ times.
$$B=p^S (1-pN)^k$$
In essence,
$$E=\sum_{k=0}^\infty \bigg[(S+k)p^S (1-pN)^k \prod_{j=1}^N {\sum_{i=j}^N S_i \,+k \choose S_j} \bigg]$$