# A problem regarding the upperbound of the sum of multinomial random variables.

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?

• WLOG assume $c_1 < c_2 < \ldots < c_d$. Note $K$ is bounded below and above by $\displaystyle \underline{k} = \left\lfloor \frac {C} {c_d} \right\rfloor$ and $\displaystyle \overline{k} = \left\lfloor \frac {C} {c_1} \right\rfloor$. Also $K > k$ if and only if $Y_{k+1} < C$. Therefore $\displaystyle \mathbb{E}[K] = \sum_{k=0}^{\infty} \Pr\{K > k\} = \underline{k} + \sum_{k=\underline{k}}^{\overline{k}-1} \Pr\{K > k\} = \underline{k} + \sum_{k=\underline{k}}^{\overline{k}-1} \Pr\{Y_{k+1} < c\}$ See if this help - if $\underline{k}$ is large then may be CLT can help to approximate it too. – BGM Apr 17 '17 at 17:05

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.