Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Conditional Probability at it's finest

  1. Feb 15, 2008 #1
    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.

    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)


    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.
  2. jcsd
  3. Feb 17, 2008 #2


    User Avatar

    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 text book. Hope this is not a homework.
    Last edited: Feb 17, 2008
  4. Feb 18, 2008 #3
    Yes it's a homework but it has already been turned in and graded. Any more responses are appreciated.
  5. Feb 18, 2008 #4

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

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

    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.
    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.
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook