La eficiencia del problema de estacionamiento aleatorio

Question

Hace unos días en mi clase de Cálculo BC nos dieron una página con 6 problemas desafiantes de fin de año. Eso fue un cambio refrescante de la tediosa tarea que generalmente hacemos (WebAssign). Uno de ellos era así:

Hay una calle de longitud 4 en la que autos de longitud 1 desean estacionarse. Sin embargo, en vez de estacionarse de manera organizada, lo hacen al azar, eligiendo uniformemente entre las posiciones disponibles para estacionar (aparentemente son desagradables). Asumiendo que ningún auto se va, y que continúan llegando hasta que ya no haya más espacio, ¿cuántos autos se espera que quepan en total?

Intenté resolver este problema asumiendo que el número esperado de autos sería un número entero. Por lo tanto, reduje el problema a encontrar la probabilidad de que 2 o 3 autos pudieran estacionarse.

Cuando busqué la respuesta en https://cornellmath.wordpress.com/2008/01/08/the-efficiency-of-random-parking/ ¡me sorprendió ver decimales! Mi interpretación del problema fue incorrecta porque pensé que "valor esperado" significaba lo mismo que "¿qué evento es más probable que ocurra?".

Aunque, ahora que lo pienso, supongo que habría significado lo mismo si hubiera permitido un número no entero de autos.

Aquí está mi pregunta: ¿Cuál es la probabilidad de que 2 autos se estacionen en la calle? ¿Y de 3 autos? ¿Hacer esta pregunta nos adentra más en la naturaleza del problema en absoluto?

Me gustaría ver respuestas a mi pregunta, pero soluciones al problema inicial del valor esperado que sean claramente diferentes a la solución en el enlace también son bienvenidas.

Gracias por su tiempo y esfuerzo.

Edición/Agregado:

En primer lugar, me gustaría, una vez más, agradecer a aquellos que contribuyeron con una respuesta. Ahora entiendo el problema y su solución mucho más que antes.

Pero lo que me preocupa es que llegué a una solución que tenía sentido (al menos para mí) y no entiendo por qué está mal. Así que publicaré mi solución y con suerte alguien puede ayudarme con eso.

Segunda Edición:

Publiqué mi solución en Something Isn't Right With My Parking como otra pregunta porque es un problema considerablemente diferente.

Answer 1

Sea $N$ la variable aleatoria que representa cuántos autos pueden estacionarse. Si un auto se estaciona, habrá espacio para otro, por lo que $\Pr(N=1)=0$. Teóricamente es posible que cuatro autos se estacionen, pero esto sucederá con una probabilidad de $\Pr(N=4)=0$.

Entonces el valor esperado de $N$ será $2\times \Pr(N=2) + 3\times \Pr(N=3)$, algo así como la media aritmética. Esto estará entre $2$ y $3, por lo que podría representarse por un decimal.

Agregado: Supongamos que tienes un espacio de longitud $y$ con $2 \le y \le 3$. Podrás colocar uno o dos autos en él, dependiendo de si el primer auto deja un espacio lo suficientemente grande antes o después. El centro está uniformemente distribuido en el intervalo $[\frac12, y-\frac12]$, y el espacio cabrá dos autos si el centro del primer auto está en el intervalo $[\frac12, y-\frac32]$ o en el intervalo $[\frac32, y-\frac12]$, haciendo que la probabilidad de quepan dos sea $\frac{2y-4}{y-1}$.

Ahora supongamos que tienes un espacio de longitud $4$. El centro de la posición inicial del primer auto está uniformemente distribuido en el intervalo $[\frac12, \frac72]$, por lo que con una densidad de $\frac13$ y si esto es $C$, entonces los espacios restantes son $C-\frac12$ y $\frac72 - C$. Si $\frac32 \le C \le \frac52$ definitivamente podrás colocar dos autos más. De lo contrario, necesitaremos usar nuestro resultado anterior. Entonces la probabilidad de que encajen tres autos en total es $$\int_{c=1/2}^{3/2} \frac13 \frac{2(\frac72 - c)-4}{(\frac72 - c)-1} \, dc + \int_{c=3/2}^{5/2} \frac13 \, dc +\int_{c=5/2}^{7/2} \frac13 \frac{2(c-\frac12 )-4}{(c-\frac12 )-1}\, dc$$ $$= \frac{2-2\log(2) }{3} +\frac13+\frac{2-2\log(2) }{3} =\frac{5-4\log(2) }{3} $$ lo que lleva a decir que el número esperado es $\dfrac{11-4\log(2) }{3}$.

