Problema de valor esperado con los coches en una carretera

Question

Hay una muy larga, recta de la carretera con $N$ coches colocado en algún lugar a lo largo de ella, de forma aleatoria. La carretera es de un solo carril, por lo que los coches no pueden pasar el uno del otro. Cada coche va en la misma dirección, y cada conductor tiene una distinta velocidad positiva en la que ella prefiere viajar. Cada uno de los preferidos de la velocidad es elegido al azar. Cada conductor viaja en su velocidad preferida a menos que ella se queda atascado detrás de un coche más lento, en cuyo caso se le queda pegado detrás del coche más lento. En promedio, ¿cuántos grupos de coches de tiempo se forma? (Un grupo de uno o más autos que viajan a la misma velocidad).

Un amigo me mostró esta pregunta y no sabíamos cómo hacerlo. Me he tomado un curso de probabilidad, así que mi mente se dirigió inmediatamente a los métodos de recuento o la expectativa de los valores, pero no sé si este es el mal de la intuición. Alguien sabe cómo solucionar esto?

Answer 1

el número de grupos es igual al número de coches que son más lentos que cada coche en frente, utilizamos linealidad de expectativa.

¿Cuál es la probabilidad $i$' coche de th (a partir del frente) es más lenta que todos los coches delante de ella? Es $\frac{1}{i}$ porque la probabilidad de que un empate es $0$ y la probabilidad de que cada una de las velocidades del coche de $i$ es el más pequeño es igual (suponiendo que nuestra distribución es razonable).

Por lo tanto el número esperado de grupos es $1+\frac{1}{2}+\dots\frac{1}{n}$

Answer 2

Supongamos que de la $N$ de los coches, el $i$th es el más lento, por lo que el último grupo de coches se compone de todos, pero el primer $i - 1$. En este caso, se espera que el número de $E_i(N)$ de los grupos entre las $N$ coches es $1$ (este último grupo), además de la previsión del número de grupos en la primera $i - 1$ de automóviles, que es, $$E_i(N) = 1 + E(i - 1) .$$

Cada una de las $N$ de los coches tiene la misma probabilidad $\frac{1}{N}$ de ser el más lento, por lo que la cantidad esperada $E(N)$ de los grupos entre las $N$ coches es \begin{align*} E(N) &= \sum_{i = 1}^n P(\textrm{the %#%#%th car is the slowest}) \cdot E_i(N) \\ &= \sum_{i = 1}^n \frac{1}{n} [1 + E(i - 1)] \\ &= 1 + \frac{1}{n} \sum_{i = 1}^{n - 1} E(i) . \end{align*} (En la última igualdad hemos vuelvan a indexar y utiliza el trivial observación de que $i$.) Trabajando fuera de los primeros valores de $E(0) = 0$ sugiere que $E(N)$$$\color{#bf0000}{\boxed{E(N) = H_N := 1 + \frac{1}{2} + \cdots + \frac{1}{N}}} ,$E(N)$ derivados de arriba.

Asintóticamente, tenemos $ and it's straightforward to prove this using induction and the formula for $$$E(N) = H_N = \log N + \gamma + O\left(\tfrac{1}{N}\right),$\gamma \aprox 0.57721$ es el de Euler-Mascheroni constante.

Los números de $ where $ son, por cierto, la armónica de los números, y se muestran en las soluciones de algunos otros famosos puzzles, como el Libro de Apilamiento de Problema y el Cupón de Coleccionista Problema.

Answer 3

Parece que él podría ser, al menos en parte, solucionado con un proceso de marcado punto híbrido (en el sentido que no puede ser una formulación "clásica") en $\mathbb{R}_{\geq 0}$, donde las marcas del proceso punto serían las velocidades respectivas, y el punto del proceso, las posiciones al azar de los vehículos.

Y luego definir un % R.V. $X$para contar el número de grupos que se formarán eventualmente...