サンプリングアルゴリズムを証明する方法は？

Question

これは宿題に関する質問です。私たちが知っているように、このアルゴリズムは、等しい確率で範囲内のすべての整数を選択します。それを証明するのを手伝ってもらえますか？

Answer 1

1. 特定の番号を選択するチャンスはm/nです。
2. この番号を選択した場合、同じ問題が発生しますが、n' = n - 1とm' = m - 1となります。そうでなければ、同じ問題がありますが、n' = n - 1とm' = mです。

あなたのアルゴリズムはこのアイデアの実装です。

また、仮定1を証明する必要がありますが、おそらく自分自身で行うことができます。