Let there be two bins $b_1$ and $b_2$. We denote the number of balls in $b_1$ as $X_1$ and $b_2$ as $X_2$. The probability a particular ball lands in $b_1$ is given by $p$, and $b_2$ given by $1-p$. We throw in distinguishable balls one by one in the same order until One of ($X_1$, $X_2$) = $C$

Show that $\arg\max_{p}{E[(X_1 + X_2) s.t. one of (X_1,X_2) = C]}$ is given by $p=0.5$

Right now, I have formulated the problem as below,

$$E[(X_1 + X_2) s.t. one of (X_1,X_2) = C] = $$ $$\sum_{i=0}^{C-1}\left(\begin{array}{c}{C+i-1}\\{i}\end{array}\right)\left((1-p)^{i}p^{C}\right)(C+i)+\sum_{i=0}^{C-1}\left(\begin{array}{c}{C+i-1}\\{i}\end{array}\right)\left(p^{i}(1-p)^{C}\right)(C+i)$$

When you take the derivative with respect to $p$ it is clear that $p = 0.5$ leads to a derivative of $0$, but I'm not sure how to show that it is the maximum. I'm having trouble showing that for $0\leqq p<0.5$ the gradient is positive, and for $\ 0.5<p\leqq1$ the gradient is negative, or that $p=0.5$ is a unique solution.

As an aside, the actual problem is with k bins but I'm having trouble even with the simplified two bins case.

  • $\begingroup$ Are you asking: an experiment with $k$ different outcomes appearing with probabilities $p_1,\ldots,p_k$ is repeated until the first time $T_c$ one of the outcomes has appeared $c$-times. Is the expectation of $T_c$ maximal when $p_1=\ldots=p_k=\tfrac{1}{k}$? That can e.g. be shown as follows (1) show that $\mathbb{E}(T_c) =\int_0^\infty \prod_{i=1}^k \exp_c(p_it)\,e^{-t}\,dt$ , where $\exp_c(t)=\sum_{i=0}^{c-1}\frac{t^{i}}{i!}$ (due to Klamkin\&Newman) (2) $\exp_c$ is log-concave on $\mathbb{R}_+$, thus the product $\prod_{i=1}^k \exp_c(p_it)$ is maximised when $p_1=\ldots=p_k$. $\endgroup$ – esg Feb 27 at 19:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.