Shatakjain2901's blog

By Shatakjain2901, 6 years ago, In English

can anyone tell me how does the probability in last cast when both are 0 becomes m-1/(2*m)?? i have seen a code having this

if(!a[i] && !b[i]) { v.push_back(make_pair((((m-1)%M)*num)%M, (den*((2*m)%M))%M) ); den = (den*(m%M))%M; } somebody plz me how is the probability calculated in this case?

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You independently select two numbers uniformly at random from {1, 2, ..., m}. The probability they are equal is 1 / m, since after you select the first you have a 1 / m chance of selecting the same value for the second.

So the probability they are different is 1 - 1 / m = (m - 1) / m. In the case they are different by symmetry it is equally likely that the first is larger than the second and that the second is larger than the first. So the probability the first is larger than the second becomes (m - 1) / 2m.

»
6 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The characters atA[i] and B[i] must be different. (with A[i] > B[i])

There are choose(m, 2) = m(m - 1)/2 ways of choosing two different characters.

How many ways are there to choose two characters in general ?m x m = m^2

Probability = Number of ways of choosing different characters/ Number of ways of choosing characters

= (m(m - 1)/2) / m^2 = (m - 1)/2m

This is my implementation. It may be useful for you.