Problemas de probabilidad: los coches en la carretera

Question

He oído a este problema, así que puede ser que falten piezas. Imaginemos que hay dos ciudades separadas por un camino muy largo. El camino de un solo carril, por lo que los coches no pueden superar el uno al otro. $N$ coches son liberados de una de las ciudades, los coches viajan a velocidades constantes $V$ elegido al azar y de forma independiente a partir de una distribución de probabilidad $P(V)$. ¿Cuál es el número esperado de grupos de coches de llegar simultáneamente a la otra ciudad?

P. S.: Supuestamente, esta fue una de Princeton física calificador problema, si eso hace una diferencia.

Answer 1

Como Hagen von Eitzen ha señalado, el número de grupos es el número de expediente de baja velocidad como podemos analizar los coches de los coches de primera a la última. Podemos calcular el número esperado de una manera mucho más sencilla. La etiqueta de los coches, en fin empiezan a salir, $1,2,\dots,n$.

Para$i=1$$n$, vamos a $X_1=1$ si car $i$ es más lento que todos los coches $j$$j\lt i$, y deje $X_i=0$ lo contrario. A continuación, el número de $Y$ de registro de bajas velocidades es $\sum_{i=1}^n X_i$. El $X_i$ son no independientes. Sin embargo, por la linealidad de la espera, $$E(Y)=E(X_1+X_2+\cdots+X_n)=E(X_1)+E(X_2)+\cdots +E(X_n).$$ Pero $Pr(X_i=1)=\dfrac{1}{i}$. Esto es debido a que entre los primeros a $i$ coches, cada uno tiene la misma probabilidad de ser el más lento. Por lo que la expectativa es $$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}.$$

Answer 2

Un coche eventualmente (recuerde que el camino es muy largo) estar en el mismo grupo que el antes de que el coche es más lento desde el principio o es el tiempo más lento porque tiene que desacelerar para algunos auto de adelante. En definitiva, un coche va a ser el primer coche de un clúster de iff ninguno de los coches antes de que tenga un ritmo más lento de la velocidad inicial. De ahí que el número de clusters es el número de "nuevos registros" o picos en una secuencia de variables aleatorias. Como cuestión de hecho, la distribución de $V$ no importa (el tiempo es continuo) y uno puede trabajar simplemente con una permutación de velocidades. Deje $F(n,k)$ el conjunto de las permutaciones de $\{1, \ldots,n\}$ $k$ picos y $f(n,k)=|F(n,k)|$. Los elementos de $F(n+1,k)$ que comienzan con $1$ puede ser bijected con $F(n,k-1)$ al caer el líder de $1$ y la disminución de cada número por uno. Los elementos de $F(n+1,k)$ que no comienzan con $1$ puede ser asignada a $F(n,k)$ al caer el uno y la disminución de cada número por uno, pero esta vez cada elemento de a $F(n,k)$ es obtenido $n$ veces (dependiendo de la posición de la $1$). Llegamos a la conclusión de $$\tag1 f(n+1,k) = f(n,k-1) + n f(n,k).$$ En realidad, estamos interesados en $E_n=\frac1{n!}\sum_k k f(n,k)$, se espera que el número de picos en una permutación aleatoria. Sumando $k$ veces (1) $k$ produce $$ \sum_k k f(n+1,k) = \sum_k (k-1) f(n,k-1)+\sum_k f(n,k-1) + n \sum_k kf(n,k)$$ $$ (n+1)! E_{n+1} = n!E_n+\sum_k f(n,k) + n!nE_n.$$ El uso de $\sum_k f(n,k)=n!$, nos encontramos con $$E_{n+1} = E_n+\frac 1{n+1}$$ y con $E_1=1$ vemos thath $E_n$ $n$ésimo número armónico.

Answer 3

Quiero suponer que todos los coches tienen distintas velocidades y se lanzó al mismo tiempo en un orden aleatorio. El coche más lento se acumulan todos los coches detrás de él. El coche más lento no se en que grupo se acumulan todos los coches detrás de él y en la parte delantera del coche más lento. Estos son los grupos que están en el otro extremo.

En este modelo, imaginemos que tenemos el más rápido de $N-1$ en un poco de orden y poner el coche más lento en la lista al azar. El número de coches en el frente de los más lentos serán distribuidos aleatoriamente de$0$$N-1$, por lo que el número esperado de grupos de $E(N)=1+\frac 1N \sum_{i=0}^{N-1}E(i)$$E(0)=0$. Un poco de exploración numérica indica que $E(N)$ es un poco por encima de $\ln (N)$ y la diferencia es muy disminuyendo paulatinamente. Se cae por debajo de $0.6$ $N=22$ y está todavía por encima de la de Euler-Masheroni constante en $N=2700.$

Answer 4

Ya hay dos respuestas que muestran que bajo una determinada interpretación de la pregunta, la respuesta es la $N$-ésimo número armónico. Esto puede ser visto más directamente al señalar que la $k$-th coche es el "líder" de un grupo de iff es el más lento de la primera $k$ de automóviles, lo cual ocurre con probabilidad de $1/k$. Así, el número esperado de líderes de grupos es el $N$-ésimo número armónico, y por supuesto, hay tantos grupos como líderes de los grupos.

Answer 5

Uno de los carriles? No hay adelantamientos? Llegada simultánea? Luego se debe llegar uno por uno, por lo $N$ es el número de grupo de coches. Lo he entendido mal?