Conditional Probability at it's finest

[Somefantastik]

In an election, candidate A receives n votes and candidate B receives m votes, where n>m. Assume that in the count of the votes all possible orderings of the n+m votes are equally likely. Let Pn,m denote the probability that from the first vote on A is always in the lead. Find Pn,m.

[solution]
Pn,m = P(A gets n votes, B gets m votes | last vote to A)*(n/n+m) + P(A gets n votes, B gets m votes | last vote to B) * (m/m+n)

= Pn-1,m * (n/n+m) + Pn,m-1*(m/m+n)

From the formula, we have

Pn,1 = Pn-1,1 *(n/n+1) + Pn,0*(1/n+1) = (n/n+1)*Pn-1,1 + 1/(n+1)
P1,1 = 0

=> Pn,1 = (n-1)/(n+1)

and

Pn,2 = Pn-1,2*(n/n+2) + Pn,1*(2/2+n) = Pn-1,2*(n/n+2) + 2*(n-1)/(n+2)
P2,2 = 0

==> Pn,2 = (n-2)/(n+2)

Please explain this solution to me. The stuff in red is where I got lost.

 

[ssd]

This is a common method for 'random walk' type problems which are solved by difference equations. Pn,m is called 'steady state probability' and the corresponding equation is called ballance equation of transition. If you understand the first expression of Pn,m then it will not be difficult to understand how Pn-1,m and Pn,m-1 are eleminated. Go through the method of solving difference equations in any textbook. Hope this is not a homework.

 

[Somefantastik]

Yes it's a homework but it has already been turned in and graded. Any more responses are appreciated.

 

[D H]

Pn,m = Pn-1,m * (n/n+m) + Pn,m-1*(m/m+n)

Since this wasn't in red I assume you have no problem with this.

From the formula, we have
Pn,1 = Pn-1,1 *(n/n+1) + Pn,0*(1/n+1) = (n/n+1)*Pn-1,1 + 1/(n+1)

The first part of this statement results directly from substituting m=1 into the generic recursive relationship. If candidate B does not receive any votes then candidate A will always be in front. Thus Pn,0=1 for all n>0. The latter equality arises from this fact.
From this, the latter equality need this to make the latter part of the above statement.

P1,1 = 0

If candidate B receives as many or more votes than candidate A there will be some point at which candidate A is not in front. Thus Pn,m=0 for all n<=m.

=> Pn,1 = (n-1)/(n+1)

The recursive relationship suggests there might be a direct expression of the form
Pn,1 = f(n)/(n+1). Using this form in the recursive relationship,
f(n)/(n+1) = (n/(n+1))*(f(n-1)/n) + 1/(n+1)
from which
f(n) = f(n-1) + 1
In other words, f(n) = n+k where k is some constant. Since P1,1=0, f(1)=0 and k=-1, or
Pn,1 = (n-1)/(n+1)

You can verify this with recursion. The expression is obviously correct for n=1. Assuming its correct for n-1, you should be able to prove it is true for n.

The case m=2 is similar.