# Expected value of maximum of a matrix of size $n$

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.

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

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}$$.