指示変数と期待値の線形性

$1,2,3,4,5,6$ を $1$ 列に並べる $6!$ 通りの並べ方から $1$ つを等確率で選び、それを配列 $A[1],A[2],\dots ,A[6]$ とする。$1\le i<j\le 6$ を満たす整数の組 $(i,j)$ で $A[i]>A[j]$ となるものを「転倒」とよぶ（転倒の個数は、挿入ソートで隣り合う要素を交換する回数に等しいことが知られている）。配列 $A$ に含まれる転倒の個数を $X$ とするとき、期待値 $E[X]$ を求めよ。

互いに異なる $6$ 個の実数を、$6!$ 通りの並べ方のどれもが等確率 $\frac{1}{720}$ で起こるように並べ、配列 $A[1],A[2],\dots ,A[6]$ を作る。$1\leqq i<j\leqq 6$ を満たす整数の組 $(i,j)$ のうち、$A[i]>A[j]$ となるものを転倒といい、転倒の個数を $X$ とする（$X$ は、この配列を挿入ソートで昇順に並べかえるときに行われる隣り合う要素の交換の回数に等しい）。$X$ の期待値 $E(X)$ を求めよ。

長さ $12$ のビット列 $b_1{b}_2\cdots b_{12}$ を、各ビット $b_j$ $(j=1,2,\dots ,12)$ が互いに独立に確率 $\frac{1}{2}$ ずつで $0$ または $1$ になるようにランダムに作る。このビット列の中でパターン $101$ が現れる回数 $X$ を
$$X=(b_i{b}_{i+1}{b}_{i+2}=101\text{ となる整数 }i(1\le i\le 10)\text{ の個数})$$
と定める（重なった出現も別々に数える。たとえば $10101$ の中には $101$ が $2$ 回現れる）。$X$ の期待値 $E(X)$ を求めよ。

昇順に並んだ互いに異なる $10$ 個の数の配列 $A[1]<A[2]<\cdots <A[10]$ から、値 $x$ を次の二分探索で探す。ただし、$x$ は $A[1],A[2],\dots ,A[10]$ のどれかと必ず等しいとする。

• はじめに $\mathrm{lo}=1$, $\mathrm{hi}=10$ とする。
• $m=\lfloor \frac{\mathrm{lo}+\mathrm{hi}}{2}\rfloor$ とし、$x$ と $A[m]$ を比較する。この比較は $1$ 回で「$x=A[m]$」「$x<A[m]$」「$x>A[m]$」のどれであるかがわかるものとし、比較 $1$ 回と数える。
• $x=A[m]$ ならば探索を終える。$x<A[m]$ ならば $\mathrm{hi}=m-1$ とし、$x>A[m]$ ならば $\mathrm{lo}=m+1$ として、前の手順に戻る。

$x$ が $A[1],A[2],\dots ,A[10]$ のそれぞれと等しい確率がどれも $\frac{1}{10}$ であるとき、探索を終えるまでの比較回数の期待値を求めよ。

バケット数 $4$ のチェイン法ハッシュ表に、互いに異なる $5$ 個のキーを挿入する。各キーのハッシュ値は $4$ 個のバケットのどれかに等確率 $\frac{1}{4}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$5$ 個すべてを挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

互いに異なる $5$ 個の数が入った配列から、小さい方から $3$ 番目の数（中央値）を、次の乱択選択アルゴリズム（乱択クイックセレクト）で求める。

• 現在の候補の集合を $X$ とし、最初は $X$ を $5$ 個の数全体とする。また、求めたい順位を $k=3$ とする。
• $X$ の要素が $1$ 個だけなら、それを答えとして終了する（比較は行わない）。
• そうでなければ、$X$ の要素から $1$ つを等確率で選んでピボット $p$ とし、$p$ を $X$ のほかのすべての要素と $1$ 回ずつ比較して、$p$ より小さい要素の集合 $L$ と大きい要素の集合 $R$ に分ける（このとき比較は $|X|-1$ 回行われる）。
• $|L|=k-1$ なら $p$ を答えとして終了する。
• $|L|\ge k$ なら、$X$ を $L$ に置き換えて（$k$ はそのまま）最初の手順に戻る。
• $|L|\le k-2$ なら、$X$ を $R$ に、$k$ を $k-|L|-1$ に置き換えて最初の手順に戻る。

ピボットの選択は毎回独立に行われるものとする。このアルゴリズムが終了するまでに行う比較の回数の期待値を求めよ。

互いに異なる $7$ 個の実数からなる集合を、次の乱択クイックソートで昇順に並べかえる。

• 大きさ $2$ 以上の集合 $S$ を処理するときは、$S$ の要素から $1$ 個をピボット $p$ として等確率で選ぶ。$p$ を $S$ のほかのすべての要素とそれぞれちょうど $1$ 回ずつ比較し、$S$ を $p$ より小さい要素の集合 $S_{-}$ と $p$ より大きい要素の集合 $S_{+}$ に分ける。そのあと、$S_{-}$ と $S_{+}$ をそれぞれ同じ方法で処理する。
• 大きさ $0$ または $1$ の集合を処理するときは、何もしない（比較を行わない）。

