Register to reply

Conditional Probability at it's finest

by Somefantastik
Tags: conditional, finest, probability
Share this thread:
Somefantastik
#1
Feb15-08, 11:26 AM
Somefantastik's Avatar
P: 225
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.
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
ssd
#2
Feb17-08, 01:31 AM
P: 239
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.
Somefantastik
#3
Feb18-08, 07:33 AM
Somefantastik's Avatar
P: 225
Yes it's a homework but it has already been turned in and graded. Any more responses are appreciated.

D H
#4
Feb18-08, 08:08 AM
Mentor
P: 15,065
Conditional Probability at it's finest

Quote Quote by Somefantastik View Post
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.


Register to reply

Related Discussions
Conditional probability Precalculus Mathematics Homework 9
Conditional Probability Set Theory, Logic, Probability, Statistics 4
Conditional Probability Calculus & Beyond Homework 8
Conditional probability Calculus & Beyond Homework 0
Conditional Probability Set Theory, Logic, Probability, Statistics 7