A curious puzzle for which I would appreciate an explanation.

For $x$ and $y$ both uniformly and independently distributed in $[0,1]$, the value of $\lfloor 1/(x y) \rfloor$ has a bias toward odd numbers. Here are $10$ random trials: $$51, 34, 1, 239, 9, 4, 2, 1, 1, 1 $$ with $7$ odd numbers. Here are $10^6$ trials, placed into even and odd bins:


      EvenOddReciprocal
About 53% of the reciprocals are odd. If I use the ceiling function instead of the floor, the bias reverses, with approximately 47% odd. And finally, if I round to the nearest integer instead, then about 48% are odd.

None of these biases appear to be statistical or numerical artifacts (in particular, it seems that the 47% and 48% are numerically distinguishable), although I encourage you to check me on this.

Update. To supplement Noam Elkies' answer, a plot of $x y = 1/n$ for $n=2,\ldots,100$:


         

  • 2
    This reminds me of the graph on page 31 here: amacad.org/publications/bulletin/spring2003/diaconis.pdf – Jamie Weigandt Oct 19 '14 at 2:12
  • 1
    @JamieWeigandt: Indeed, I have added a similar image. – Joseph O'Rourke Oct 19 '14 at 11:36
  • 3
    Well, given any law on $\mathbb{N}$, you will see this kind of things happen: it is impossible to find a probability measure on $\mathbb{N}$ which gives weight $1/k$ to each of the classes modulo $k$, simultaneously for all $k$ (the weight of any number should be zero to meet that request). – Benoît Kloeckner Oct 19 '14 at 18:21
up vote 57 down vote accepted

You're dividing the square $S = \{ (x,y) \colon 0 < x < 1, 0 < y < 1\}$ into two regions according to the parity of $\lfloor 1/(xy) \rfloor$, separated by the segments of the hyperbolas $xy = 1/n$ ($n=2,3,4,\ldots$) contained in $S$. There's no reason to expect that the two regions have the same area. If I did this right, the area between the $n$-th hyperbola and the top right corner of the square is $$ A(n) := 1 - \frac{1 + \log n}{n} $$ so the discrepancy between odd and even values of $\lfloor 1/(xy) \rfloor$ is $$ (A(2)-A(1)) - (A(3)-A(2)) + (A(4)-A(3)) - + \cdots $$ which is numerically $0.066556553635\ldots$ according to the gp calculation

A(n) = 1 - (log(n)+1)/n
sumalt(n=1, (-1)^n*(A(n)-A(n+1)))

So we expect about 53.33% odd and 46.67% even values, which seems consistent with your experiment.

P.S. Using a formula I found in MO Question 140547, I gather that this number $0.066556553635\ldots$ has the closed form $$ (\log 2)^2 + \bigl(2 (1 - \gamma) \log 2\bigr) - 1, $$ where $\gamma$ is Euler's constant $0.5772156649\ldots$.

P.P.S. I see that I didn't address the end of the original question: "If I use the ceiling function instead of the floor, the bias reverses, [...] if I round to the nearest integer instead, then about 48% are odd." The first part is clear because changing $\lfloor 1/(xy) \rfloor$ to $\lceil 1/(xy) \rceil$ switches even and odd values (except in the negligible case that $1/(xy)$ is an exact integer). For the nearest-integer function, the discrepancy between odd and even values is $$\bigl(A(3/2)-A(1)\bigr) - \bigl(A(5/2)-A(3/2)\bigr) + \bigl(A(7/2)-A(5/2)\bigr) - + \cdots $$ which evaluates numerically to $-0.03500998166\ldots$ (using sumalt in gp as before), which again is consistent with observation (48.25% odd, 51.75% even). There's still a "closed form" for this discrepancy, but more complicated: $$ -3 + 4 \log(2) + \pi \bigl(1 + \log(\pi/2) - \gamma - 4 \log\Gamma(3/4) \bigr). $$ This requires evaluation of $\log(1)/1 - \log(3)/3 + \log(5)/5 - \log(7)/7 + - \cdots$, which can be achieved by differentiating the functional equation for the Dirichlet L-function $L(s,\chi_4) = 1 - 3^{-s} + 5^{-s} - 7^{-s} + - \cdots$ and evaluating at $s=1$.

  • 7
    Since $f(x) = (1+\log x)/x$ is convex decreasing on $x \geq e^{1/2}$, it's easy to see that the sequence $p_k = \mathbb P(\lfloor 1/(xy)\rfloor = k)$ is decreasing for $k \geq 2$. But $p_1 = \frac12(1-\log2) > \frac12(1+\log 2)-\frac13(1+\log3) = p_2$, so the distribution in question has a decreasing probability mass function supported on $\mathbb N$, making odds more prevalent than evens. – cardinal Oct 19 '14 at 4:32

I suspect that it has to do with the fact that the most likely outcome is $\lfloor 1/(x y) \rfloor=1$ (which happens to be odd), followed with an application of the Strong Law of Small Numbers. Here are some more details. Let $Z$ be the random variable $xy$. Note that $Z$ takes values in $[0,1]$ and $\lfloor 1/Z \rfloor$ is odd if and only if

$$ Z \in (1/2, 1] \cup (1/4, 1/3] \cup (1/6, 1/5] \cup \dots $$

Note that this set has measure more than $1/2$. However, the distribution of $Z$ is of course not uniform on $[0,1]$ (it is actually skewed towards $0$ instead of $1$). I suspect what ends up happening is that the distribution of $\lfloor 1/Z \rfloor$ is almost perfectly split between even and odd for say $Z < 1/5$, and the discrepancy is thus a result of what happens for $Z \geq 1/5$ (where one easily sees that odd wins out).

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.