ピボットの選択はそれぞれ独立に行うものとする。最初の集合 $7$ 個全体を処理し始めてから終わるまでに行われる比較のうち、小さい方から $3$ 番目の要素がかかわる比較の回数の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

• キーのハッシュ値を $h$ とし、スロット $h,h+1,h+2,\dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
• $1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

互いに異なる $8$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[8]$ の最大値と最小値を、次のアルゴリズムで同時に求める。

• 最初に $M\leftarrow A[1]$, $m\leftarrow A[1]$ とする。
• $i=2,3,\dots ,8$ の順に、次の操作を行う。
• まず $A[i]$ と $M$ を比較する。$A[i]>M$ ならば $M\leftarrow A[i]$ とし、この $i$ についての操作を終える（$m$ とは比較しない）。
• $A[i]<M$ ならば、続けて $A[i]$ と $m$ を比較する。$A[i]<m$ ならば $m\leftarrow A[i]$ とする。

配列の並び方は $8!$ 通りのどれも同様に確からしいとする。このアルゴリズムで行われる要素どうしの比較（$A[i]$ と $M$ の比較、$A[i]$ と $m$ の比較）の回数の期待値を求めよ。

互いに異なる $6$ 個の実数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の列はそのまま返す。
• 長さ $k\ge 2$ の列は、前半の $\lceil k/2\rceil$ 個と後半の残り $\lfloor k/2\rfloor$ 個に分け、それぞれを再帰的に昇順に並べかえてから、次の手続きで併合する。
• 併合の手続き: 昇順に並んだ $2$ つの列 $P,Q$ が与えられたとき、どちらも空でない間は、$P$ の先頭と $Q$ の先頭を $1$ 回比較し、小さい方を取り出して出力の末尾に加える。一方の列が空になったら、もう一方の列に残っている要素を、比較を行わずにそのまま順に出力の末尾に加える。

入力の $6$ 個の数の並び方は $6!$ 通りすべてが等確率で現れるとする。このマージソート全体で行われる要素どうしの比較回数の期待値を求めよ。

互いに異なる $8$ 個の数を並べた配列を、次のマージソートで昇順に並べかえる。

• 長さ $1$ の配列はそのまま返す。
• 長さ $2k$（$k$ は正の整数）の配列は、前半 $k$ 個と後半 $k$ 個に分け、それぞれを再帰的にこのマージソートで並べかえたあと、次の「マージ」で $1$ つの昇順の列にまとめる。
• マージ: 昇順に並んだ 2 つの列の先頭どうしを $1$ 回比較し、小さい方を取り出して出力の末尾に加える。これを一方の列が空になるまで繰り返し、空になったら、もう一方の列に残っている数を比較せずにそのまま出力の末尾に加える。

入力の $8$ 個の数の並び方は $8!$ 通りすべてが等確率で現れるものとする。このとき、ソート全体で行われる数どうしの比較回数の期待値を求めよ。

互いに異なる $6$ 個の実数を並べた配列 $A[1],A[2],\dots ,A[6]$ から、最大値と最小値の両方を次のアルゴリズムで求める。

• 最初に $mx=A[1]$、$mn=A[1]$ とする。
• $i=2,3,\dots ,6$ の順に、次の操作を行う。
• まず $A[i]$ と $mx$ を比較する。$A[i]>mx$ であれば $mx=A[i]$ とし、この $i$ についての操作を終える。
• そうでなければ、$A[i]$ と $mn$ を比較し、$A[i]<mn$ であれば $mn=A[i]$ とする。

$6$ 個の数の並び方は $6!$ 通りすべてが等確率 $\frac{1}{6!}$ で起こるとする。このアルゴリズムで行われる要素どうしの比較の回数の期待値を求めよ。

$p$ を素数、$r$ を正の整数とし、${\mathbb{F}}_p=\{0,1,\dots ,p-1\}$ を $p$ を法とする剰余体とする。キーの集合を $U={\mathbb{F}}_p^r$ とし、$\mathbf{a}=(a_1,\dots ,a_r)\in {\mathbb{F}}_p^r$ に対してハッシュ関数 $h_{\mathbf{a}}:U\to {\mathbb{F}}_p$ を
$$h_{\mathbf{a}}(\mathbf{x})=a_1{x}_1+a_2{x}_2+\cdots +a_r{x}_r({\mathbb{F}}_p\text{での計算})$$
で定める。ただし $\mathbf{x}=(x_1,\dots ,x_r)$ である。

$n$ 個の相異なるキーからなる集合 $S\subseteq U$ を固定し、$\mathbf{a}$ を ${\mathbb{F}}_p^r$ の $p^r$ 個の元から一様ランダムに選ぶ。各 $j\in {\mathbb{F}}_p$ について、バケット $j$ に入るキーの個数を
$$N_j=\left|\{\mathbf{x}\in S:h_{\mathbf{a}}(\mathbf{x})=j\}\right|$$
とおく。このとき
$$E\left[\sum _{j\in {\mathbb{F}}_p}{N}_j^2\right]=n+\frac{n(n-1)}{p}$$
が成り立つことを証明せよ。