4

Let us assume a pure random number generator generates a random number between the given range $[0,m]$ with equal probability.

Given $m_1$, let it generate a random number($r_1$) in the range $[0,m_1]$. Given $m_2$, let it generate a random number($r_2$) in the range $[0,m_2]$.

Now what is the probability that $r_1 + r_2 < K$ ( another number)?

How can I calculate this probability?

jkn
  • 5,129
  • 25
  • 53
Ravi Chandra
  • 141
  • 8
    Considering $X = (r_1, r_2)$ as a point in $\Bbb{R}^{2}$ may help you calculate the probability. – Sangchul Lee Aug 02 '13 at 12:23
  • 12
    "How can I calculate this probability?" By drawing the part $H$ of the line $x+y=K$ in the rectangle $R=(0,m_1)\times(0,m_2)$, computing the area of the triangle with a vertex at $(m_1,m_2)$ with hypotenuse $H$ and dividing it by the area of $R$. The result is the probability that $r_1+r_2\gt K$. (Unrelated: homework?) – Did Aug 02 '13 at 12:25
  • 1
    Not entirely sure, but perhaps this should help - http://math.stackexchange.com/questions/427139/probability-integers-and-reals-soft-question. – Constantine Aug 02 '13 at 12:27
  • It is not a home work. I am just learning probability. I found this question interesting on a website. – Ravi Chandra Aug 02 '13 at 12:28
  • OK. Which website? – Did Aug 02 '13 at 12:44
  • 1
    Suspense... $ $ – Did Aug 02 '13 at 14:55
  • [link]hackerrank.com – Ravi Chandra Aug 02 '13 at 18:10
  • Thanks. Which page? How a website dedicated to "challenges across multiple domains of Computer Science" would be interested in that is a mystery to me. (Unrelated: please use @.) – Did Aug 04 '13 at 10:46
  • Which page on hackerrank.com? – Did Aug 09 '13 at 23:27
  • @Did Sorry for the late reply.https://www.hackerrank.com/challenges/random-number-generator – Ravi Chandra Aug 20 '13 at 09:20

3 Answers3

17

A picture to go with Did's excellent hint.

enter image description here

1

$$ {m_{1}m_{2} \over m^{2}} - {\left(m_{1} + m_{2} - K\right)^{2} \over 2m^{2}}\,,\quad K < m_{1} + m_{2} $$

Felix Marin
  • 89,464
  • Probably could have been a comment, but $(+1)$ anyway :) – Mr Pie Mar 19 '18 at 09:18
  • @FelixMarin How did you come to that conclusion? I feel like my answer is wrong compared to your equation, could you take a look at mine? (I just learned the answer and decided to try and express it in my own words) https://math.stackexchange.com/a/2950353/473500 – Sebastian Nielsen Oct 10 '18 at 18:27
0

We are looking for the probability of the sum of two random numbers being less than or equal to K, the two random numbers, $r_1$ and $r_2$, are constrained as followed:

$0 \leq r_1 \leq m_1 $

$ 0 \leq r_2 \leq m_2$

Let's say that: $$ m_1=6, m_2=6, K=2$$

Let's visualize it:

enter image description here

This is a "sum box". The sides are not discrete but continuous. Inside the box, we have indefintely many numbers summarized by adding up the number from $[0, m_1]$ and the number from $[0, m_2]$. Basically this shows all the possible combinations that you are able to create.

The area of possible outcomes is: $$m_1 \cdot m_2=6\cdot6=36$$

The area of possible outcomes of which $m_1+m_2<=K$ (the area of the green triangle) is: $$(K \cdot K)/2 = (22)/2=2 $$

We can now calculate the probability of the sum of the two numbers each with their own constrained interval as follows: (area of green triangle)/(area of grey square) = $2/36$

We can now conclude that the probability of the sum of two numbers chosen randomly from the interval $[0,6]$ the probability of the sum being less than or equal to 2 is $2/36$

Sebastian Nielsen
  • 612