Skip to main content
MathOverflow

Return to Answer

added 1429 characters in body
Source Link
fedja
fedja
  • 61.9k
  • 11
  • 160
  • 302

I believe that the answer heavily depends on the distribution and, thereby, is incomprehensible. Indeed, let us consider the $2\times n$ table (2 rows, n columns). I'll use the random rearrangement version (by the law of large numbers it shouldn't really matter too much). Suppose that we have one "prize ball" $p$, $2k$ "empty balls" $0$ and $2n-2k-1$ "penalty balls" $-1$.

If $p>1$, choosing the best column guarantees us that the prize ball is there, while the best row may fail to contain it, so the column strategy is, clearly, better.

However, if $p<1$, the row strategy guarantees $p$ with probability greater than $1/2$ (the best row is the one with fewer penalty balls so, if we place the penalty balls first and the prize ball next, we have higher chance for the prize ball to go to the better row). Also, the best row is guaranteed to contain either the prize ball, or an empty ball. Thus, we get more than $p/2$ from the row strategy. However, with the column strategy, the probability to find the prize ball is at most the probability that it is not paired with the penalty ball, which is $\frac{2m}{2n-1}$, plus the probability that no two empty balls are paired, which is, roughly speaking, of order $(1-\frac {m^2}{n^2})^n$ for $m\ll n$, so if $\sqrt n\ll m\ll n$, we get much less than $\frac 12$. But without finding the prize ball, we can get nothing at best.

EDIT:

Following Douglas' comments, here is the IID case. Let $a$ be the prize ball probability and $b$ be the empty ball probability (we shall choose them later) and $c=1-a-b$ be the probability of the penalty ball.

Case 1. $p>1$. Here, if the prize ball is there at all, we'll get it with the column strategy. The only chance to get $-1$ is when everything is $-1$. The row strategy cannot give more in the all $-1$ case, gives $0$ if the prize ball is not there and there are empty balls, and can yield less than the prize ball in some ohter cases too. So, it is worse regardless of the probability assignments.

Case 2: $p<1$. If we go rows first, we get at least $[1-(1-a)^n]^2p$ chance to get the prize ball (the probability that both columns have at least one) and the probability $\le 2c^n$ for the penalty ball (at least one column is pure penalty). So, if $a\gg 1/n$, $b\gg 1/n$, and $p$ is close to $1$, we get almost $1$ on average.

Now, the column strategy cannot yield more than the prize ball but fails to yield it if all prize balls are coupled with the penalty ones (the chance that it is not the case is that we have one prize-prize or one prize-empty pair, which amounts to roughly speaking $na(a+b)$) and there is an empty-empty pair (that fails with probability $(1-b^2)^n$). So, we cannot hope to get more than $na(a+b)+(1-b^2)^n$, which can be easily made small under our restrictions.

I believe that the answer heavily depends on the distribution and, thereby, is incomprehensible. Indeed, let us consider the $2\times n$ table (2 rows, n columns). I'll use the random rearrangement version (by the law of large numbers it shouldn't really matter too much). Suppose that we have one "prize ball" $p$, $2k$ "empty balls" $0$ and $2n-2k-1$ "penalty balls" $-1$.

If $p>1$, choosing the best column guarantees us that the prize ball is there, while the best row may fail to contain it, so the column strategy is, clearly, better.

However, if $p<1$, the row strategy guarantees $p$ with probability greater than $1/2$ (the best row is the one with fewer penalty balls so, if we place the penalty balls first and the prize ball next, we have higher chance for the prize ball to go to the better row). Also, the best row is guaranteed to contain either the prize ball, or an empty ball. Thus, we get more than $p/2$ from the row strategy. However, with the column strategy, the probability to find the prize ball is at most the probability that it is not paired with the penalty ball, which is $\frac{2m}{2n-1}$, plus the probability that no two empty balls are paired, which is, roughly speaking, of order $(1-\frac {m^2}{n^2})^n$ for $m\ll n$, so if $\sqrt n\ll m\ll n$, we get much less than $\frac 12$. But without finding the prize ball, we can get nothing at best.

