VNQF brainteasers collection

[Khoa Tran]

Regarding martingales, I have another fun problem. If the Monty Hall Problem is too popular, this one can provide more fun for an interview.

23. (Likelihood Ratio Test paradox?) a. Let be a sequence of independent & identically distributed (iid. for short) random variables. You don't know it's true distribution but suppose you know that the probability density function is either p(x) or q(x) (if x is a vector then p and q are joint density functions). In statistics, the ratio

is known as a likelihood ratio. After each experiment, you update your . The ratio is likely to be small or large, according as the tru probability density function is p or q, and is used as a statistical test to determine the true distribution.

However, show that if p is the true density, is a martingale.

b. If it is a martingale then why is it used as a statistical test? What's wrong?

You can run a simple simulation here (Matlab code) to see what happens.

%A deformed coin with 70% head and 30% tail
%You know that it's deformed
%You guess that it's either: (70% head, 30% tail) or (30%head, 70% tail)
%Now run the likelihood ratio test for 100 times
ratio=1;
for i=1:100
    r = rand;
    if r<0.7 %if head
        ratio = ratio*0.3/0.7;
    else %if tail
        ratio = ratio*0.7/0.3;
    end
end
ratio

You will "always" get almost 0 (say, of order ).

[Khoa Tran]

Có lẽ sau chiêu sư tử hống (link) của Kim Mao Sư Vương Ngô Quang Hưng, quần hùng lăn ra giãy đành đạch, không còn ai hứng thú thi triển võ công nữa. Thôi thì chúng ta lại viết tập mới với mấy câu hỏi dễ thương hơn.

1. Let be a Brownian motion. What is ?

2. How do you compute

3. (from YADD) After each second, a bacteria may: either die, or survive, or split into 2, or split into 3 (each with probability 0.25). Suppose that there's 1 insect at the beginning of the day, what is the probability that the whole population dies at the end of the day?

4. (Programming) Given 2 variables a and b. How do you swap the values of a and b without using any extra memory?

5. (Blog KHMT) Giả sử

(mũ x đến vô cùng). Vậy x bằng bao nhiêu? Ví dụ, ta có thể lý luận như sau. Dễ thấy rằng . Do đó , hay . Nhưng nếu thì, theo lý luận trên, cũng dẫn đến . Sao lạ thế? à?

[shinichi9htv]

[***] Có 124 con bài khác nhau và 2 nhà toán học. 1 người thứ 3 cầm lấy bộ bài, lấy ra 5 con bất kì, đưa cho 1 nhà toán học. Ông này ngồi xem xem tính toàn một thôi một hồi, đút lại 1 con vào bộ bài và xếp 4 con ngay ngắn trên bàn. Nhà toán học kia đứng lên nhìn 4 con bài, rồi tìm ra con bài thứ 5 còn lại. Hỏi 2 nhà toán học đã làm thế nào?

(Restated by Khoa)