This originated from an algorithm question.
Given an array of length $N$ of random integers with uniform distribution from $-1000$ to $1000$, the maximum possible product of three elements in this array is given by comparing the product of:
- the three largest positive elements, OR
- the two most negative integers, and the largest positive element.
What is the expected value of this largest product value?
My main issue is dealing with the max argument part of the question. I've tried thinking about enumerating the different combinations of the elements with the largest absolute value, but this seemed clumsy and I was wondering if there was a nicer method.
I can attach an R simulation to see if that helps with any intuition.
Hello and welcome to math.stackexchange.
Here is a partial answer of a slightly modified question. Consider first $n$ independent random real numbers from the interval $[0,1]$. The joint density of the three largest numbers $U < V < W$ is $$ f(u,v,w) = \frac{n!}{(n-3)!} u^{n-3} \quad (0 < u < v < w < 1) \, . $$ Then the expected value of the product of the largest three numbers in the sample is $\frac{n(n-2)}{(n+1)(n+3)}$.
If the sample is from a uniform distribution on $[0,M]$, the expected value is therefore $M^3\frac{n(n-2)}{(n+1)(n+3)}$.
If the sample is instead from the uniform distribution on the integers from 0 to $M$, the expected value of the largest product should be close to this.
If the sample is from the uniform distribution on the integers from $-M$ to $M$, the largest product is formed from two negative numbers and one positive number about 71% of the time (simulation) and from the three largest positive numbers about 29% of the time. The distributions of the products appear to be the same for both cases, but the products tend to to be slightly smaller, since the random numbers tend to be more spread apart. In that case, the quantity $M^3\frac{n(n-2)}{(n+1)(n+3)}$ should be a close upper bound for the expected value in question.
Hope this helps.