Given two random numbers in (0,1) what are odds that the quotient is closer to an odd integer?

[member 428835]

Homework Statement

Given two random numbers $x$, $y$, what is the probability $x/y$ is closer to an odd integer than an even integer?

Relevant Equations

Nothing comes to mind.

Closer to odd number implies $|y/x - (2n+1)| < 1/2$ for $n = 0,1,2...$. Then
$$-\frac 1 2 < \frac y x - (2n+1) < \frac 1 2 \implies\\
y < (2n + 1.5)x,\\
y > (2n + 0.5)x$$
for each $n$. We note $x \in (0,1)$ implies $y$ can be larger than 1 since the slope is greater than 1 (but we know it can't be). So the integration limits would not be uniform, and thus more work is needed. Fortunately, the problem is identical if we take $x/y$, which implies the slopes are inverse of what I wrote, and therefore always less than 1, which implies the integration limits can are $0,1$. This implies probability $P$ is equal to
$$P = \sum_n \int_0^1 \left( \frac{1}{2n + 1.5}x - \frac{1}{2n + 0.5}x \right) \, dx \implies\\
P = \frac 1 2 \sum_n \frac{1}{0.5 + 2n} - \frac{1}{1.5 + 2n}$$. This sum is $P = 1/5-1/7+1/9-1/11+...$ which is similar to expansion of $\log(2)$ but that's all I know. This sum is not telescoping (at least not immediately so). Intuitively we know this must converge (just plot the integrals for various $n$ and it's clear the area is finite). But I don't know how to proceed. Or is leaving this in open form the best we can do?

EDIT: linebreak doesn't seem to work. Have I missed something in latest syntax?

 

[mjc123]

I don't know about your proof, but 1 - 1/3 + 1/5 - 1/7 ... = π/4
Why do you omit the first two terms (corresponding to n = 0)?

 

[member 428835]

I don't know about your proof, but 1 - 1/3 + 1/5 - 1/7 ... = π/4
Why do you omit the first two terms (corresponding to n = 0)?

Brain fart, I just spaced it. But how are we supposed to know that series converges to $\pi/4$?

EDIT: actually, the $n=0$ case is special, since the integration bounds change!

 

[PeroK]

I wrote a Python simulation to get the answer. It's not $\frac \pi 4$, which seems too close to $1$.

 

[member 428835]

I wrote a Python simulation to get the answer. It's not $\frac \pi 4$, which seems too close to $1$.

It's because the solution is $$1/5-1/7+1/9-1/11+...+1-\int_0^{1/2}2x \, dx$$ since $x,y<1$. The integral at $n=0$ has slope greater than 1 for one of the integrands. So answer is $1-1/4+1/5-1/7+1/9-1/11+...=\pi/4-7/12$?

 

[FactChecker]

Intuitively, I don't see how it could be anything other than 1/2.
Is there a limit on the range of your random numbers? (Sorry, I see the range limits in the title)

 

[FactChecker]

It's because the solution is $$1/5-1/7+1/9-1/11+...+1-\int_0^{1/2}2x \, dx$$ since $x,y<1$. The integral at $n=0$ has slope greater than 1 for one of the integrands. So answer is $1-1/4+1/5-1/7+1/9-1/11+...=\pi/4-7/12$?

$\pi/4 - 7/12 \approx 0.202$ seems much too small.
I ran some simulations of one billion samples each and seem to get a fairly consistent value. (Not the 1/2 that my intuition told me.)

 

[member 428835]

$\pi/4 - 7/12 \approx 0.202$ seems much too small.
I ran some simulations of one billion samples each and seem to get a fairly consistent value. (Not the 1/2 that my intuition told me.)

Okay, I think I got it. Two mistakes in my first post: 1) integration difference is flipped (typo) and 2) treatment of $n=0$. So we have
$$P =P_0 + \sum_{n=1} \int_0^1 \left( \frac{1}{2n + 0.5}x - \frac{1}{2n + 1.5}x \right) \, dx \implies\\
P = P_0+ 1/5-1/7+1/9-1/11+...$$
where $$P_0 = \int_0^{1/2} \left(\frac{1}{0 + 0.5}x - \frac{1}{0 + 1.5}x \right) \, dx + \int_{1/2}^1 \left(1 - \frac{1}{0 + 1.5}x \right) \, dx = 1/4 + 1/6$$. Then $P = 5/12 - 1 + 1/3 +(1-1/3+1/5-1/7+1/9-1/11+...) = \pi/4-1/4 \approx 0.53...$ which agrees with my python calculations too. But how am I supposed to know that series converges to $\pi/4$? I'd have never known this. Just common knowledge I guess?

 

[PeroK]

It's because the solution is $$1/5-1/7+1/9-1/11+...+1-\int_0^{1/2}2x \, dx$$ since $x,y<1$. The integral at $n=0$ has slope greater than 1 for one of the integrands. So answer is $1-1/4+1/5-1/7+1/9-1/11+...=\pi/4-7/12$?

My point is that if you write a simulation you can check whether you are correct.

 

[PeroK]

But how am I supposed to know that series converges to $\pi/4$? I'd have never known this. J

This is quite famous, using the Taylor expansion for $\tan^{-1}(1) = \frac \pi 4$.

 

[haruspex]

