Intersection of two line segments from uniform distribution

[Master1022]

Homework Statement

Find the probability of two line segment intersecting with each other. The end points of lines are informally sampled from an uniform distribution between 0 and 1.

Relevant Equations

Probability

Hi,

I found this question online and made an attempt and would be keen to see whether I am thinking about it in the right manner?

Question: Find the probability of two line segment intersecting with each other. The end points of lines are informally sampled from an uniform distribution between 0 and 1.

Attempt: I was just thinking of picking the two points for the first line segment. Then I thought about what the expected value of the length of the line segment $E[|X-Y|]$. After some thinking on a Cartesian plane, I thought it would be $\frac{1}{3}$. Then I was thinking about how to choose the other two ways such that they don't intersect with that $\frac{1}{3}$, but I was stuck and don't know how to proceed...

 

[Steve4Physics]

Homework Statement:: Find the probability of two line segment intersecting with each other. The end points of lines are informally sampled from an uniform distribution between 0 and 1.
Relevant Equations:: Probability

Hi,

I found this question online and made an attempt and would be keen to see whether I am thinking about it in the right manner?

Question: Find the probability of two line segment intersecting with each other. The end points of lines are informally sampled from an uniform distribution between 0 and 1.

Attempt: I was just thinking of picking the two points for the first line segment. Then I thought about what the expected value of the length of the line segment $E[|X-Y|]$. After some thinking on a Cartesian plane, I thought it would be $\frac{1}{3}$. Then I was thinking about how to choose the other two ways such that they don't intersect with that $\frac{1}{3}$, but I was stuck and don't know how to proceed...

The question is not that clear. I think it’s not about 2 lines in the Cartesian plane; it’s about 2 line-segments on a number-line, say the x-axis.

1st random number (0≤x₁≤1) gives the start-point, on x-axis, of 1st line-segment.
2nd random number (0≤x₂≤1) gives end-point, on x-axis, of 1st line-segment.
3rd random number (0≤x₃≤1) gives start-point, on x-axis, of 2nd line-segment.
4th random number (0≤x₄≤1) gives end point, on x-axis, of 2nd line-segment.

If I’m correct, ‘overlapping’ would be a better term than ‘intersecting’.

And ‘informally sampled’ makes no sense. Maybe it should say ‘randomly sampled'.

If that helps!

EDIT. Minor corrections.

 

[Master1022]

Hi @Steve4Physics ! Many thanks for your response and apologies for my late reply.

The question is not that clear. I think it’s not about 2 lines in the Cartesian plane; it’s about 2 line-segments on a number-line, say the x-axis.

Yes, that is correct, I was just using the x-y plane to visualize the calculation of $E[|X-Y|]$

1st random number (0≤x₁≤1) gives the start-point, on x-axis, of 1st line-segment.
2nd random number (0≤x₂≤1) gives end-point, on x-axis, of 1st line-segment.
3rd random number (0≤x₃≤1) gives start-point, on x-axis, of 2nd line-segment.
4th random number (0≤x₄≤1) gives end point, on x-axis, of 2nd line-segment.

If I’m correct, ‘overlapping’ would be a better term than ‘intersecting’.

Agree!

And ‘informally sampled’ makes no sense. Maybe it should say ‘randomly sampled'.

Also agree

Apologies, my wording was unclear (I just copied the problem, when I ought to have made some other edits). I'll keep having a think about it

 

[PeroK]

An idea. Calculate the probability that they do not overlap.

Imagine we draw the first line. The second line must either be before the first line or after. Overall this is equally likely, so we calculate the probability that the second line is before the first line. Then double that.

The second line is before the first one if the higher of the two numbers chosen for that line is less than the lower of the two numbers chosen for the first line.

 

[PeroK]

PS I got the answer, confirmed by a Python script.

And now that I know the answer I see there is a really easy way to do it, which does not involve probability density functions at all!

 

[PeroK]

Attempt: I was just thinking of picking the two points for the first line segment. Then I thought about what the expected value of the length of the line segment $E[|X-Y|]$. After some thinking on a Cartesian plane, I thought it would be $\frac{1}{3}$. Then I was thinking about how to choose the other two ways such that they don't intersect with that $\frac{1}{3}$, but I was stuck and don't know how to proceed...

One problem with this is that the expected value loses a lot of information about the distribution of line lengths, which looks important. You could get an answer for a typical length of $1/3$ - although that also depends where the line is.

That looks like a dead-end to me.

 

[WWGD]

