Probability and Lagrange Identity

20^th 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.
Solution:

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)]² , 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 2ⁿ ways (sum of binomial coefficients). It means total sample space is 2²ⁿ. So, it is easy to find the probability.