Tuesday, November 10, 2015

Puzzles, Maths and Algorithms: Innocents and Criminals: Finding Minority Entity

Innocents and Criminals: Finding Minority Entity

Problem: There are two types of people in a particular city, innocents and criminals. All you know is that innocents are in majority and would like to get rid of criminals and criminals would like to protect themselves from persecution. You can ask any number of questions, with yes/no type answer, from any person in the city. Propose an algorithm which requires asking the minimum number of questions.

Read full article from Puzzles, Maths and Algorithms: Innocents and Criminals: Finding Minority Entity

Puzzles, Maths and Algorithms: Math Magician

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, such that each box contains atleast one card. A member of audience draws two cards from two different boxes and announces the sum of the number on those cards. Given this information magician locates the box from which no card has been drawn. How many ways are there to put the cards in the boxes so that the trick works.
Source: International Maths Olympiad 2000

Answer: 12

Solution:
We split the possible arrangements into two different cases.

Case 1: Assume that there exists an i such that i, i+1, i+2 go in different box (say wrb). Since, (i+1) + (i+2) = i + (i+3) => (i+3) should go in white box. Similarly i-1 should go in blue box. Since the pattern repeats without much choice so it boils down to assigning different boxes to first three cards. Total of 6 ways.

Case 2: Assume that no three neighbors are put in different boxes. Let card 1 be in white box. Let i be the smallest card to go in red box (such that i > 2). Let j be the smallest card to go in blue box (such that j < 100). Let j > i.

==> i-1 is in white box.
==> i + j = (i-1) + (j+1)
==> j+1 is in white box.

==> i + (j+1) = (i+1) + j
==> i+1 is in blue box
==> j = i+1

This violates the main assumption from both ends i-1, i, i+1 are in different boxes and also i, i+1, i+2, hence j = 100. so that j+1 doesn't exist and both 99 and 98 belong to same box other than blue.

also (i-1) + 100 = i + 99 => card 99 is in red box => card 98 is in red box

but 2 + 99 = 1 + 100 => 2 is red. in general assume that there exists a card c (>1) and it belongs to white box and also c-1 to white box. => c + 99 = (c-1) + 100. which leads to failure of the trick. Assuming cards surrounding c are red. c + 99 = c-1 + 100 => failure of trick. Hence no such c exists and c=1 is the only card in white box.

hence the combination looks like wrrrr.........rrrrrb i.e. one card (value 1) in white box, one card (value 100) in blue box and rest all cards in red box. There are six ways of such arrangements.

Read full article from Puzzles, Maths and Algorithms: Math Magician

Puzzles, Maths and Algorithms: Number and Age of David's Kids

Problem: The product of the ages of David's children is the square of the sum of their ages. David has less than eight children. None of his children have the same age. None of his children is more than 14 years old. All of his children is at least two years old. How many children does David have, and what are their ages?

Read full article from Puzzles, Maths and Algorithms: Number and Age of David's Kids

Puzzles, Maths and Algorithms: Unbiased Coin Tossing

Puzzles, Maths and Algorithms: Unbiased Coin Tossing
Given a biased coin, with probability of Heads equal to x. How to do unbiased coin tossing?

Lets define an event, E as tossing the biased coin twice. The possible outcomes with probabilities is as follows

P(h,h) = x^2
P(h,t) = x(1-x)
P(t,h) = x(1-x)
P(t,t) = (1-x)^2

The event h,t or t,h are equi-likely, without any bias we can call that if Event h,t occurs it means head, t,h means tails but if h,h or t,t occurs we repeat the experiment.

Try to find the expected number of coin toss that would be required to call heads or tails?

Let expected coin toss be e.

Probability that we get outcome in 1st event is 2x(1-x)
Total number of coin toss would be 2
Probability that we get no outcome in 1st event is [1 - 2x(1-x)]
Total number of coin toss would be 2 + e (we wasted 2 coin toss and still we expect e)

==> e = 2 * 2x(1-x) + (2+e) * [1 - 2x(1-x)]
==> e = 4x(1-x) + 2 - 4x(1-x) + e - 2ex(1-x)
==> e = 1/ [x(1-x)]

so for x = 1/2, e = 4
for x=2/3, e = 4.5
for x=1, e = INF (as expected, because all we get is chain of h h h h h)

What is the probability that there wont be any outcome in e coin tosses (expected outcomes)?

