## 2008年12月21日 星期日

### 估中有獎

(e.g. 估中的話在 MD Academic seminar 中有優先座位選擇權 ^^)

---------------------------------------------------------------------------------------------

Construct a strictly increasing function f(x) from the real line to the open interval (0, 1).
For example, f(x) can be

or (the latter is the cumulative distribution of a normal random variable), etc. Can you create another example for f(x)?

The strategy is simple:

If the number you picked is x, guess that it is larger with probability f(x).

Here' s how you can do it "practically": After you see the number, say x, create a coin which has probability f(x) to show up head and 1-f(x) to show up tail, and then flip it. Then you guess "x is bigger" if head shows up, and guess "x is smaller" if tail shows up.

Suppose the number I wrote are a and b, where a < b, then the probability that you guess correctly is

which is bigger than 1/2 as f(b)>f(a). ( Verify the formula above!)

The interesting thing in the above strategy is:
Even if you look at the number x, you do not know whether you'll guess "larger" or "smaller" until you've flipped the coin. This is a so called "Probabilistic Strategy".

p.s. 此問題與 MD Academic seminar 無關，如有雷同，實屬巧合。