音楽シャッフル・クイズ

comp

結城さんの音楽シャッフル・クイズ

に応募してみたら，どういうわけか掲載されてしまったのはいいのですが (n さんというのが私です．結城さんありがとうございました)，よくみると

前回のランダム・アルバイト・クイズでは壮絶な勘違いをしでかしてしまいましたが，めげずにシャッフルクイズにも回答してみます．．．
なんてところまでしっかり載っちゃってるよ…．あうー． ＿|￣|○



というわけで，「壮絶な勘違いって何ナニ?? うひひ」と興味津々の方のために，ランダム・アルバイト・クイズの解答もついでに晒してみます． m9（^Д^）ﾌﾟｷﾞｬー してやってください…

ランダム・アルバイト・クイズ自体はこちら．n さんの送った解答は以下．どう間違えたかは読めば分かります．が，読む気もおきないと思うので簡単に解説すると，帰納法と演繹法がごっちゃになってるっつーことです．あほすぎ．鬱死(ry

問題 1:
 
可能である．以下の手順に従えばよい．
 
k 番目の応募者が来た時，
  - k <= 5 であれば無条件に待機させる．
 
  - k > 5 であれば，6 名 (控え室内の 5 名 + やってきた 1 名) から一人
    を選び，拒否する．ただし，拒否対象は以下の確率分布に従って選択する．
 
       * 控え室内の人の場合: 1/k
       * やって来た人の場合: 1 - 5/k
 
このとき，各応募者にとって，最初に控え室にやって来てからこの時点まで待
機し続けられる確率は等しく 5/k になる．これが k >= 5 なる任意の k につ
いて成り立つから，一日の終わりまでに N 人の応募者が訪れたとすれば，採
用される確率は等しく 5/N になる．
 
 
問題 2:
 
k 番目の応募者が来た時，
  - k <= S であれば無条件に待機させる．
 
  - k > S であれば，S+1 名 (控え室内の S 名 + やってきた 1 名) から一
    人を選び，拒否する．ただし，拒否対象は以下の確率分布に従って選択す
    る．
 
       * 控え室内の人の場合: 1/k
       * やって来た人の場合: 1 - S/k
 
このとき，各応募者にとって，最初に控え室にやって来てからこの時点まで待
機し続けられる確率は等しく S/k になる．これが k > S なる任意の k につ
いて成り立つから，一日の終わりまでに N 人の応募者が訪れたとすれば，採
用される確率は等しく S/N になる．
 
(帰納的証明)
 
まず，k = S とする．集まった S 名が待機できる確率は明らかに 1 である．
 
つぎに，k = n ( >= S) とする．いま，控室の S 人の応募者に 1 から S ま
で番号を振り，新しくやって来た応募者に S+1 をつける．
 
わたしが拒否対象の選択を繰り返していくと，各応募者が待機し続けられる確
率は明らかに減っていく．候補者 i が部屋に残っている確率を P_i(n) とし，
わたしが応募者 i を拒否する確率を a_i(n) とすれば，
 
    for i=1...S,  P_i(n) = P_i(n-1) * (1 - a_i(n))             (1)
    for i=S+1,    P_i(n) = 1 - a_i(n)                          (2)
 
となる．
 
控え室にいる S 名は，やって来てから現在まで待機し続けられる確率が等し
くなるように選ばれているはずなので，
 
    for i,j=1...S,  P_i(n) = P_j(n)                            (3)
 
である．よって以降では単に P(n) とかく．また，わたしがこれから行う選択
によって，各応募者のチャンスに差があってはならないので，
 
    for i,j=1...S+1,  P_i(n+1) = P_j(n+1)                      (4)
 
である．さらに，明らかに
 
    Σ a_i(n) = 1                                              (5)
 
である．
 
(1)(3)(4) より明らかに，i=1...S に対し a_i(n) は等しい．よってこれを単
に a(n) とかく．また，i=S+1 に対する a_i(n) を a'(n) とかく．(1)〜(5) 
を書き直すと，
 
    P(n) = P(n-1) * (1 - a(n))                                 (6)
    P(n-1)(1 - a(n)) = 1 - a'(n)                               (7)
    a(n)S + a'(n) = 1                                          (8)
 
となる．(7)(8) より，
 
    a(n) = P(n-1) / (P(n-1) + S)                               (9)
 
が得られる．これを漸化式 (6) に代入すると
 
    P(n) = SP(n-1) / (P(n-1) + S)                              (10)
 
となるが，Q(n) = 1/P(n) を導入すると (10) 式は
 
    Q(n) = Q(n-1) + 1/S                                        (11)
 
と簡単になり，一般項は
 
    Q(n) = Q(S) + (n - S)/S                                    (12)
    P(n) = P(S)S / (S + (n-S) P(S))                            (13)
 
となる．P(S) は 1 なので，結局
 
    P(n) = S/n                                                 (14)
    a(n) = 1/n                                                 (15)
    a'(n) = 1 - S/n                                            (16)
 
となる．
 
(証明終)

以上です．



ついでに，今回の音楽シャッフル・クイズの解答では


どのように分布が偏るかも考えてみたいのですが，厄介そうなので，思いついたらまたフィードバックいたします．
なんてことをうっかり書いてますが，結局思い付いてません(ぉ．最初，swap って線形代数でいう互換だから，偶置換と奇置換で違いが出るのかな，と思って N=3 でやってみましたが，見事にはずれました．誰か解いてくれ．ていうか考えてて塵理論思い出した．