Cuántos cuadrados hace una línea entre dos puntos pasan a través de?

Question

Supongamos que tengo un cuadrado, digamos que los lados tienen longitud 1. A continuación, voy a la partición de la plaza en $N^2$ sub-cuadrados, donde $N \in \mathbb{N}$ y el sub-cuadrados son todos del mismo tamaño. Ahora, supongamos que colocamos dos puntos de $A$ $B$ al azar dentro de la gran plaza, en una distancia de $D$ separados el uno del otro, y, a continuación, dibuje el segmento de la línea de $AB$. La pregunta es, ¿cuál es el número esperado de pequeños cuadrados que $AB$ va a pasar?

No tengo idea de cómo resolver analíticamente, y estaba pensando en intentar obtener un sentido de uso de la simulación, pero fue curioso lo que he podido aprender sobre ello aquí. (Esta no es una tarea cuestión; es relacionada con un problema en el que estoy trabajando en la investigación en economía.)

Answer 1

Supongamos que usted tiene que dividir el cuadrado en $N^2$ sub-cuadrados, donde $N\in\mathbb{N}$. A continuación, supongamos que $A=(x_{1},y_{1})$ $B=(x_{2},y_{2})$ donde $x_{1},x_{2},y_{1}$ $y_{2}$ son números reales en $[0,1]$. A continuación, el segmento de $AB$ debe pasar a través de, al menos, $N|y_{2}-y_{1}|$ plazas en el $y$ (o vertical) de la dirección y, al menos, $N|x_{2}-x_{1}|$ plazas en el $x$ (u horizontal) de la dirección. Así, se espera que el segmento de $AB$ para pasar a través de $N|x_{2}-x_{1}|+ N|y_{2}-y_{1}|$ plazas.

Answer 2

Imaginar las filiales de la plaza como un $N\times N$ tablero de ajedrez de la subsquares. Cada punto de la placa pertenece a uno subsquare con coordenadas $(r,c)$ donde $r$ (el índice de fila) rangos de $1$ $N$y lo mismo para las $c$ (el índice de columna).

Ahora el número de subsquares que el segmento de línea $\overline{AB}$ entre los dos uniformemente en los puntos seleccionados $A$ $B$ toca es igual a $d(A,B)=|A(r)-B(r)|+|A(c)-B(c)|+1$. Aquí $A(r)$ significa índice de fila para $A$, y lo mismo para las otras notas. Los puntos de $A$ $B$ están en "situación general" debido a la aleatoriedad, de modo que el segmento pasa siempre por el máximo número de subsquares. El segmento de no golpear las esquinas.

Dado que las variables aleatorias $A(r),B(r),A(c),B(c)$ son independientes y uniformemente distribuido en $\{1,\dots, N\}$, no es difícil calcular que el número esperado es $$\mathbb{E}(d(A,B))=1+{2(N^2-1)\over3N}.$$

Answer 3

El número de las células tocado por la línea (después de Byron respuesta) $N (|X_1-X_2| + |Y_1-Y_2| +1) $ . Llamar a $X =|X_1 - X_2|$ $Y = |Y_1 - X_2|$ y dejando aparte el $N$ factor, esto es aproximadamente equivalente, para un gran$N$,$d_M=X+Y$, la distancia Manhattan.

Por lo tanto, voy a atacar el siguiente problema: Tenemos que tirar dos puntos al azar en la unidad de la plaza; queremos calcular $$E(d_M | d)$$

where $d=\sqrt{X^2+Y^2}$ is the euclidean distance.

The expected number of touched cells, in this approximation, would be $N E(d_M | d) + 1$.

It's not difficult to see that $X$ (absolute value of the difference of two uniform v.a) has a triangular density : $f_X(x)=2(1-x)$ The same for $S$, y los dos son independientes, por lo tanto: $$f_{XY}(x y)=4(1-x)(1-y)$$ on the unit square.

UPDATE: Below I found a much simpler solution

