確率が等しくないときのバケットソートの期待値

Question

私はn入力数とnバケットを持つバケットソートアルゴリズムに関連する問題を解決するのに役立つ必要があります。この本から得た例では、アイテムの確率が特定のバケットに落ちるという問題が示されています。これは等しい=   です。
ここでは、nバケットがあり、nの数値（範囲0〜1）をランダムに生成するという問題が見つかりました。生成された数字yが> 0.5であれば、コインを投げる。コインが「HEAD」になると、y = y-0.5となります。
質問は以下のとおりです。

1. 数Yは最初のバケットに陥る確率は何ですか？
2. 数字yが最後のバケットに入る確率はいくらですか？
3. このバケットソートの平均実行時間を得るための期待値を計算するにはどうすればよいですか？

ありがとうございます。確率1/2で

Answer 1

1. • 、Y未満1/2あります。これに条件付けられ、確率は2/nで、最初のバケットに入ります。確率/2で

   • 、Yは1/2より大きい。これに基づいて、最初のバケットに入る確率は（1/2）（2/n）です。

   • 合計確率定理により、確率は1.5/nです。対称性によって、これはバケットの前半のそれぞれについて真です。

2. 確率はバケットの最初の半分の各々について1.5/Nあるので、後半の各々に対する確率は、対称性により、ある（1 - （N/2）（1.5/n））/（0.5n）= 0.5/nである。

3. 期待は線形です。期待の線形性によって、期待値は各バケットを（2次的に）ソートする時間の期待値の合計です。第1バケットおよび第2バケットのそれぞれは、一定の予想時間を有する。証明は本質的に古典的なバケットソートの場合と同じです。バケットあたりの分布は、パラメータがα/nのαのBernoulliです。