Tuesday, January 20, 2009

Ballot problem with lattice pts




I was discussing the Ballot problem with Dr. Clark and he showed my how the reflection principle can solve this problem in seconds. The Ballot problem simply stated is counting the ballots so that one candidate is always ahead of other. Let the candidates be C and D, where C gets c votes and D gets d votes. Therefore total number of votes is c+d. Also let d > c i.e candidate D remains ahead of C through out the counting. The probability that D remains ahead of C is a surprisingly compact result of (d-c)/(d+c).
To solve using lattice path reflection one need to only observe that the lattice path never touches the line y =x which passes through lattice pts. As D is ahead of C the first lattice pt is (1,0). The number of such path to lattice pt (c,d) is binomial (c+d-1,c). This however includes path which do across or touch line y =x. Excluding those by reflection principle give binomial(c-1+d,d). Hence probability is
(binomial(c+d-1)-binomial(c-1+d,d))/binomial(c+d,c) = (d-c)/(d+c).

0 Comments:

Post a Comment

<< Home

Site Meter