p = prob of e heads + prob of e tail
==> p = x^e + (1-x)^e

To find a bound on this p in polynomial terms can be done by using binomial expansion and Newtonian series is out of the scope of this blog. But some number crunching is.

For x = 1/2, e = 4, p = 0.125
For x = 2/3, e = 4.5, p = 0.168
For x = 3/4, e = 5.33, p = 0.216
For x = 0.99, e = 101, p = 0.362

This tells us that probability that outcome comes is quite good even for high coin biases.

How can we improve on the expected number of coin tosses?

In above method, we say that HT or TH terminates experiment. and continue the experiment a fresh when the outcome is HH or TT.

We can further combine outcome of two such events to increase the probability of outcome e.g. say HH TT => heads and TT HH means tails.

How much expected coin tosses are we doing in this case?

Read full article from Puzzles, Maths and Algorithms: Unbiased Coin Tossing

Puzzles, Maths and Algorithms: Stick Breaking

Puzzles, Maths and Algorithms: Stick Breaking
Problem Set 1: Given a stick of length 1 meter. It is cut into two parts randomly.

Problem 1a: What is the expected length of the smaller stick?
Problem 1b: What is the expected length of the bigger stick?

Problem Set 2: Given a stick of length 1 meter. It is cut into three parts randomly.

Problem 2a: What is the expected length of the smallest stick?
Problem 2b: What is the expected length of the largest stick?
Problem 2c: What is the expected length of the stick with second smallest (or second largest) length?
Problem 2d: What is the expected length of the middle stick (stick that is between the two cuts)?
Problem 2e: What is the probability that the three sticks would form a triangle?
Problem 2f: What is the probability that the three sticks would form a right angle triangle?
Problem 2g: What is the probability that the three sticks would form an equilateral triangle?

Problem Set 3: Given a stick of length 1 meter. It is cut into two parts randomly. Then bigger stick is picked and is again cut into two parts randomly.

Problem 3a: What is the expected length of the smallest stick?
Problem 3b: What is the expected length of the largest stick?
Problem 3c: What is the expected length of the stick with second smallest (or second largest) length?
Problem 3d: What is the expected length of the middle stick (stick that is between the two cuts)?
Problem 3e: What is the probability that the three sticks would form a triangle?
Problem 3f: What is the probability that the three sticks would form a right angle triangle?
Problem 3g: What is the probability that the three sticks would form an equilateral triangle?

Generalized Cut Problem: Find the solution to problem 2a-2c, 3a-3c for n-1 cuts.

Let us work out solution for 1a. Smaller stick has length x which is uniformly distributed in the range [0,0.5]. The probability distribution of x is p(x) = 1 / [1/2-0] = 2. Yes it is a pdf, ∫ ₀^0.5p(x)dx = 1. The expected length of the smaller stick is E[x] = ∫ x p(x) dx = ∫ ₀^0.52xdx = 1/4.

2a) Let us work out solution for 2a. Let two cuts are at distance x,y from one end. Let x < y. So the three sticks are of length x, y-x, 1-y. Let z = min(x,y-x,1-y) represent the minimum length of the stick. Let Pr(z>a) indicate the probability that min length stick has length greater than a.

=> Pr(z>a) = 2 * Pr(x>a, y-x>a, 1-y>a) = Pr(x>a, a+x < y < 1-a)

Note multiplication by 2 is for the other case (x > y). Since a+x< y < 1-a, we get x < 1-2a. Also setting x =a, we get a < 1/3 (which is obvious).

=> Pr(z > a) = 2 ∫ _a^1-2a ∫ _a+x^1-adxdy = (1-3a)².

So we get Pr(z<=a) = 1-Pr(z>a). And Pr(z=a) = derivative of Pr(z<=a) at a = 6(1-3a).

=> E[a] = ∫ ₀^1/36a(1-3a)da = 1/9

2b) We can do a similar derivation for z = max(x,y-x,1-y) to get the expected max length. It would be slightly more complicated. Unlike above, we compute here Pr(z< a)

=> Pr(z < a) = Pr(x < a, y-x < a, 1-y < a) = Pr( 1-2a < x < a, 1-a < y < x + a).

