Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

First I'll phrase the question as a riddle, and than as a general math problem.

We have 12 lettered vases $(A,B,...,L)$, in each vase there are 30 numbered balls (1-30). In each ball there is some random amount of money between 1-1000 dollars (the distribution of the money in the balls is some IID). Now we have two options:

1) We can ask which number (1-30) contains in average the largest amount of money, and than we get 12 balls of that number, we open them all and we take the ball with the highest amount of the 12.

2) We can ask which vase (A-L) contains the largest sum of money, and than we get 30 balls from that vase, we open them all and we take the ball with the highest amount of the 30.

What is the better strategy, assuming that we want a lot of money...

Now to phrase it more generally:

Let $ A \in\mathbb{N}^{m\times n} , n>m$,

Let $x_{ij}$ be i.i.d. (real) random variables with mean 0 and variance 1

Let $X_1=\max_{1\leq i\leq m}{\sum_{1\leq j\leq n}a_{ij}}$

and let $X_2=\max_{1\leq j\leq n}{\sum_{1\leq i\leq m}a_{ij}}$

What is larger (in average, or the expected value of) $X_1$ or $X_2$? That is, what we should take first, the maximum value of the rows and than the highest value in that row, or the maximum value of the columns and than the highest value in that column?

Another question (more combinatorial): We can ask in a case where all of the values in the matrix are different and between 1 to $m\cdot n$. So we have a pure combinatorial question about the possible $m\cdot n!$ permutations of the numbers in the matrix.

The riddle is of course like this:

Let $ A \in\mathbb{N}^{12\times 30}$ ,$1\leq a_{ij} \leq 1000$ (by i.i.d distibution)

Let $X_1=\max_{1\leq i\leq 12}{\sum_{1\leq j\leq 30}a_{ij}}$ (Option 1)

and let $X_2=\max_{1\leq j\leq 30}{\sum_{1\leq i\leq 12}a_{ij}}$ (Option 2)

Thanks! David

Edited. Thanks for the comments of Yemon, Gerry and James.

share|improve this question
    
It doesn't make any difference, if $m=1$; it doesn't make any difference, if $m=n$; since it doesn't make any difference in the extreme cases, I'm going to guess it doesn't make any difference ever. –  Gerry Myerson Aug 15 '11 at 10:21
    
Gerry, I'm not sure I follow. In the case $m=1$ one seems to be comparing (the expected value of) the sum of entries with the maximum of entries. –  Yemon Choi Aug 15 '11 at 10:28
1  
David, I think you need to clarify whether you are interested in the case where the entries are IID, or where they are obtained by randomly placing $mn$ distinct numbers into the $mn$ slots. These two scenarios would seem to have different underlying stochastic models. –  Yemon Choi Aug 15 '11 at 10:29
4  
I like the question (in the formulation of the riddle) but the generalisation of it written below isn't right. In the general formulation you wrote, you just compare the expectation of one sum with that of the other, but actually you want to take only the maximum of the individual summands in each case. Also as Yemon points out, the "specific case" at the end is not a special case of the general problem since the entries are no longer i.i.d. –  James Martin Aug 15 '11 at 11:23
1  
@Yemon, the question asks different things in different places. I was taking the interpretation that OP wants the maximum element in the row or column with maximum sum. –  Gerry Myerson Aug 15 '11 at 12:26
add comment

4 Answers

up vote 7 down vote accepted

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.

share|improve this answer
    
What is the argument that the random rearrangement version is similar to the IID version? –  Douglas Zare Aug 15 '11 at 14:16
    
The argument is stable with respect to the number of prize and empty balls. Little changes if we have a few instead of 1 prize balls and about $2m$ instead of exactly $2m$ empty balls. So, if the probability of a prize ball is $C/n$, and of an empty ball $m/n$, the result is the same. If the table is big enough, the distribution of the sample is almost fixed and the only question is what goes where. Perhaps, if you fix some decent distribution first and let m,n grow afterwards, you'll have some interesting asymptotic effect that makes one strategy better but, in general, they are incomparable. –  fedja Aug 15 '11 at 14:42
    
If you have one prize ball of value $p=1/2$ and one penalty ball of value $-1$ in a $2 \times n$ matrix, then the random rearrangement analysis is really simple. You find the prize as long as the prize and penalty are not in the line you add up first, otherwise you get $0$. So, the row first method gives an expected value of $p \frac{n}{2n-1}$, while the column first method gives $p \frac {2n-2}{2n-1}$. I think these values are much different with an IID approximation. –  Douglas Zare Aug 15 '11 at 17:37
    
It depends on what you mean by "much", but OK, I'll add the formal IID argument later. –  fedja Aug 15 '11 at 19:06
    
Sorry if I'm missing something trivial. Does this version with one "prize ball" is when failing to find the ball with the maximum amount is "bad", or it also solve the case with scores and we want in average the highest score? Maybe it is the same thing. Maybe the method that is more probable to give you the best ball is also the method that will give you in average the highest amount of money, but I fail to see why it will be the case in every condition. If it is a known fact about i.i.d, can you give me a reference? –  Tangent Aug 16 '11 at 5:25
show 1 more comment

