The description of the problem is simple: Suppose there're many balls in a box. Each ball has a score ranging in $\{c_1,\ldots,c_d\}$, and the probability that you pick a ball of score $c_i$ is $p_i$. Given a budget $C$, you are allowed to repeatedly pick balls with replacement, as long as the total score doesn't exceed $C$. Now the question is,
what's the expectation of the maximum number of balls you can pick?
The problem can also be formulated as follows: suppose $X_1,X_2,\ldots,X_k,\ldots$ are i.i.d multinomial random variables that range in $\{c_1,\ldots,c_d\}$, with corresponding probability $\{p_1,\ldots,p_d\}$ s.t. $\sum_i p_i=1$. Denote $Y_k=\sum_{i=1}^kX_i$, what's the expectation of $$K=\text{arg}\,\text{max}_t\, Y_t\quad\text{ s.t. }Y_t\leq C,$$ where $C$ is some known constant.
It's also acceptable if one can give a non-trivial high-probablity bound of $K$ (i.e., something like $\Pr[M-\epsilon<K<M+\epsilon]>1-\delta$).
My only idea is
$$ \begin{align} \mathbb{E}[K] &= \sum_{i=1}^\infty i\Pr[K=i] \\ &\leq \sum_{i=1}^\infty i\Pr[Y_{i+1}>C] \end{align} $$ If I am lucky, the $\Pr[Y_{i+1}>C]$ can be bounded with some concentration inequality (e.g. Chernoff bound, since each $Y_i$ is a sum of several i.i.d. random variables).
Any suggestions?
You can regard this as a random walk with steps $X_i$, and you are interested in the expectation of the hitting time $\tau_C = \inf\{n\ge 0: Y_n>C\}$. The problem is rather standard, but usually there is no nice explicit expression. By simple martingale arguments you can find asymptotics: defining $X_n' = X_n - E[X_n]$, $Y_n' = Y_n - E[Y_n]$, the process $Y_n'$ is a martingale. Since $\tau_C$ is bounded, by the optional stopping theorem, $$ 0 = E[Y'_{\tau_C}] = E[Y_{\tau_C}] - E[X_1]E[\tau_C], $$ whence $$\frac{C}{E[X_1]} \le E[\tau_C]\le \frac{C+c_d}{E[X_1]},$$ which already gives $E[\tau_C]\sim \frac{C}{E[X_1]}$ as $C\to\infty$.
You can also estimate the probabilities $P(|\tau_C - E[\tau_C]|>a)$ by reformulating them in terms of $Y_n$ and using the large deviation techniques.