1
$\begingroup$

I have a square matrix (call it $A$) of size $n$ ($n$ is a positive integer). Each column is a permutation of $[1:n]$.

I take the first row of $A$, i.e. $A(1,:)$ and wonder what will be the frequency of the mode. This is, how many times the most common element in the first row of $A$ will appear and whether the mode will be unique.

For example, if

A=
 1     2     5     4     1
 3     3     3     1     3
 5     5     2     2     5
 2     1     4     5     4
 4     4     1     3     2

Then the frequency of the mode is 2 (because 1 appears two times), and the mode is unique because the second most common element in $A(1,:)$ only appears once.

Simulations have shown me that if $n=100$, then the frequency of the mode is 4.23 and is unique in 51% of the cases.

If $n=500$, then the frequency of the mode is $5.14$ and is unique in 47% of the cases.

Any help understanding how these two numbers depend on $n$ would be appreciated.

$\endgroup$
3
  • $\begingroup$ Are the permutations distinct? $\endgroup$
    – Rinkesh P
    Dec 2, 2022 at 13:16
  • 1
    $\begingroup$ Unless there are special (untold) constraints, there is no need to consider a matrix of permutations. What you have is just a uniform distribution. $\endgroup$
    – user16034
    Dec 2, 2022 at 13:34
  • $\begingroup$ It is easy to find examples with a non-unique mode. (In particular, if all elements are distinct, they are all modes.) $\endgroup$
    – user16034
    Dec 2, 2022 at 13:35

1 Answer 1

2
$\begingroup$

This is the classical balls into bins problem with as many balls as bins. The maximum load is with high probability about $\frac{\log n}{\log \log n}$.

$\endgroup$
2
  • $\begingroup$ Thanks. Is the probability that the maximum load is unique known? $\endgroup$
    – fox
    Dec 2, 2022 at 18:36
  • $\begingroup$ Why not try and look it up, now that you know what's it called? $\endgroup$ Dec 4, 2022 at 17:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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