Asymptotics when the numbers involved become large suggest that you will want to select the best vase. That is, if there are more columns than rows, take the best row.

Suppose eg that the amounts $a_{ij}$ are i.i.d. with exponential(1) distribution. Suppose there are $m$ rows and $m^2$ columns, and $m$ is large.

Now, the distribution of a given column-sum concentrates around $m$, and even the max of $m^2$ such column sums will be $m(1+o(1))$. Meanwhile, the max of $m$ i.i.d. exp(1) random variables conditioned on their sum being $S$ is like $(\log m+o(1))S/m$. So the maximum entry in the column with largest sum will be $\log m + o(1)$.

Similarly, the maximum entry in the row with largest sum will be $\log(m^2)+o(1)$ which is better.

share|improve this answer
add comment

This is not close to a complete answer, but for $m=2$ rows and $n>>2$ columns, and uniform random variables, you get a higher expected value by taking the largest value in the larger row.

If you simply just look at the largest of $n$ IID random variables uniform on $[0,1]$ in the first row, the expected maximum is $n/(n+1)$. Choosing the larger row does not decrease this, so the expected value returned by this method is at least $n/(n+1)$.

The sums of the columns are distributed by the tent function supported on $[0,2]$. Conditioning on the maximum value of the sum of a column $v \gt 1$, the expected largest value in that column is $1/2 + v/4$, a linear function. The value is smaller, $3v/4$, in case the column has sum under $1$. The expected value of this method is at most $1/2 + E(v_n)/4$ where $v_n$ is the maximum of $n$ IID samples from the tent function on $[0,2]$.

I believe $E(v_n)$ is roughly $2-\frac{c}{\sqrt{n}}$, which would imply that the expected higher entry in the column with the largest total is about $1-\frac{c}{4\sqrt{n}}$ which is asymptotically smaller than $1-1/(n+1)$. A quick estimate which establishes the inequality for large $n$ is to note that the probability that the sum in a column is at most $2-\sqrt{\frac 2 {n+1}}$ is $\frac{n}{n+1}$, so the probability that the largest column sum is at most $2-\sqrt{\frac 2 {n+1}}$ is $(\frac{n}{n+1})^n \gt 1/e$. So, maximizing the columns first produces a value which is at most $1-\frac{1}{4e}\sqrt{\frac{2}{n+1}}$ which is asymptotically smaller than the lower bound for the expected value from maximizing the row sum, $1-\frac{1}{n+1}$.

In a quick numerical test for $m=2, ~n=100$, the row method gave a value of about $0.991$ and the column method about $0.969$. For $m=2, ~n=3$, the values were $0.835$ and $0.829$, respectively.

share|improve this answer
    
About the numerical test. I'm ashamed to show it in a mathematical forum, but I ran a simulation in MATLAB, averaged over 10000 simulations. For $m=2, n=100$: Average for the 1st method (choosing column first) is $0.926$ and for 2nd method is $0.967$. I counted how many times each method was better: 1st>2nd: $0.18$, 2nd>1st: $0.59$, 1st==2n: $0.22$ For $(m,n)=(2,3)$: Avg for 1st: $0.958$ for 2nd: $0.968$. times 1st>2nd: $0.194$, 2nd>1st: $0.234$, 1st==2nd: $0.57$ For $(m,n)=(12,30)$: Avg for 1st: $0.88$ for 2nd: $0.9$. times 1st>2nd: $0.382$, 2nd>1st: $0.547$, 1st==2nd: $0.07$ –  Tangent Aug 15 '11 at 16:14
    
Perhaps what I called first and second disagree with your conventions, but I do not expect to see such a difference between my simulation's $0.991$ and your $0.926$. –  Douglas Zare Aug 15 '11 at 16:34
    
I ran the same test as Douglas (before seeing his answer) for (m,n)=(2,3), and got the same answers, 0.835 and 0.829. I'm not sure how Tangent is getting 0.958 and 0.968 here, unless it has something to do with what James Martin pointed out in the comments to the original problem. –  Barry Cipra Aug 15 '11 at 21:39
add comment

Perhaps some understanding will occur if a variant is studied. Suppose we chuck the vases and arrange the T-many balls on a billiard table. We are allowed to take any groups of size T/m through T/n and weigh the group on a scale to see which group has the most gold (money), and afterwards select the group we like and select the heaviest object from that group. Here m and n are integers greater than 1. If we could select the whole group, we could find the largest by inspection. If we allowed m to be some number between 1 and 2, there would be some good chance of finding the heaviest ball. If we could instead choose groups of size 1, again by exhaustion we could find the largest with certainty, and could have a good chance of finding a large amount if groups of size 2 were used.

The idea of recasting the problem into a weighing problem is not arbitrary. There are schemes where using a balance scale and a logarithmic number of weighings, one can find a maximum with high probability, especially if the weight distribution resembles that of classic coin puzzles. If you are restricted to only two weighings of each ball, with a different group for each weighing, and you know only the relative order of the weighings and not the values of the weights themselves, it makes sense to me to pick the smaller group, as there is less noise to hide a large weight.

Gerhard "Ask Me About System Design" Paseman, 2011.08.15

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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