We need to be careful here are respect constraints like x > 0, x < y, y < 1. To ensure these constraints are respected. Pr(z < a) is broken into three cases, Case 1: a < 1/2. Case 2: a >= 1/2, 0 < x < 1-a, Case 3: a >= 1/2, 1-a < x < a. Then we have to take differential of obtained Pr(z < a) to get Pr(z=a). [Dont mix terms from the three cases].

Integrate the first case from [1/3 to 1/2]. Second and third case from [1/2 to 1]. We will see the desired output as 1/2+1/9=11/18. (Don't forget to multiply by 2 to cover for x > y case).

2c) It would be easy to obtain: 1 - (2a) - (2b) = 1 - 1/9 - 1/2 - 1/9 = 1/2 - 2/9 = 5/18.

2d) Since there are no constraints, expected length of middle cut is 1/3

2e) For triangle, we require satisfaction of three inequalities
x + y - x > 1-y,
x + 1- y > y - x,
y - x + 1 - y > x
Apart from the implicit x < y inequality.

=> 1/2 < y < x + 1/2, x < 1/2

So x follows a pdf of P(x) = 2. y satisfied the range with probability x. So the probability of triangle formation is ∫ ₀^1/22 x dx = 1/4.

2f) There are discrete stick lengths, e.g. (3/12, 4/12, 5/12) that satisfy this property. There are countably infinite, yet the area encapsulated by them is 0.

Problem set 3 is slightly more complicated. Let us work out 3a).

Let the first cut is at length x from shorter side (x < 1/2). Now from the stick of length (1-x), we make a cut at random of length y. Let y < (1-x)/2. If x is the shortest stick then x < y => x < 1/3.

Case 1: 1/3 < x < 1/2, 0 < y < (1-x)/2 => y is the shortest stick

Case 2: 0 < x < 1/3
Case 2a: 0 < y < x => y is the shortest stick
Case 2b: x < y < (1-x)/2 => x is the shortest stick

We also note that P(x) = 2 (a uniform distribution in [0,1/2]), P(y) = 2/(1-x) (a uniform distribution in [0, (1-x)/2]).

So the Expected min length = ∫ _1/3^1/2 ∫ ₀^(1-x)/2 4y/(1-x) dx dy + ∫ ₀^1/3 ∫ ₀^x 4y/(1-x) dx dy +
∫ ₀^1/3∫ _x^(1-x)/24x/(1-x) dx dy = 15/16 - 2 log(3/2)

For Generalized problem read David and Nagaraja's Order Statistics (pp. 133-135, and p. 153)

The solutions through Monte-Carlo simulations. Following python code solves problem set 2 and 3.

from random import random
def prob2():
    niter = 100000
    n, ntri, nrtri = 0.0, 0, 0
    lsmall, llarge, lmid, lcenter = 0, 0, 0, 0

    while n < niter:
        n += 1
        p = random()
        q = random()
        x = min(p, q)
        y = max(p, q)

        l1 = x
        l2 = y-x
        l3 = 1-y

        mn = min(l1, l2, l3)
        mx = max(l1, l2, l3)
        md = 1 - mn - mx
        lsmall += mn
        llarge += mx
        lmid += md
        lcenter += y

        if l1 + l2 > l3 and l1 + l3 > l2 and l2 + l3 > l1:
            ntri += 1

        if mn**2 + md**2 == mx**2:
            nrtri += 1

    print 'min len:', lsmall/n
    print 'max len:', llarge/n
    print 'mid len:', lmid/n
    print 'center stick len', lcenter/n
    print 'triangle prob:', ntri/float(n)
    print 'right triangle prob:', nrtri/float(n)

def prob3():
    niter = 100000
    n, ntri, nrtri = 0.0, 0, 0
    lsmall, llarge, lmid, lcenter = 0, 0, 0, 0

    while n < niter:
        n += 1
        p = random()
        q = random()

        l1 = 0.5 * (1-p)
        l2 = 0.25 * (1+p) * (1-q)
        l3 = 0.25 * (1+p) * (1+q)

        mn = min(l1, l2, l3)
        mx = max(l1, l2, l3)
        md = 1 - mn - mx
        lsmall += mn
        llarge += mx
        lmid += md
        lcenter += (l2+l3)/2

        if l1 + l2 > l3 and l1 + l3 > l2 and l2 + l3 > l1:
            ntri += 1

        if mn**2 + md**2 == mx**2:
            nrtri += 1

    print 'min len:', lsmall/n
    print 'max len:', llarge/n
    print 'mid len:', lmid/n
    print 'center stick len', lcenter/n
    print 'triangle prob:', ntri/float(n)
    print 'right triangle prob:', nrtri/float(n)

