I have a random number machine generator that is very good at generating integers between 1 and 256, inclusive, with equal probability. However, right now, I want to produce a random number between 1 and n, inclusive, so I do the following:
-
I use my machine to generate a number between 1 and 256. Call this a.
-
I take a and divide it by n to get remainder r. If r \neq 0, then I record r as the randomly generated number. If r=0, then I record n instead.
Note that this process does not necessarily produce all numbers with equal probability, but that is okay. I apply this process twice to generate two numbers randomly between 1 and 10. Let p be the probability that the two numbers are equal. What is p \cdot 2^{16}?