\begin{equation} \left(\hat{L} + \lambda \rho(\mathbf{x}) \right) u(\mathbf{x}) = 0 \end\begin{equation} \bigg( \frac{ - \hbar^{2} }{ 2 m_{\mathrm{e}} } \frac{ \mathrm{d}^{2} }{ \mathrm{d} r^{2} } + \frac{ \hbar^{2} }{ 2 m_{\mathrm{e}} } \frac{ \ell (\ell + 1) }{ r^{2} } - \frac{ Z e^{2} }{ 2 m_{\mathrm{e}} r } - E \bigg) r R(r) = 0 \end----- begin ignore -----

Conditioning on a fixed value of $d$ implies that we must restrict to an arc, the intersection of $x^2+y^2=c^2$ and the unit square.

Let's assume first that $d<1$

Note that $d\le d_M \le \sqrt{2} d$

To compute $P(d_M \le \xi | d)$, we must integrate over two pieces of arcs begining on the axis (because of symmetry, we compute just one and multiply by two). (blue arcs in the figure) The first limit point is given by $$x_1=\frac{\xi - \sqrt{2 d^2-\xi^2}}{2}$$ Más a cambio de la integración sobre el arco para una integral sobre $x$, observamos que $ds=\sqrt{1+\frac{x^2}{y^2}}{dx} = \frac{d}{y}dx$. Así que, dejando de lado las constantes (que desaparecen en la división), tenemos que la función de distribución acumulativa (condicionado a $d$) está dada por

$$F_{d_M|d}(\xi;d)=P(d_M \le \xi | d) = \frac{2 \int_{0}^{x_1}\left( 1-x\right) \,\left( \frac{1}{\sqrt{{d}^{2}-{x}^{2}}}-1\right) dx}{\int_{0}^{d}\left( 1-x\right) \,\left( \frac{1}{\sqrt{{d}^{2}-{x}^{2}}}-1\right) dx}$$

Finally, we must integrate to get the expected value

$$E(d_M |d) = d+ \int_{d}^{\sqrt{2} d} \left[1- F_{d_M|d}(\xi;d) \right] \; d\xi $$

This is all.. but it seems pretty complicated to get in close form. Let's see Maxima:

assume(x1>0);assume(d>0);assume(d>x1);
integrate((1-x)*(1/sqrt(d^2-x^2)-1), x,0,x1);

$$\frac{2\,\mathrm{asin}\left( \frac{x1}{d}\right) +2\,\sqrt{{d}^{2}-{x1}^{2}}+{x1}^{2}-2\,x1-2\,d}{2}$$

ix2(x1,d):=(2*asin(x1/d)+2*sqrt(d^2-x1^2)+x1^2-2*x1-2*d)/2;
x1(dm,d):=(dm-sqrt(2*d^2-dm^2))/2;
assume(dm>d); assume(dm<sqrt(2)*d);
fdist(dm,d):=2*(ix2(xx(dm,d),d))/ix2(d,d);

This gets a little messy. Let's try at least some numerical values:

dd:0.8;
dd+quad_qags(1-fdist(dm,dd), dm, dd, sqrt(2)*dd)

1.01798

Let's simulate to check: Matlab/Octave:

N=300000;
t=rand(N,4);
xy = [abs(t(:,1)-t(:,3)),abs(t(:,2)-t(:,4))];
t=[];
d2=xy(:,1).^2+xy(:,2).^2;
d=sqrt(d2);
dm=xy(:,1)+xy(:,2);
step=0.02;
dround=round(d/step)*step;
%size(dround(dround==0.8))
mean(dm(dround==0.8))
>>>ans =  1.0174

Not bad, I'd say. Some other values:

  d   Maxima      Octave (simul)
 0.9  1.15847     1.1569
 0.8  1.01798     1.0174
 0.7  0.88740     0.8863
 0.6  0.75983     0.7579
 0.5  0.63328     0.6331
 0.4  0.50698     0.5063
 0.3  0.38062     0.3808

The case $d>1$ should be solved in a similar way.

--------------- end ignore -----

A much simpler solution:

Let's change to polar coordinates: $x = r \cos(t)$, $y = r \sin(t)$. La articulación de la densidad es

$$f_{r,t}(r,t) = 4 r (1- r \cos(t))(1- r \sin(t))$$

in the domain $0 \le r \le \sqrt{2}$, $0 \le t \le \pi/2$ for $r\le 1$, $ arccos(1/r) \le t \le arcsen(1/r)$ for $r > 1$

