2
$\begingroup$

Thought this would be a nice puzzle for some. :)

First, I take a random number from 1 to 10, then take that number and multiply it by 5, we'll call this result 'threshold'. Then I take another new random number from 1 to 100, and see if it is equal or lower than the 'threshold' number.

pseudocode:

th = rand(10) * 5; res = rand(100); if (res <= th) return TRUE; 

Is this the simplest way to calculate this? I'm thinking one of rand(500) or rand(1000) would be the same, but I can't get my probability formulas to work.

  • 6
    Equivalent would be "if (rand(1000) <= 275) return TRUE;" as the probability of your program returning TRUE is 27.5%.2011-08-25

2 Answers 2

2

Others have already given the answer, but I thought it might be useful to show in some detail how to arrive at it:

Let $X \in \{1,\dotsc,10\}$ be the first random variable, and let $Y \in \{1,\dotsc,100\}$ be the second. The probability that $Y \le 5X$, given that $X$ has the value $x$, is

$\mathrm P(Y \le 5X \;|\; X=x) = \mathrm P(Y \le 5x) = \frac{5x}{100}.$

$X$ takes all values with equal probability, so, for any given $x \in \{1,\dotsc,10\}$, $\mathrm P(X=x) = \frac{1}{10}$. Therefore, the probability that $X=x$ and $Y \le 5X$ is

$\mathrm P(Y \le 5X \text{ and } X=x) = \mathrm P(Y \le 5X \;|\; X=x)\; \mathrm P(X=x) = \frac{5x}{100} \frac{1}{10} = \frac{5x}{1000}.$

To get the marginal probability that $Y \le 5X$, we then simply need to sum over all possible values of $X$:

$\mathrm P(Y \le 5X) = \sum_{x=1}^{10}\; \mathrm P(Y \le 5X \text{ and } X=x) = \sum_{x=1}^{10}\frac{5x}{1000}.$

The final step is either remembering the formula for the sum of an arithmetic progression or just working it out by hand:

$\sum_{x=1}^{10}\frac{5x}{1000} = \frac{5}{1000} \sum_{x=1}^{10}\; x = \frac{5}{1000} (1 + \cdots + 10) = \frac{5}{1000} 55 = \frac{275}{1000} = \frac{11}{40}.$

Thus, the probability that your pseudocode returns true is $\frac{275}{1000} = \frac{11}{40}$, and so it can be replaced by

if (rand(1000) <= 275) return TRUE; 

or even by

if (rand(40) <= 11) return TRUE; 
0

The possibility of res being less than or equal to th is th / 100. If you add 5, 6, 7,... 50, or all the possibilities of th, you get 1265. Divide that by the number of possible values of th (46), and you get 27.5/100 as the probability that res <= th. Or take (5+50) / 2 / 100.

  • 0
    Oops! You're right.2011-08-27