Maximum Probability a Line Segment touches Exactly One Grid Line

[Tee Zad Awk]

Hello,

I'm looking at a problem that I am stuck on.

This is the question:

There is a checkerboard grid of infinite length. There is also a random line segment P of length D What length of D maximizes the probability that this line segment P will cross exactly one line on the checkerboard grid? Additionally, what is this max probability?

Here is my attempt at this question (pasted below): https://math.stackexchange.com/ques...-line-segment-crosses-only-one-line-in-a-grid

/////////////////////////////////////////////////////////////////// Paste Begins ///////////////////////////////////////////////////////////////////

Let's assume we have a grid of squares that stretches into infinite. Each square has a side length of X. I've drawn the grid below. I want to know if what I've written below is the correct way to find the maximum probability that line segment P crosses at least one grid-line on this grid.
As an example, the grid below is 4 by 4, in reality the grid stretching on for infinity in all directions.

Grid


Lets look at the extremes. We know a dot in this grid will never cross one line. Alternatively, we know that a line segment Y equal to √((2X)²+X²) or X√5 will always cross two squares in the grid. See below:

Hence our answer for P needs to be somewhere in between these two lengths (0 and X√5). The chance a line segment P crosses a single grid-line is maximized when D is X√5/2 (the midpoint of line Y), as shown below. I came to this conclusion because the probability of crossing a single grid-line for all lengths of D on Y is normally distributed (starts at 0 for a single dot, and heads back to 0 when D=Y).

Midpoint Line Length (D)


I'm struggling on calculating the probability that this line crosses at least one grid-line. This is my current reasoning:
We know that a line (Z) of length √(X²+X²) will always cross at least one line. See below:

Hence, the probability of our maximum probability line segment P is represented by the area of a circle (CircleP) where D is the radius, divided by the area of a circle (CircleZ) where Z is the radius. Conceptually Z represents a line long enough for a 100% chance of crossing exactly one line. So by doing CircleP/CircleZ we are finding the probability that P will cross at least one grid-line.

Maximum probability that line segment P crosses at least one grid-line = πP²/πZ²

/////////////////////////////////////////////////////////////////// Paste Ends ///////////////////////////////////////////////////////////////////

Someone has referred me to the Buffon Needle problem, which is similar but not exact.

I've also spoken to a friend who solved this and he told me my answer is wrong. Hence, I'm here

 

[Cubist]

First, I would recommend writing a function that returns the probability that a line of length k at angle θ to the horizontal goes through exactly ONE grid line.

To help with this, consider the case θ=0.52rad (30^o) and k=X/3. The red shaded area in the following sketch shows all the locations, within a single grid square, that the lower-left end of such a line could start from. I added some example lines in green around the perimeter of the red area to show that they all pass through exactly one grid line (excuse my rough sketch). What fraction of the grid square is shaded red?



--

The next step would be to calculate a mean probability for a set of angles from θ=0 to θ=π/2. Perhaps this could be turned into an integration to find the exact probability for a line of length k at a random angle.

 

[Tee Zad Awk]

Frankly if you cannot the techniques of the Buffon Needle problem to your problem, I highly doubt we can add anything.

I'm looking at a grid though, as opposed to parallel planks. Does this not further complicate the Buffon Needle problem? How can it be adjusted to account for this? Furthermore, the question mentions that the needle can only cross exactly one line. But in the long needle case for Bufton Needle, "...In the second expression, the first term represents the probability of the angle of the needle being such that it will always cross at least one line.". I don't need at least one line, I need to adjust for exactly one line.

 

[Cubist]

I wrote a Monte Carlo simulation to give an idea of the probability...

from random import random
from numpy import arange
import math

def isLineOnOneGridLine(x,y,l,t):
    x2 = abs(math.floor(x + l*math.cos(t)))
    y2 = abs(math.floor(y + l*math.sin(t)))
    return x2+y2==1

max=500000
for l in arange(0, math.sqrt(5), .02):
    c=0
    for i in range(max):
        if (isLineOnOneGridLine(random(), random(), l, random()*math.pi*2)):
            c=c+1
    print l,float(c)/max

Note that if you decide to use my suggestion in post#2, then the sketch would change for the case k>X.
Also note that I think you would only need to consider 0 ≤ θ ≤ π/4 thanks to symmetry.

 

[Tee Zad Awk]

I wrote a Monte Carlo simulation to give an idea of the probability...

View attachment 16532

from random import random
from numpy import arange
import math

def isLineOnOneGridLine(x,y,l,t):
    x2 = abs(math.floor(x + l*math.cos(t)))
    y2 = abs(math.floor(y + l*math.sin(t)))
    return x2+y2==1

max=500000
for l in arange(0, math.sqrt(5), .02):
    c=0
    for i in range(max):
        if (isLineOnOneGridLine(random(), random(), l, random()*math.pi*2)):
            c=c+1
    print l,float(c)/max

Note that if you decide to use my suggestion in post#2, then the sketch would change for the case k>X.
Also note that I think you would only need to consider 0 ≤ θ ≤ π/4 thanks to symmetry.

I'm currently using this information to run my own analysis in C++. I'll get back to you shortly. I want to understand the methodology more so than get the right answer. Thank you.

EDIT: I drew everything out and started writing the solution on paper and in C++. This is not only elegant, and creative, it is a brilliant approach!

 

[Tee Zad Awk]

In your code you go up to X * sqrt(5), which is the length of D that guratantees it will always cross at least two lines. But you can actually cut runtime substantially by going up to X * sqrt(2), which is the line length that is always guaranteed to cross at least one line. If D is any longer than X * sqrt(2), the probability will be decreasing, as sometimes it will cross two lines.

 

[Cubist]

Thank you.

You're welcome!

I've now worked out the formula for probability P within the domain 0 ≤ length ≤ X

First I let X=1 to keep the work simpler. Let the line length be k, so 0 ≤ k ≤ 1. (Outside this domain the sketch with the red areas in post#2 will be different.)

My expression for the area of the red rectangles (which is also P(k,θ) since the grid has unit area) is:
(cos(θ)*k)*(1-k*sin(θ)) + (1-k*cos(θ))*(k*sin(θ))

Then I integrate between 0 ≤ θ ≤ π/4, and multiply the result by 4/π to obtain the average over the angle range
(see http://tutorial.math.lamar.edu/Classes/CalcI/AvgFcnValue.aspx)

My final result was:

Spoiler

P(k) = 2*k*(2 - k)/pi

The case 1 ≤ k ≤ 2 is a lot harder. I might have a go at this later.