0
$\begingroup$

Let $S$ be a subset of the natural numbers, and sample $x$ and $y$ uniformly from $[0,1]$.

What is the probability that the integer part of $x/y$ is an element of $S$?

For example, if $S$ is the set of even numbers, then the probability is $1-\ln(2)/2$.

Can you generalize this calculation to sets of the form $\{mn+b:n\in\Bbb N\}$?

What about sets of the form $\{p(n):n\in\Bbb N\}$ where $p$ is a polynomial?

$\endgroup$
1
$\begingroup$

The event that $\lfloor X/Y \rfloor=k$ is the event that $kY\le X<(k+1)Y$, which if $k>0$, has probability $E[ P( X\in(Y/(k+1),Y/k)|Y)] = E[Y](1/(k+1)-1/k)$, and probability $1/2$ if $k=0$, from which $$P(\lfloor X/Y \rfloor\in S) = \sum_{k\in S\setminus\{0\}}\frac 1 {2k(k+1)}+\frac 1 2 \mathbb 1_{0\in S}.$$

$\endgroup$
1
  • $\begingroup$ Great. If $S=n\Bbb Z$ then $P(\lfloor X/Y\rfloor\in S)=\frac{\psi(1+1/n)+\gamma}{2n}$ where $\psi$ is digamma and $\gamma$ is Euler-Mascheroni. $\endgroup$ – M. Nestor Nov 25 '19 at 1:48

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.