El problema con tu solución: Si calculas la distribución marginal de la posición del primer auto en tu solución, encontrarás que el primer auto no está uniformemente distribuido en el intervalo original, sino que es más probable que esté en uno de los extremos. Si divides las posiciones posibles del primer auto en tres longitudes iguales entonces (contando tus triángulos), las probabilidades de cada tercio están en la proporción $3:2:3$, es decir, las probabilidades son $\dfrac38, \dfrac14, \dfrac38$ cuando deberían ser $\dfrac13,\dfrac13,\dfrac13$.

Answer 2

Sea $f(x)$ el número esperado de autos de longitud unitaria que caben en una carretera de longitud $x$. Podemos escribir una recurrencia para $f(x)$ de la siguiente manera:

$$ f(x) = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) + f(x-1-t) \, dt $$

Es decir, el primer auto se estaciona con su extremo izquierdo en el punto $t$, donde $t$ está distribuido uniformemente en el intervalo $[0, x-1]$. Esto (generalmente) divide la carretera en dos partes, una de longitud $t$ y otra de longitud $x-1-t$, que cabrán un número de autos igual a $f(t) + f(x-1-t)$. Luego podemos escribir

$$ \begin{align} f(x) & = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt + \frac{1}{x-1} \int_{t=0}^{x-1} f(x-1-t) \, dt \\ & = 1 + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt + \frac{1}{x-1} \int_{t=0}^{x-1} f(t) \, dt \\ & = 1 + \frac{2}{x-1} \int_{t=0}^{x-1} f(t) \, dt \end{align} $$

Es decir, el valor de $f(x)$ es igual a $1$ más el doble del valor promedio de $f(t)$ sobre el intervalo $t \in [0, x-1]$. Observamos que $f(x) = 0$ para $0 \leq x < 1$, por lo que $f(x) = 1$ para $1 \leq x < 2$. Para $2 \leq x < 3$, escribimos

$$ f(x) = 1 + \frac{2(x-2)}{x-1} $$

y luego para $3 \leq x < 4$,

$$ \begin{align} f(x) & = 1+\frac{2}{x-1} \left(1+\int_{t=2}^{x-1}1+\frac{2(t-2)}{t-1}\,dt\right) \\ & = 1+\frac{2}{x-1} \left(1+\left.(3t-2\ln(t-1))\right]_{t=2}^{x-1}\right) \\ & = 1+\frac{2}{x-1} \left(1+3(x-3)-2\ln(x-2)\right) \\ & = 1+\frac{2}{x-1}\left(3x-8-2\ln(x-2)\right) \end{align} $$

En $x = 4$, esto se evalúa como

$$ f(4) = 1+\frac{4}{3}(2-\ln 2) = \frac{11-4\ln 2}{3} \doteq 2.7425 $$

Respuesta a tu pregunta: Dado que el número de autos estacionados en una carretera de longitud $4$ es casi seguro $2$ o $3$, la probabilidad de que el número de autos estacionados sea $2$ es $3-f(4) = (4\ln 2-2)/3$, y la probabilidad de que el número de autos estacionados sea $3$ es $f(4)-2 = (5-4\ln 2)/3.

Por cierto, parece que mi solución es sustancialmente igual al enlace que proporcionaste. ¡Lo siento! Creo que es simplemente la forma más directa de llegar a la respuesta. No estoy seguro de que haya algún tipo de atajo.

Continuando, para $4 \leq x < 5$, escribimos

$$ \begin{align} f(x) & = 1+\frac{2}{x-1} \left(4-2\ln 2+ \int_{t=3}^{x-1}1+\frac{2}{t-1}(3t-8-2\ln(t-2))\,dt\right) \\ & = 1+\frac{2}{x-1} \left(4-2\ln 2+\left. (7t-10\ln(t-1)-4\ln(t-1)\ln(t-2)-4\text{Li}_2(2-t)) \right]_{t=3}^{x-1}\right) \\ & = 1+\frac{2}{x-1} \left(7x-24+8\ln 2-10\ln(x-2)-4\ln(x-2)\ln(x-3) -\frac{\pi^2}{3}-4\text{Li}_2(3-x)\right) \end{align} $$

En $x = 5$, eso se evalúa como

$$ f(5) = \frac{13}{2}+4\ln 2-5\ln 3-2\ln 2\ln 3-\frac{\pi^2}{6}-2\text{Li}_2(-2) \doteq 3.4851 $$

No veo cómo se obtendría una expresión en forma cerrada para todo $x > 0$, ya que $f(x)$ es agradable y suave solo sobre intervalos de longitud unitaria. Ya se ve bastante feo. Sin embargo, una rápida simulación sugiere que $f(x) \doteq kx$ asintóticamente, con $k$ en las cercanías de $3/4$. Voy a reflexionar sobre si esa densidad límite se puede derivar analíticamente.

ETA: Alguien ya nos ha anticipado. Mira aquí: http://mathworld.wolfram.com/RenyisParkingConstants.html