Suppose I have a square, let's say the sides have length 1. I will then partition the square into $N^2$ sub-squares, where $N \in \mathbb{N}$ and the sub-squares are all the same size. Now, suppose we place two points $A$ and $B$ randomly within the large square a distance of $D$ apart from each other, and then draw the line segment $AB$. The question is, what is the expected number of small squares that $AB$ will pass through?
I have no idea how to solve this analytically, and was thinking of attempting to get a sense using simulation, but was curious what I could learn about it here. (This isn't a homework question; it's related to a problem I'm working on in economics research.)
Best Answer
Imagine the subdivided square as an $N\times N$ chessboard of subsquares. Every point on the board belongs to one subsquare with coordinates $(r,c)$, where $r$ (the row index) ranges from $1$ to $N$ and similarly for the $c$ (the column index).
Now the number of subsquares that the line segment $\overline{AB}$ between two uniformly selected points $A$ and $B$ touches equals $d(A,B)=|A(r)-B(r)|+|A(c)-B(c)|+1$. Here $A(r)$ means row index for $A$, and similarly for the other notation. The points $A$ and $B$ are in "general position" because of the randomness, so the segment always passes through the maximum number of subsquares. The segment doesn't hit any corners.
Since the random variables $A(r),B(r),A(c),B(c)$ are independent and uniformly distributed on $\{1,\dots, N\}$, it is not hard to calculate that the expected number is $$\mathbb{E}(d(A,B))=1+{2(N^2-1)\over3N}.$$