Read full article from Puzzles, Maths and Algorithms: Stick Breaking

Monday, November 9, 2015

Probability Puzzle - PrismoSkills

Puzzle: If the probability of observing a car in 20 minutes on a highway is 609/625, what is the probability of observing a car in 5 minutes (assuming constant default probability)?

Solution: Probability of not seeing the car in 20 minutes = (1 - 609/625) = 16/625
If P be the probability of not seeing the car in 5 minutes, then PxPxPxP = 16/625
=> P = 2/5
=> Probability of seeing the car in 5 minutes = (1 - 2/5) = 3/5

Read full article from Probability Puzzle - PrismoSkills

选择爱人的数学方法（经典秘书问题） - tenos - 博客园

选择爱人的数学方法（经典秘书问题）

Kepler（开普勒，1571年12月27日－1630年11月15日），德国天文学家、数学家，十七世纪科学革命的关键人物。

这样一位伟大的人物在1611年遇到一个问题，他的夫人患匈牙利斑疹伤寒（Hungarian spotted feve）过世，为了照顾孩子、打理家务，Kepler 需要重新寻找一位夫人。身为严谨的科学家，他认真记录下了"面试"11位夫人"候选人"的过程。

第一位，"口臭"，Kepler写到。

第二位，"养尊处优"。

第三位："已经许配给一个有私生子的人，太复杂了"。

第四位："身材高挑，气质不凡"。

不过，Kepler 想看看第五个，因为有人告诉他，第五位女孩儿集"谦虚、节俭、勤奋..."等优点于一身。于是，Kepler 犹豫了，而且犹豫了很长时间，以至于第四位和第五位女孩儿都不耐烦地离开了。

第六位是一个"衣着华丽的大小姐"，这把Kepler吓了一跳，他有点担心高昂的婚礼费用。

第七位女孩儿很迷人，Kepler 也很喜欢她。由于没看完这11位"候选人"，Kepler 心有不甘。他让这位女孩儿等他看完"候选人"再做决定。不愿意等人的第七位女孩儿也离开了。

第八位女孩儿，Kepler 没怎么关心。

第九位女孩儿"体弱多病"；第十位女孩儿有着"对于没什么要求的普通人"也没办法接受的体型；最后一位女孩儿，还是个小姑娘，也不适合。

11位"候选人"都看完了，一个也没有约成。Kepler 开始想，哪里出错了？

Kepler 所需要的，是优化策略，一种不能保证成功但能将失望降至最低的方法。数学家们觉得，我们能算出这样的公式来。本文地址

如果你有自己的候选列表，爱人也好，约会也好，工作也好，这方法都管用。规则很简单：只要你的选择有限，你可以做一个列表，然后挨个来。再一次声明，不总能成功。但对数学家来说，足够了。

这个问题甚至有个名字：(开普勒的)婚姻问题。后来，又被衍生为经典秘书问题（Classic Secretary Problem）。比如，你有20个候选人要逐一面试，在面试之后，你必须决定要不要。要，选择结束；不要，那就喊下一位。不能回头。一旦决定聘用，问题结束。

根据马丁・加德纳在1960年的说法，最好的办法是，先面试前36.8%的候选人，但不录用他们。在此之后，一旦遇到比前面这36.8%里最好的还好的，立马录用。

为什么是36.8%呢？这个答案牵扯到e，1/e=0.368（关于这个概率的证明可以参考维基百科）。很显然，这个公式经过了无数次的验证。尽管它不能保证结果最优，但你有36.8%的机会。对于11个"候选人"来说已经足够了。

如果，当时Kepler 用了这个公式，会怎样呢？11的36.8%的是4，所以他要pass掉前四位候选人，从第五位开始，只要比前四位好，Kepler 就应该求婚。也就是，经过一番折腾后，Kepler 会和第五位女孩儿结婚。(你还见记得第五位是谁吗？)

如果Kepler 当时知道这个公式(这也是当今数学上最优停止的一个例子)，他便能省去后后面一批人的约会了。

Read full article from 选择爱人的数学方法（经典秘书问题） - tenos - 博客园

Massive Math Stuff