Earlier results have shown that when $l < d$, the expected number of crossings of a needle of length $l$ with vertical lines spaced $d$ apart is $\frac{2l}{\pi d}$, which is also the expression for the probability that a needle intersects a line. I'm looking for an intuitive explanation for why that is the case (is that even the case...?) when the needle is longer ie. $l > d$ (consider $l = 3, d = 1$ for example).

This does not match the expression for the probability that a needle intersects a line when $l > d$; rather, it matches the expression for the probability that a needle intersects a line when $l < d$. Is this just because the possible numbers of crossings are no longer restricted to $0$ and $1$ (ie. the $0$ term cancels out when computing the expected value)?

And, how would one find the PMF of the number of crossings when $l > d$ (for a simpler case such as $l = 3, d = 1$)? The possible values for the numbers of crossings are $0, 1, 2, 3, 4$ if I'm not mistaken. But I don't know where to go from there.

edit: still looking for the PMF!

  • 1
    $\begingroup$ Possibly helpful: cs.umb.edu/~eb/piday/whypi.pdf $\endgroup$ – Ethan Bolker Nov 25 '18 at 23:38
  • $\begingroup$ @EthanBolker I guess so! Still only deals with the situation when $l = d$. was really hoping for some hard-hitting intuition when $l > d$, but maybe it's just not intuitive and that's all there is to it. $\endgroup$ – 0k33 Nov 25 '18 at 23:44
  • 1
    $\begingroup$ I think that discussion covers the case you are interested in since it explains (or at least asserts) that the crossing number in fact depends on the ratio of $d$ to $l$. $\endgroup$ – Ethan Bolker Nov 26 '18 at 0:02
  • 1
    $\begingroup$ When $l \lt d$, the probability of crossing is equal to the expected number of crossings for precisely the reason you give: the number of crossings can only be $0$ or $1$. When $l\gt d$ then the $\frac{2l}{\pi d}$ gives the number of expected crossings but not the (smaller) probability of of at least one crossing - the expression is obviously not the probability when $\frac{l}{d}l \gt \frac{\pi}{2}$ since the expression will be greater than $1$ $\endgroup$ – Henry Nov 26 '18 at 0:36
  • $\begingroup$ @Henry Yes, of course. $\endgroup$ – Ethan Bolker Nov 26 '18 at 0:42

It is clear that we can rescale the problem and take, wlog, $d=1$ and $l/d=r$.
Therefore we can take the lines to be the vertical lines at $x \in \mathbb Z$.
Consider the needle placed with one end at $(s,0)$ and forming an angle $\alpha$ wrt the $x$ axis: we can sketch the following scheme


Considering the simmetry of the problem, we can limit to the I and II quadrants.
Also, the variable $s$ will be limited to the range $\left[ {0,1} \right)$.
However, there is a symmetry around $s=1/2$, so we will reduce our analysis to $0 \le s < 1/2$, considering $s$ and $1-s$ to be equivalent.

The circle with center in $(s,0)$ and radius $r$ encompasses the abscissas $s-r \le x \le s+r$.
The set of lines that the needle can cross are those given by $$ x = n\quad \left| {\;\left\lceil {s - r} \right\rceil \le n \le \left\lfloor {s + r} \right\rfloor } \right. $$

It is convenient to extend the values of $n$ by two additional elements at the extremes, and define a set of boundary values for $x$ and for the angle $\alpha$ defined as follows $$ \left\{ \matrix{ N = \left\{ {n\quad \left| {\;\left\lceil {s - r} \right\rceil - 1 \le n \le \left\lfloor {s + r} \right\rfloor + 1} \right.} \right\} \hfill \cr X = \left\{ {x(n)} \right\} = \left\{ {\left( {s - r} \right),\;\left\lceil {s - r} \right\rceil ,\;\left\lceil {s - r} \right\rceil + 1,\; \cdots ,\;0, \;1, \cdots ,\left\lfloor {s + r} \right\rfloor ,\left( {s + r} \right)} \right\} \hfill \cr A = \left\{ {\alpha (n) = \arccos \left( {{{x(n) - s} \over r}} \right)} \right\} = \left\{ {\pi ,\;\arccos \left( {{{\left\lceil {s - r} \right\rceil - s} \over r}} \right),\; \cdots ,\; \arccos \left( {{{\left\lfloor {s + r} \right\rfloor - s} \over r}} \right),\;0} \right\} \hfill \cr} \right. $$ where the set $A$ is in non-increasing order, contrary to the others.

In this way, the arc corresponding to $q$ intersections will be individuated by the values of $x$ such that $$ \bbox[lightyellow] { x \in \left( {\left( { - q, - q + 1} \right] \cup \left[ {q,q + 1} \right)} \right) \cap \left[ {s - r,\;s + r} \right] } \tag{1}$$ so that we have in general two arcs, except
- at $q=0$ in which case we have just one range;
- (possibly) at the extremes , where the range could be void or of null measure, depending on the values of $r$ and $s$.

In an another perspective, by the above we are assigning a value $q$ to the intervals delimited by the points in $X$,
and correspondingly to the arcs delimited by the angles in $A$.
Thus we are constructing a measure of the angle $Ang(q,s;r)$ as the sum of one or two angles.

The position $s$ and the angle $\alpha$ are supposed independent and uniformly distributed, thus the
probability of having $N$ intersections
is given by $$ \bbox[lightyellow] { \eqalign{ & dP(q,\,s;\;r) = dP(q,\,1 - s;\;r)\quad \left| \matrix{ \;0 \le s < 1/2 \hfill \cr \;0 < r \hfill \cr \;0 \le q \in Z \hfill \cr} \right. = \cr & = {1 \over \pi }{{ds} \over {1/2}}\left( {\alpha \left( { - q} \right) - \alpha \left( { - q + 1} \right) + \alpha \left( q \right) - \alpha \left( {q + 1} \right)} \right) \cr} } \tag{2}$$

After that, since $$ \eqalign{ & \int {\arccos \left( {{{n - s} \over r}} \right)ds} = - r\int {\arccos \left( {{{n - s} \over r}} \right)d\left( {{{n - s} \over r}} \right)} = \cr & = r\left( {\sqrt {1 - \left( {{{n - s} \over r}} \right)^{\,2} } - \left( {{{n - s} \over r}} \right)\arccos \left( {{{n - s} \over r}} \right)} \right) \cr} $$ we can integrate the above for $0 \le s < 1/2$, with due consideration for the variation in $s$ of the intervals:
the $n$ indicated above may vary $\pm 1$ at varying $s$, which will require to split the integral.

  • $\begingroup$ This is fantastic. The diagram is incredibly illustrative. Thank you for such a thorough explanation! $\endgroup$ – 0k33 Nov 27 '18 at 3:32
  • 1
    $\begingroup$ @Ok33: actually, in my previous version, I missed some important details: sorry. I re-casted the answer to deal more precisely with them. $\endgroup$ – G Cab Nov 28 '18 at 15:20
  • $\begingroup$ @G Cab thank you so much for the follow up! $\endgroup$ – 0k33 Nov 29 '18 at 23:58
  • 1
    $\begingroup$ @Ok33 : the argument was interesting for me as well, but it is a pleasure to help people so nice to leave a thank! $\endgroup$ – G Cab Nov 30 '18 at 0:32

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.