Wolfram Language

Zufallsmatritzen

Längste aufsteigende Teilfolgen

Die Anzahl der Permutationen von Elementen, bei der die längste aufsteigende Teilfolge die maximale Länge hat, kann durch die Ermittlung des Durchschnitts über berechnet werden, wobei Matritzen einer CircularUnitaryMatrixDistribution der Dimension sind.

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

Bestimmen Sie die Verteilung der Matrixeigenschaft und berechnen Sie den Mittelwert.

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

Vergleichen Sie mit der direkten Zählung.

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

Bei konvergiert die Verteilung der skalierten Längen der längsten ansteigenden Teilfolge zufälliger Permutationen gegen die TracyWidom-Verteilung mit .

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

Vergleichen Sie das geglättete Histogramm der skalierten Längen mit der WDF der TracyWidom-Verteilung.

Den kompletten Wolfram Language-Input zeigen
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]=

Verwandte Beispiele

en es fr ja ko pt-br ru zh