To distinguish the input from the output, let "IP" denote the event that the input is prime and "IC" denote the event that the input is composite, while "OP" denotes the event that the output is "Prime" and "OC" denotes the event that the output is "Composite". In conditional probaility notation:
P( OP | IP ) = 1 | P( OC | IP ) = 0 |
P( OP | IC ) = p | P( OC | IC ) = 1 - p |
Suppose the proportion of primes to composites given as input to the algorithm is ( q : 1 - q ), so P( IP ) = q and P( IC ) = 1 - q (these are called "prior probabilities"), then
P( IP | OP ) = P( IP and OP ) / P( OP )
= P( IP ) * P( OP | IP ) / [ P( IP and OP ) + P( IC and OP ) ]
= P( IP ) * P( OP | IP ) / [ P( IP ) * P( OP | IP ) + P( IC ) * P( OP | IC ) ]
= q * 1 / [ q * 1 + ( 1 - q ) * p ]
= q / ( q + p - pq )
Similarly, P( IP | OC ) = q * 0 / [ q * 0 + ( 1 - q ) * ( 1 - p ) ] = 0