Max-Min and Min-Max universally yield Gumbel

08/27/2018
by   Iddo Eliazar, et al.
0

"A chain is only as strong as its weakest link" says the proverb. But what about a collection of statistically identical chains: How long till all chains fail? The answer to this question is given by the Max-Min of a random matrix whose (i,j) entry is the failure time of link j of chain i: take the minimum of each row, and then the maximum of the rows' minima. The corresponding Min-Max is obtained by taking the maximum of each column, and then the minimum of the columns' maxima. The Min-Max applies to the storage of critical data. Indeed, consider multiple copies (backups) of a set of critical data items, and consider the ( i,j) matrix entry to be the time at which item j on copy i is lost; then, the Min-Max is the time at which the first critical data item is lost. In this paper we establish that the Max-Min and Min-Max of large random matrices are universally governed by asymptotic Gumbel statistics. We further establish that the domains of attraction of the asymptotic Gumbel statistics are effectively all-encompassing. Also, we show how the asymptotic Gumbel statistics can be applied to the design of large systems.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset