How can I calculate the probability of getting a number smaller than a previous random picked number?


I have a first independent experience where a set of n random numbers are picked from 1 to M.

(n <<< M)

From the picked numbers, I choose the smaller number.

Then, I repeat this experience again (independently).

How can I calculate the probability of this second number being smaller or equal than the first one?

Thanks in advance.

  • $\begingroup$ what do you mean by a minor number? $\endgroup$ – avz2611 Oct 24 '17 at 10:39
  • $\begingroup$ Sorry, English isn't my mother language. I meant to say: smaller number. $\endgroup$ – Pedro Simões Oct 24 '17 at 10:45
  • $\begingroup$ Not entirely sure I am following the procedure. If I have understood it, the two numbers are chosen in exactly the same way. If so, then the probability that the second is smaller is $.5$, by symmetry, if the process is continuous. otherwise it is $.5\times (1-p_{tie})$ where $p_{tie}$ denotes the probability that the two values coincide. $\endgroup$ – lulu Oct 24 '17 at 11:19
  • 1
    $\begingroup$ To illustrate, suppose my numbers are obtained by tossing a fair die. Then the probability of a tie is $\frac 16$. The probability that the second toss is strictly lower than the first is $\frac 12\times \left(1-\frac 16\right)=\frac 5{12}$. You can check this by listing all possible rolls. $\endgroup$ – lulu Oct 24 '17 at 12:02
  • 1
    $\begingroup$ Then the exact same computation goes through. Now $p_{tie}=2^{-256}$ so the probability you want is $\frac 12\times \left(1-2^{-256}\right)$ which is certainly very close to $.5$ (as $p_{tie}$ is very close to $0$). $\endgroup$ – lulu Oct 24 '17 at 12:29

If the numbers are drawn so there is zero probability of ties and all orders are equally likely, then the probability that the $n+1^{\text{th}}$ number drawn will be smaller than all of the previous $n$ numbers drawn is $\frac{1}{n+1}$, by symmetry

An equivalent approach counting the possible orders could calculate $\frac{1 \times n!}{(n+1)!}$ to give the same answer

If you already know the smallest number drawn so far, you could make a better estimate


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.