8
$\begingroup$

Take an $n \times n$ random matrix whose entries are i.i.d. with uniform distribution in $[0,1]$. Look at the sums of the elements of each row and then permute the rows so that these sums form an increasing sequence. Next, perform the analogous sorting of the columns.

Obvious remarks: Almost surely no two rows or columns will have the same sum and so the double-sorting operation is uniquely defined. Moreover, the operation is symmetrical: it makes no difference to sort the columns first.

Question: What are the expected value and variance (or more generally, the probability distribution) of the $(i,j)$ entry of the matrix?

I imagine that exact answers should be very complicated, so approximate or asymptotic answers (as $n \gg 1$) may be even better.

A variation of the problem is to take each entry uniformly distributed on $\{0,1\}$ (i.e., a fair coin toss). The bi-sorting won't be necessarily unique, but in that case we choose randomly among the possibilities, say.

PS: Here is the output of an experiment with $n=20$: $$ \begin{array}{cccccccccccccccccccc} 0 &0 &0 &1 &1 &0 &0 &0 &0 &1 &0 &1 &0 &0 &1 &1 &0 &1 &1 &0 \\ 1 &0 &0 &0 &0 &0 &1 &0 &1 &1 &1 &0 &0 &1 &0 &1 &1 &0 &0 &1 \\ 0 &1 &1 &0 &0 &0 &1 &0 &0 &1 &0 &1 &0 &0 &1 &0 &0 &1 &1 &1 \\ 0 &0 &0 &0 &0 &0 &1 &0 &0 &1 &1 &1 &1 &1 &1 &0 &0 &1 &1 &0 \\ 0 &1 &0 &0 &0 &1 &1 &1 &0 &0 &0 &1 &1 &0 &0 &0 &1 &1 &0 &1 \\ 1 &1 &0 &0 &0 &0 &1 &1 &0 &1 &1 &1 &1 &1 &0 &1 &0 &0 &0 &0 \\ 0 &0 &1 &0 &1 &0 &0 &1 &1 &1 &1 &0 &1 &1 &0 &0 &1 &0 &1 &0 \\ 0 &1 &0 &1 &0 &1 &0 &1 &1 &0 &0 &0 &1 &1 &0 &0 &1 &0 &1 &1 \\ 1 &0 &0 &1 &0 &0 &0 &1 &1 &0 &0 &0 &1 &0 &1 &1 &1 &0 &1 &1 \\ 0 &1 &0 &0 &0 &1 &1 &0 &1 &0 &1 &0 &0 &1 &1 &1 &0 &0 &1 &1 \\ 0 &0 &1 &1 &0 &1 &0 &0 &1 &1 &1 &1 &0 &1 &1 &0 &1 &0 &1 &0 \\ 0 &1 &1 &0 &1 &1 &0 &0 &0 &1 &1 &0 &0 &1 &0 &1 &0 &1 &1 &1 \\ 0 &0 &1 &1 &1 &1 &0 &1 &1 &0 &1 &0 &0 &0 &0 &1 &1 &1 &1 &1 \\ 0 &0 &0 &0 &1 &1 &1 &1 &0 &1 &0 &1 &1 &0 &1 &0 &1 &1 &1 &1 \\ 1 &0 &1 &1 &0 &1 &0 &0 &0 &0 &0 &1 &1 &1 &1 &1 &0 &1 &1 &1 \\ 1 &0 &0 &1 &1 &0 &1 &1 &1 &1 &1 &0 &0 &1 &1 &0 &1 &1 &0 &1 \\ 0 &1 &0 &1 &1 &0 &1 &1 &1 &0 &0 &1 &1 &1 &0 &1 &1 &1 &0 &1 \\ 0 &1 &1 &1 &1 &0 &0 &1 &0 &0 &1 &1 &1 &0 &1 &1 &1 &1 &1 &1 \\ 0 &0 &1 &0 &1 &1 &1 &0 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &0 &0 \\ 1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &1 &0 &1 &1 &1 &1 &1 &1 \end{array} $$ As expected, $0$s are more concentrated around the upper left corner, while $1$s are more concentrated around the lower right corner.

Improve this question
$\endgroup$
9
  • $\begingroup$ Something is not quite right in your simulation, it seems: the probability to have a row with less than 1 zero is bounded above by $n^2 2^{-n}$. With $n=20$, it is minuscule, yet you do get such a row in your simulation. (Note that the operation you defined does not change the number of rows with one or less zeros.) $\endgroup$
    – ofer zeitouni
    Commented May 5, 2014 at 6:08
  • $\begingroup$ I generated the matrix using Numbers spreadsheet; maybe their random number generator is not very good. Apart from this "miracle", the row-sums (8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 12, 12, 12, 13, 13, 14, 14, 19) and the column-sums (6, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12, 12, 12, 12, 12, 12, 13, 13, 14, 14) doesn't seem to be too exceptional. And since the exceptional row with many 1's simply goes to the bottom, it doesn't influence too heavily the result of the experiment. $\endgroup$
    – Jairo Bochi
    Commented May 5, 2014 at 10:55
  • $\begingroup$ BTW, the probability of having a row or column with at most one entry different form the others is aprox. 1/600, which is indeed quite rare but not extremely rare... $\endgroup$
    – Jairo Bochi
    Commented May 5, 2014 at 11:46
  • 2
    $\begingroup$ In any case, for $(i,j)=(\alpha n, \beta n)$ the law of $(X_{i,j})$ converges to the uniform law. The tilting due to your operations is very small, asymptotically - since the maximal row sum is of order $sqrt{n}$ with a logarithmic correction, the distribution you get for $X_{i,j}$ is essentially an exponential tilting of uniform with mean of order $1/2+(log n)/\sqrt{n}$. Not very much.... $\endgroup$
    – ofer zeitouni
    Commented May 5, 2014 at 15:19
  • 1
    $\begingroup$ I actually wouldn't be surprised if even the distribution of the corner entries converged to uniform on $[0,1]$. A rough idea might be to first show (assuming this is true!) that the maximal row/column sum typically differs from the second largest by more than $1$. This would imply that changing a single entry has no impact on the extreme points of the sorting, which would in turn imply that whether an entry is sorted to the upper left is (nearly) independent of the value of the entry. $\endgroup$
    – Kevin P. Costello
    Commented May 5, 2014 at 21:29

1 Answer 1

Reset to default
4
$\begingroup$

Let $X$ be the array after your operation. The law of $X_{i,j}$ for $(i,j)$ chosen in a deterministic way from $[1,..,n]^2$ converges to the uniform law. The tilting due to your operations is very small, asymptotically - since the maximal row sum is of order $\sqrt{n}$ with a logarithmic correction, the distribution you get for $X_{i,j}$ is essentially an exponential tilting of uniform with mean of order $1/2+O(\log n/\sqrt{n})$. Not very much, and not enough to affect the limit law.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .