読者です 読者をやめる 読者になる 読者になる

順序統計量

研究中に思いついた問題

[0,1]一様乱数からn個とってきたとき,小さい方からk番目の値はどうなるか?

であるが,答えがあった.

順序統計量 - Wikipedia

結論としてはベータ分布:Beta(k,n-k+1)になるらしい.

期待値は予想通りk/(n+1).全ての値が等間隔にならぶ.






どこから出てきた問題かというと,各辺のコストが[0,1]一様乱数であるような完全グラフでMSTを作ったところ,頂点数に依らずコストが1より少し大きい程度の値だったことから.
辺数 n(n-1)/2で下位(n-1)個のコストを足したとすると期待値は(n^2-n)/(n^2-n+1)なので,MSTのコストの期待値はこれ以上.
n->∞で1に収束するのではないかとにらんでいるが,詳細は不明.