[Ramdomized algorithm] 用粒爛骰 (unfair dice) 答mc (equal prob.)

是咁的,你唔識做mc卷某一題,你想uniform randomly揀ABCD其中一個做答案。

你手頭上有粒爛骰 (unfair dice),已知擲到某幾面既概率特別高,可以點搞?

有個將unfair coin變成fair coin既algorithm,好簡單:

  1. 掟兩次銀仔
  2. 兩次結果一樣既話,重覆1
  3. Return 第一次掟銀仔既結果

用呢個原理,將粒爛骰變成一個爛銀仔既問題,例如將123當係公,456當字。

應用返上邊既algorithm,你個algorithm每run一次,就拎到一個random bit,兩個random bit加埋就可以表示4種可能性,例如ABCD。

個algorithm run得快唔快視乎出兩邊結果既probability有幾極端,兩邊愈接近0.5愈快。

Recommendations

Last modified: 2016-12-06 14:45:57
Powered by Simple Blog