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?

  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.