Homework Statement:: Given two random numbers $x$, $y$, what is the probability $x/y$ is closer to an odd integer than an even integer?

I do not understand why you are summing over n. From the above statement of the problem, I would think you want to find $P[\min_n |\frac xy-\frac 1{2n+1}|<\min_n |\frac xy-\frac 1{2n}|]$.

 

[PeroK]

I do not understand why you are summing over n. From the above statement of the problem, I would think you want to find $P[\min_n |\frac xy-\frac 1{2n+1}|<\min_n |\frac xy-\frac 1{2n}|]$.

The OP's approach seems like the obvious one.

In general, for $\frac x y$ to be closest to the integer $n$ we need:
$$y \in [\frac{2x}{2n+1}, \frac{2x}{2n - 1}]$$This is a problem only when $x \ge \frac 1 2$ and $n = 1$. In which case, we have $y \in [\frac{2x}{3}, 1]$.

For $x \le \frac 1 2$, we have a sum of intervals for $y$ for odd $n$:
$$f(x) = 2x\sum_{n \ odd}\big [\frac 1 {2n -1} - \frac 1 {2n+1} \big ] = \frac \pi 2 x$$ And, for $x > \frac 1 2$, we have:
$$f(x) = 2x\sum_{n \ odd}\big [\frac 1 {2n -1} - \frac 1 {2n+1} \big ] - (2x - 1) = \frac \pi 2 x + 1 - 2x$$

 

[haruspex]

The OP's approach seems like the obvious one.

In general, for $\frac x y$ to be closest to the integer $n$ we need:
$$y \in [\frac{2x}{2n+1}, \frac{2x}{2n - 1}]$$This is a problem only when $x \ge \frac 1 2$ and $n = 1$. In which case, we have $y \in [\frac{2x}{3}, 1]$.

For $x \le \frac 1 2$, we have a sum of intervals for $y$ for odd $n$:
$$f(x) = 2x\sum_{n \ odd}\big [\frac 1 {2n -1} - \frac 1 {2n+1} \big ] = \frac \pi 2 x$$ And, for $x > \frac 1 2$, we have:
$$f(x) = 2x\sum_{n \ odd}\big [\frac 1 {2n -1} - \frac 1 {2n+1} \big ] - (2x - 1) = \frac \pi 2 x + 1 - 2x$$

Ok, I see the principle, but I get $\pi/2-1$, and it seems borne out by experiment.

 

[PeroK]

Ok, I see the principle, but I get $\pi/2-1$, and it seems borne out by experiment.

That comes out as $0.570$, whereas I get $0.535$.

 

[PeroK]

... the difference is only $(\pi -3)/4$.

 

[FactChecker]

That comes out as $0.570$, whereas I get $0.535$.

My simulation also gives 0.535 consistently.

 

[haruspex]

My simulation also gives 0.535 consistently.

Then there is a real difference.
My simulation, just a Google sheet, generates two random numbers in (0,1) and counts if(isodd(round(max(x/y,y/x))),1,0). With 1000 samples, the average is definitely around 0.57.

 

[vela]

Then there is a real difference.
My simulation, just a Google sheet, generates two random numbers in (0,1) and counts if(isodd(round(max(x/y,y/x))),1,0). With 1000 samples, the average is definitely around 0.57.

What if you replace max(x/y, y/x) with just x/y?

I simulated both ways in Mathematica. Choosing the maximum of x/y and y/x yields 0.57; without it, you get 0.535.

 

[member 428835]

What if you replace max(x/y, y/x) with just x/y?

I simulated both ways in Mathematica. Choosing the maximum of x/y and y/x yields 0.57; without it, you get 0.535.

Hmmmmm very cool.

 

[WWGD]

This screams Geometric Probability to me. Find the total area between: $$y=x/2$$ and $$y=3x/2$$, then between $$5x/2$$ and $$7x/2, (2n-1)/2$$ and in general $$(2n+1)/2$$, within $$[0,1]\times [0,1]$$ etc.

 

[haruspex]

What if you replace max(x/y, y/x) with just x/y?

I simulated both ways in Mathematica. Choosing the maximum of x/y and y/x yields 0.57; without it, you get 0.535.

Yes, it dawned on me after I posted that I was slightly misreading the problem.

 

[vela]

This screams Geometric Probability to me.

I did this and ended up with the same sum @joshmccraney derived. It's a nice way to look at the problem as all you need to do is calculate areas of triangles, and it sheds light on why @FactChecker's intuitive guess was wrong.

 

[PeroK]

it sheds light on why @FactChecker's intuitive guess was wrong.

I thought the function $x/y$ was too non-linear for $0.5$ to be the answer. In fact, I would have guessed more like $2/3$, with $n = 1$ dominating. That's true, as it turns out, but $n = 0$ is also quite likely.

The probability that $0$ or $1$ is nearest to $x/y$ is $1/4$ and $5/12$ respectively. That gives the odd numbers a head's start of $+1/6$.

The rest have a total probability of only $1/3$ between them (with more likelihood of even than odd). That closes the gap, but I don't see the symmetry that would possibly lead to equality.

 

[Prof B]

This screams Geometric Probability to me.

The region where y/x is closer to an odd number than an even number consists of triangles. The first two triangles have area 1/4 and 1/6. The rest have area, 1/5-1/7, 1/9-1/11, 1/13-1/15, etc.