1
$\begingroup$

Let $a$ and $b$ be positive integers with $b > a$.

Let $A$ and $B$ be two discrete uniform distributions over the integer intervals $[[1, a]]$ and $[[1, b]]$ respectively.

Then, given any $t \in [[1, a b]]$, what is the value of

$$\Pr(A\cdot B = t )?$$

If this is too hard, can we know at least $\Pr(A\cdot B \le t )?$

-- EDIT --

Actually, $A\cdot B = t$ means that we sampled an $\alpha$ from $A$ and a $\beta$ from $B$ such that $\alpha \cdot \beta = t$. So, it means that both $\alpha$ and $\beta$ are divisors of $t$, $\alpha$ is smaller than or equal to $a$, and $\beta = t/\alpha \le b$.

So, let $Div(x) := \{ y \in \mathbb{N}^* : y \text{ divides } x\}$ and $D_{t, a, b} := \{(\alpha, \beta) \in Div(t) \times Div(t) : \alpha \le a \text{ and } t / \alpha \le b\}$, then, we have

$$\Pr(A\cdot B = t) = \frac{|D_{t, a, b}|}{ab}$$

However, that characterization is not very useful, since computing the divisors of $a$ and of $b$ is very computationally expensive.

Do you know another way of computing this probability?

$\endgroup$
  • 2
    $\begingroup$ You can make a table. Then it is easy to deduce a pdf. $\endgroup$ – callculus Sep 13 at 16:42
  • $\begingroup$ But when $a$ and $b$ are big, doing such a table is not feasible. $\endgroup$ – Hilder Vítor Lima Pereira Sep 14 at 12:12

Your Answer

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

Browse other questions tagged or ask your own question.