Suppose there is a random walk on the integer line, where the value cannot go below $0$, and the process stops when it hits a barrier at value $k$. The goal is to compute the expected number of steps to hit the barrier, starting from $0$.
Up to here, the problem seems to be fairly classic, and known as "monkey at a cliff" or "gambler's ruin" (with a reflecting barrier), see e.g. http://www2.math.uu.se/~sea/kurser/stokprocmn1/slumpvandring_eng.pdf.
The difficulty is that in the case I'm considering, the transition probabilities are not defined to be $p=1/2$ of doing $+1$ and $-1$. Instead, at every time step the adversary is allowed to choose between different transition probabilities, but the expected change must always be at least $0$. For example, the adversary might choose a transition with probability $p=1/4$ of doing $+3$ and probability $p=3/4$ of doing $-1$. The probability of doing $+0$ is always $0$.
I have tried doing a similar proof as in the case with simple probabilities, but do not know how to account for the varying transition probabilities. I expect the answer should still be $k^2$ expected steps to hit the barrier, because doing "bigger steps" should only be better on average, but do not know how to show this. Maybe there is some theorem about random walks that could help ?