Язык Wolfram Language

Случайные матрицы

Самые длинные возрастающие подпоследовательности

Число перестановок элементов , в которых самая длинная возрастающая подпоследовательность, имеющая предельную длину , может быть вычислена путём нахождения среднего значения , где являются матрицами, полученными из CircularUnitaryMatrixDistribution размера массива .

In[1]:=
Click for copyable input
{k, n} = {6, 2};

Определите распределение матричных свойств и рассчитайте среднее значение.

In[2]:=
Click for copyable input
\[ScriptCapitalD] = MatrixPropertyDistribution[Abs[Tr[\[ScriptCapitalU]]]^( 2 k), \[ScriptCapitalU] \[Distributed] CircularUnitaryMatrixDistribution[n]]; N[Mean[\[ScriptCapitalD]]]
Out[2]=

Сравните с прямым подсчётом.

In[3]:=
Click for copyable input
Count[Permutations[Range[k]], perm_ /; Length[LongestOrderedSequence[perm]] <= n]
Out[3]=

Для распределение нормированных длин самых длинных возрастающих подпоследовательностей случайных перестановок стремится к распределению Трейси-Видома с .

In[4]:=
Click for copyable input
sample[n_] := 1/n^(1/6) (Table[ Length[LongestOrderedSequence[ RandomSample[Range[n]]]], {2000}] - 2.0 Sqrt[n]);

Сравните сглаженную гистограмму выборочных нормированных длин для возрастающих измерений с функцией распределения плотности распределения Трейси-Видома.

код на языке Wolfram Language целиком
In[5]:=
Click for copyable input
dims = {1000, 5000, 10000}; Show[ SmoothHistogram[sample /@ dims, PlotLegends -> (Row[{"n = ", #}] & /@ dims)], Plot[PDF[TracyWidomDistribution[2], x], {x, -4, 2}, PlotStyle -> {Black, Dashed, Thick}, PlotLegends -> {"Tracy-Widom distribution"}]]
Out[5]=

Родственные примеры

de en es fr ja ko pt-br zh