The conditional density is then

$$f_{t|r}(t|r) = \frac{1}{g(r)} (1- r \cos(t))(1- r \sin(t))$$

where $g(r)$ is the normalization constant (indepent of $t$).

Assuming first that $r<1$, then

$$g(r) = \int_0^{\pi/2} (1- r \cos(t))(1- r \sin(t)) dt = \frac{{r}^{2}}{2}-2\,r+\frac{\pi }{2}$$

Further, $d_M= x + y= r (\cos(t)+\sin(t))$, so the conditional expectation is given by

$$E[d_M | r] = r \frac{1}{g(r)} \int_0^{\pi/2} (1- r \cos(t))(1- r \sin(t)) (\cos(t)+\sin(t)) dt$$

which gives

$$ E[d_M | r] = r \frac{4\,{r}^{2}-3\,\left( \pi +2\right) \,r+12}{3\,{r}^{2}-12\,r+3\,\pi }$$

For $r>1$ it's more complicated. The result is

$$ E[d_M | r] = r \frac{\sqrt{{r}^{2}-1}\,\left( 4\,{r}^{2}+8\right) +\left( 6\,\mathrm{asin}\left( \frac{1}{r}\right) -6\,\mathrm{acos}\left( \frac{1}{r}\right) -6\right) \,{r}^{2}-4}{3\,{r}^{3}-12\,r\,\sqrt{{r}^{2}-1}-\left( 6\,\mathrm{asin}\left( \frac{1}{r}\right) -6\,\mathrm{acos}\left( \frac{1}{r}\right) -6\right) \,r} $$

The figure shows $E[d_M | r] / r$, ie. the factor by which the expected Manhattan distance exceeds the euclidean distance (we already knew that this must be in the $[1,\sqrt{2}]$ range).

(BTW: sorry if the formatting is not optimal, but I got sick of my Chorme crashing on the edition, lots of times, sometimes losing changes - am I the only one?)

Added: Notice that for small distances ($r \a 0$) the expected number of squares results $r N \frac{4}{\pi} +1 $, lo cual está de acuerdo con Ronald de la respuesta.

Answer 4

Coincido en líneas generales con @Byron Schmuland la respuesta, que parece correcto, pero tengo algunas sugerencias adicionales.

Estoy suponiendo que el tamaño de un pequeño cuadrado es 1, por simplicidad, en comparación con una distancia de D.

Si la pregunta es colocar a y B "al azar" con una distancia de D aparte, este puede caer mal de Bertrand paradoja: que este concepto de aleatoriedad no está claramente definido.

Sin embargo, parece que tiene sentido colocar Una primera, lo que sugiere que deberíamos lugar B en un arco con centro a y radio D. El arco estará restringido dependiendo de cuán cerca se encuentra al borde de la plaza.

Supongamos que elegimos el punto A, y, a continuación, el ángulo de $\theta$ es seleccionado al azar. Cada dirección $\theta$ es igualmente probable (por supuesto aquí y por la simetría de la plaza).

A continuación, el número de plazas se pasa a través de se $D|\sin(\theta)|+D|\cos(\theta)|+1$ de Byron del trabajo y el uso de un ángulo recto del triángulo.

$$E[D|\sin(\theta)|+D|\cos(\theta)|+1]$$ $$= D \cdot E[|\sin(\theta)|+|\cos(\theta)|] + 1$$ $$= 4D/\pi + 1$$

O, teniendo en cuenta $(1/N)$ a ser la longitud de un cuadrado pequeño (de acuerdo a la pregunta) $$= 4ND/\pi + 1$$

En el caso de que $N = 2$ ($2$ cuadraditos por lado) y $D = 0.5$ ($D$ es la mitad de la longitud de un lado largo), los esperamos para pasar a través de $2.27$ plazas. Parece derecho. A veces pasa sólo a través de $1$, pero más a menudo de lo $3$.

Esto va a romper hacia abajo mal cuando D se pone de largo en comparación con el lado de la gran plaza, me imagino ($D>1$?), cuando la línea ya no tiene la opción de ser horizontal o vertical.