Seems you can setup two Random Variables$X_1, X_2$ ; both uniform on [0,1] and find$P( Min X_2-Max X_1 \geq 0)$. Dont know if the difference of two ( independent, I assume) uniforms is uniform, though. Edit: If $X_2$is $U[0,1]$, then -$X_2$ is $U[-1,0]$. Then you can do the convolution product $F_3:=F_1*F_2$ for the respective densities and find the probability $F_3\geq 0$.

 

[PeroK]

Seems you can setup two Random Variables$X_1, X_2$ ; both uniform on [0,1] and find$P( Min X_2-Max X_1 \geq 0)$. Dont know if the difference of two ( independent, I assume) uniforms is uniform, though. Edit: If $X_2$is $U[0,1]$, then -$X_2$ is $U[-1,0]$. Then you can do the convolution product $F_3:=F_1*F_2$ for the respective densities and find the probability $F_3\geq 0$.

Neither the lower point of one line, nor the higher point of the other line is a uniform distribution. The difference of those certainly can't be uniform. It's much more likely to be a small number.

You can do it by generating the pdf's - that's what I did first - but there is a much easier way.

 

[WWGD]

Neither the lower point of one line, nor the higher point of the other line is a uniform distribution. The difference of those certainly can't be uniform. It's much more likely to be a small number.

You can do it by generating the pdf's - that's what I did first - but there is a much easier way.

I think you can use the original rvs to compute the probability that the difference is larger than 0, instead of the respective Max and Min.

 

[PeroK]

I think you can use the original rvs to compute the probability that the difference is larger than 0, instead of the respective Max and Min.

We can all think things. It's whether you can back them up with calculations that matters!

 

[WWGD]

We can all think things. It's whether you can back them up with calculations that matters!

Do you believe my premises are flawed? Aren't we looking for the probability that the difference is larger or equal to 0? And that the difference distribution is given by the convolution product? I let the OP do part of the work; I don't do the whole exercise for them.

 

[WWGD]

I consider this a question in Mathematics and not in Physics.

 

[Steve4Physics]

How about this...

Two random numbers define one line-segment (LS).
Another two random numbers define the other LS.

List the 4 numbers, smallest to largest: p, q, r and s.

One of the LS’s contains the smallest number, p.
Since the distribution is uniform, this line segment is equally likely to be (p, q) or (p, r) or (p, s).

Can you finish it off from there?

(However, I don't see why the interval is limited to between 0 and 1. So either that's a red-herring or I'm missing some subtle point.)

 

[WWGD]

How about this...

Two random numbers define one line-segment (LS).
Another two random numbers define the other LS.

List the 4 numbers, smallest to largest: p, q, r and s.

One of the LS’s contains the smallest number, p.
Since the distribution is uniform, this line segment is equally likely to be (p, q) or (p, r) or (p, s).

Can you finish it off from there?

(However, I don't see why the interval is limited to between 0 and 1. So either that's a red-herring or I'm missing some subtle point.)

Edit: Brain fart: assume the choice [0,1] matters ( modulo length) because it's easier to avoid each other in segments with larger width. Not correct.

 

[PeroK]

I assume the choice [0,1] matters ( modulo length) because it's easier to avoid each other in segments with larger width.

My Python script says otherwise.

 

[Steve4Physics]

I assume the choice [0,1] matters ( modulo length) because it's easier to avoid each other in segments with larger width.

I can't see why the choice of interval matters. The argument is just the same for any other interval, e.g. [-5, 34.7].

To complete my Post #13 argument...

Arrange the 4 random numbers in order: p, q, r and s.

Consider the line-segment containing the smallest number (p). This line-segment must be (p, q) or (p, r) or (p, s). Since the distribution is uniform, these three possibilities are equally likely.

But only (p, q) avoids overlap. In the other two cases ((p, r) or (p, s)) the line-segments necessarily overlap.

So the probability of two line-segments overlapping is two out of three, i.e. ⅔.

This is totally independent of the interval chosen (but does require a uniform probability distribution over the interval).

 

[WWGD]

I can't see why the choice of interval matters. The argument is just the same for any other interval, e.g. [-5, 34.7].

To complete my Post #13 argument...

Arrange the 4 random numbers in order: p, q, r and s.

Consider the line-segment containing the smallest number (p). This line-segment must be (p, q) or (p, r) or (p, s). Since the distribution is uniform, these three possibilities are equally likely.

But only (p, q) avoids overlap. In the other two cases ((p, r) or (p, s)) the line-segments necessarily overlap.

So the probability of two line-segments overlapping is two out of three, i.e. ⅔.

This is totally independent of the interval chosen (but does require a uniform probability distribution over the interval).

Ah, you're right, my bad. Brain fart. Let me edit.

 

[WWGD]

My Python script says otherwise.

Yes, my bad, I just edited. Brain fart.