4
$\begingroup$

This is just a problem I have thought of.

Let us say we have a square matrix of dimension $n$ with possible entries $1, 2, 3,..., n^2$ and we can freely distribute the entries in the matrix, each one has to be used exactly once.

The numbers then are drawn without replacement.

The probability that number $k$ is drawn is $0 \leq P(k) \leq 1$ with $\sum_{k=1}^{n^2}P(k)=1$

Now, we know the probabilities of the draws before we fill in our matrix. Let us say we sorted them such that $0 \leq p_1 \leq p_2 \leq ... \leq p_{n^2}$. We want to cheat and optimally distribute the numbers in order to minimize the expected number of draws until we cross out a whole row or column.

Is this a known problem? Is there an optimal strategy on how to distribute the probabilities $p_i$ in our matrix to minimize the expected number of draws until we cross out a whole row or column, and what is one such strategy?


I was thinking of determining the expected value of number of draws to get a certain number (then determine expected draws to get whole rows and columns and minimize those), but I do not think I can define it only given the $P(k)$, I would need to define how they change after each draw.

I was thinking that it is reasonable to remodel the probabilities after each draw for nonzero $P(k)$. Let us call $D$ the set of already drawn numbers. Then for $k \notin D$ with $P(k)\neq 0$ we do $$P'(k)=\frac{P(k)}{1-\sum_{ d \in D}P(d)}$$

But it sounds horribly complex!

Then again, it shouldn't matter, because if we have some remaining nonzero probabilities, their new probabilities are in the same order, that is if $P(k) \geq P(l)$ and both were not drawn, then $P'(k) \geq P'(l)$.

$\endgroup$
  • $\begingroup$ To win normal Bingo, you have to complete a row/column faster than other players. That's a subtly different problem than e.g. minimizing your own completion time, esp. if you can look at the other players' grids before filling in your own. If we ignore that subtlety, though, just minimizing your own completion time is still a great math problem. For $n=2$ I imagine the best answer is ${1 \,\, 2 \choose 3\,\, 4}$, but for higher $n$... would it actually depend on the values? Fascinating... (Also if you had included the diagonals, the added asymmetry makes things much more complicated.) $\endgroup$ – antkam Oct 8 '19 at 4:39
  • $\begingroup$ @antkam Your proposed solution for $n=2$ surely is not optimal for $P(1)=P(4)=0$ and $P(2)=P(3)=0.5$, as it is not possible to get a row or a colum full. Did you mean the $p_i$ as the entries? $\endgroup$ – 77and33is100 Oct 8 '19 at 18:22
  • $\begingroup$ haha, yes, i was lazy but i meant $p_i$ i.e. ${p_1 \,\,\, p_2 \choose p_3 \,\,\, p_4}$ $\endgroup$ – antkam Oct 8 '19 at 18:33
  • $\begingroup$ Oh yeah, the $P'(k)$ you defined - this problem (even without the Bingo aspects) is called something like "unequal probability sampling without replacement" and is not easy. Google it and you will see. $\endgroup$ – antkam Oct 8 '19 at 19:26
  • $\begingroup$ I have just edited! I think this is not important, but this stands in the way of calculating concrete expected values. $\endgroup$ – 77and33is100 Oct 8 '19 at 19:28

Your Answer

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

Browse other questions tagged or ask your own question.