I believe that the answer heavily depends on the distribution and, thereby, is incomprehensible. Indeed, let us consider the $2\times n$ table (2 rows, n columns). I'll use the random rearrangement version (by the law of large numbers it shouldn't really matter too much). Suppose that we have one "prize ball" $p$, $2k$ "empty balls" $0$ and $2n-2k-1$ "penalty balls" $-1$.

If $p>1$, choosing the best column guarantees us that the prize ball is there, while the best row may fail to contain it, so the column strategy is, clearly, better.

However, if $p<1$, the row strategy guarantees $p$ with probability greater than $1/2$ (the best row is the one with fewer penalty balls so, if we place the penalty balls first and the prize ball next, we have higher chance for the prize ball to go to the better row). Also, the best row is guaranteed to contain either the prize ball, or an empty ball. Thus, we get more than $p/2$ from the row strategy. However, with the column strategy, the probability to find the prize ball is at most the probability that it is not paired with the penalty ball, which is $\frac{2m}{2n-1}$, plus the probability that no two empty balls are paired, which is, roughly speaking, of order $(1-\frac {m^2}{n^2})^n$ for $m\ll n$, so if $\sqrt n\ll m\ll n$, we get much less than $\frac 12$. But without finding the prize ball, we can get nothing at best.

EDIT:

Following Douglas' comments, here is the IID case. Let $a$ be the prize ball probability and $b$ be the empty ball probability (we shall choose them later) and $c=1-a-b$ be the probability of the penalty ball.

Case 1. $p>1$. Here, if the prize ball is there at all, we'll get it with the column strategy. The only chance to get $-1$ is when everything is $-1$. The row strategy cannot give more in the all $-1$ case, gives $0$ if the prize ball is not there and there are empty balls, and can yield less than the prize ball in some ohter cases too. So, it is worse regardless of the probability assignments.

Case 2: $p<1$. If we go rows first, we get at least $[1-(1-a)^n]^2p$ chance to get the prize ball (the probability that both columns have at least one) and the probability $\le 2c^n$ for the penalty ball (at least one column is pure penalty). So, if $a\gg 1/n$, $b\gg 1/n$, and $p$ is close to $1$, we get almost $1$ on average.

Now, the column strategy cannot yield more than the prize ball but fails to yield it if all prize balls are coupled with the penalty ones (the chance that it is not the case is that we have one prize-prize or one prize-empty pair, which amounts to roughly speaking $na(a+b)$) and there is an empty-empty pair (that fails with probability $(1-b^2)^n$). So, we cannot hope to get more than $na(a+b)+(1-b^2)^n$, which can be easily made small under our restrictions.

Source Link
fedja
fedja
  • 61.9k
  • 11
  • 160
  • 302

I believe that the answer heavily depends on the distribution and, thereby, is incomprehensible. Indeed, let us consider the $2\times n$ table (2 rows, n columns). I'll use the random rearrangement version (by the law of large numbers it shouldn't really matter too much). Suppose that we have one "prize ball" $p$, $2k$ "empty balls" $0$ and $2n-2k-1$ "penalty balls" $-1$.

If $p>1$, choosing the best column guarantees us that the prize ball is there, while the best row may fail to contain it, so the column strategy is, clearly, better.

However, if $p<1$, the row strategy guarantees $p$ with probability greater than $1/2$ (the best row is the one with fewer penalty balls so, if we place the penalty balls first and the prize ball next, we have higher chance for the prize ball to go to the better row). Also, the best row is guaranteed to contain either the prize ball, or an empty ball. Thus, we get more than $p/2$ from the row strategy. However, with the column strategy, the probability to find the prize ball is at most the probability that it is not paired with the penalty ball, which is $\frac{2m}{2n-1}$, plus the probability that no two empty balls are paired, which is, roughly speaking, of order $(1-\frac {m^2}{n^2})^n$ for $m\ll n$, so if $\sqrt n\ll m\ll n$, we get much less than $\frac 12$. But without finding the prize ball, we can get nothing at best.