シャッフルの平均移動距離はN/3

N/3

  • 配列の要素数Nが大きいとき、おおよそN/3と言われている link
  • 証明を書いている人もいた link が、N→∞の箇所が私には分からなかった

実際に計算してみる

  • 結論としては、N/3 - 1/(3*N) となった★
    • 和の公式など使う
    • 1+2+...+n = ～
    • 12 + 22 + ... + n2 = ～
  • Nが大きいときはおおよそN/3となる
  • N=1,2,3の時を具体的に求めたものとも合う
  • N/3より「ちょっと小さい」とはどういう意味付けができるか？と考えたが分からず

独立に考えていいのか？

  • index kについての平均移動距離を考えて、それを足し合わせた結果が★なのだが、合っていそうな気もするが本当か？
  • 確率的に元の位置を1つ選び、移動場所を確率的に決める。それを繰り返すとすると「すでに取られた場所」を考慮する必要があるのでは
  • 全部まとめて一度実数に飛ばして小さい順から割り当てる（下記画像）と考えれば大丈夫なのかな