3
$\begingroup$

I have a problem of optimal selection given many parameters. I will try to simplify my problem in this example below:

Suppose I have a basket with 100 balls in 10 different colors (not equally distributed and I know how many balls of each color there are). In one of these balls there is a winning lottery ticket. I am allowed to chose 5 (an arbitrary number, is always less than or equal to unique color count) balls and open them. Given that I have the probabilities of every color group containing a winning ticket, how many of which color I should choose these 5 balls from to maximize my winning chance?

My variables are:

$N$ = 100, $C$ = 10, $n$ = 5, and probability vector $P$ which shows $P_c$ = 1 $\forall c\in C\cdots$ where 1 stands for winning ticket.

Which approaches I should take in order to solve this? My intuition is that it is kind of multivariate hypergeometric distribution and maybe using some kinda Bayesian approach would allow me to solve it. My end goal is to come up with an optimal choice strategy here.

thank you beforehand!

Edit: added info about color distribution

$\endgroup$
4
  • $\begingroup$ Do you know how many balls of each color are in the basket? $\endgroup$ – user20160 Feb 19 '20 at 12:42
  • $\begingroup$ yes. I have the distribution of balls and colors $\endgroup$ – Emil Mirzayev Feb 19 '20 at 12:44
  • $\begingroup$ Could you please clarify the notation? It is not clear to me what $P_c$ is and what are the winning probabilities of each color. $\endgroup$ – Davide ND Feb 19 '20 at 13:24
  • $\begingroup$ Sure. It stands for the probability of winning ticket being in color $c$. So, I name it $P_c$ $\endgroup$ – Emil Mirzayev Feb 19 '20 at 13:27
1
$\begingroup$

Let there be $k_i$ balls of color $i$ where $i$ ranges from $1$ to $m=10,$ so that the total number of balls is $k_1+\cdots+k_m=n=100,$ and let $p_i$ be the chance that any randomly chosen ball of color $i$ contains a winning ticket. You are invited to sample up to $s \le m$ balls (without replacement). How to maximize your chances of a winning ticket?

To find out, let's write down that chance, supposing you elect to include $0 \le s_i \le k_i$ balls of color $i$ in your sample, with $s_1+\cdots+s_m \le s.$

We had better decide exactly what these chances mean. We are told there is exactly one winning ticket. Evidently it was placed randomly in one of the $n$ balls. But because the chances might vary, we must suppose different colors $i$ were given different chances $\pi_i;$ a color was selected according to those chances; and then the ticket was placed in that randomly-chosen ball. I take the phrase "I have the probabilities of every color group containing a winning ticket" to mean you know the $\pi_i.$ You also know "how many balls of each color there are"--the $k_i.$

Assign numbers to the balls by giving the ball with the winning ticket the value $1$ and all other balls the value $0.$ This is the indicator of the winner. It is a random variable. Let's call it $X.$ The chance of getting the winner is the expectation of $X.$ Because the chance of any given ball of color $i$ to bear the winner is the chance its color was chosen initially ($\pi_i$) times the chance this is the particular ball of that color with the ticket (equal to $s_i/k_i$ because you are sampling randomly from the balls of each color), that expectation is

$$E[X] = \sum_{i=1}^m \pi_i \frac{s_i}{k_i}= \sum_{i=1}^m \frac{\pi_i}{k_i}s_i.$$

The second expression is a positive linear combination of the $s_i$ with coefficients $\lambda_i = \pi_i/k_i.$ We have reframed the question in the following abstract way (an integer linear program):

Let $\lambda_i$ be a set of $m$ non-negative numbers (of which at least one is positive). Given an integer $s\ge 0,$ find non-negative integers $s_i$ for which $\lambda_1 s_1 + \cdots + \lambda_m s_m$ is as large as possible subject to the restriction $s_1 + \cdots + s_m = s.$

It is an easy mathematical exercise (a consequence of the Rearrangement Inequality) to show that when you don't restrict the $s_i$ to be integers, the solution is to re-index the data so that $\lambda_1 \ge\lambda_2 \ge \cdots \ge \lambda_m$ and to take $s_1$ as large as possible subject to the requirement $s_1 \le \min(k_1,s).$ If you can take more balls, move on to color $2$ and repeat. However, since this solution automatically results in integral values of $s_i,$ it is optimal even when the $s_i$ are required to be integral. In other words,

The greedy algorithm, that takes as many balls as possible from the most likely remaining winning color until $s$ balls have been taken, is optimal.

$\endgroup$
2
  • $\begingroup$ thank you for your answer! How this setup would change if the winning chances are not equally distributed among balls within groups? Should this setup become a separate question? $\endgroup$ – Emil Mirzayev Feb 20 '20 at 13:08
  • $\begingroup$ It wouldn't change at all, because (assuming you cannot distinguish balls of a given color) your selection of balls of a particular color will be random with equal probabilities for each ball. $\endgroup$ – whuber Feb 20 '20 at 13:45

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.