Tuesday, July 20, 2010

Probability and Lagrange Identity

20th July, 2010
Find the probability of meeting A and B.

Given a Cartesian plane as shown in the figure. Consider person A, initially at the origin and person B initially at the point (n, n) wants to meet. At each point (x, y), each one flips a coin and decides the next move; A moves up side on ‘Head’ and right side on ‘Tail’ to the next point, whereas B moves downward on ‘Head’ and left side on ‘Tail’ to the next point. Find the probability that they will meet within the square lattice.
Say each point is one unit length. If A and B met, they must travel n points on total by both and meet on the diagonal at some point P. Let us assume, A traveled k units then B must travel (n – k) units. Hence they meet at point P(i, n − i), where 0 ≤ k ≤ n.
A has nCk possible ways from the origin where as B has nC(n – k) possible ways from point (n, n). Per multiplication principle, the total possible ways are (nCk) x ( nC(n – k) ). However, k can range from 0 to n. Summation of the product over possible values of k will give us the number of ways A and B can meet.
i.e. No of ways to meet = Sigma [(nCk) x ( nC(n – k) )], where 0 ≤ k ≤ n.
Simplified using Pascal identity, = Sigma [(nCk) x (nCk)], where 0 ≤ k ≤ n. Since, nCk = nC(n-k)
= Sigma [(nCk)]2 , where 0 ≤ k ≤ n.
= 2nCn, Lagrange Identity
We are half done. What would be the total sample place? For each person A and B, it is possible to take 2n ways (sum of binomial coefficients). It means total sample space is 22n. So, it is easy to find the probability.

No comments: