回答編集履歴
1
無作為抽出であることに言及
answer
CHANGED
|
@@ -1,6 +1,6 @@
|
|
|
1
|
-
このm部分集合に特定の要素が属する確率
|
|
1
|
+
無作為抽出した場合、このm部分集合に特定の要素が属する確率を数学的に求めると**m/n**(※)なので、すべての要素に対して、部分集合に属する確率がm/nであれば証明ができることになります。
|
|
2
2
|
|
|
3
|
-
(※)全パターンはnCm、特定の要素(
|
|
3
|
+
(※)全パターンはnCm、特定の要素(xとする)が属するパターンは、xを除いた(n-1)個から、xとともに属する(m-1)個を選ぶ組み合わせに等しいので、(n-1)C(m-1)=(m/n)×nCm。よって確率は{(m/n)×nCm}/nCm = **m/n**
|
|
4
4
|
|
|
5
5
|
再帰の繰り返しにより、(0, n-m)に到達し、これは空集合を返します。そして(1, n-m+1)から要素の選定が始まります。これから、n-m+1以下の要素aについては、RANDOMでaが1回でも選ばれれば部分集合に入ります。この確率を直に求めるのは難しいので、「aが1回も選ばれない」確率を求めます。
|
|
6
6
|
(1, n-m+1)の時、aが選ばれない確率は(n-m)/(n-m+1)
|