Probabilidad de la cantidad de números igualmente espaciados

Question

Si tiene una muestra uniforme de tamaño $\ell$ de enteros tomados de $[1,\dots,n]$ que luego se ordena, ¿cómo se calcula la probabilidad de que exista una subsecuencia igualmente espaciada de longitud $k$ (o al menos $k$ )?

Por ejemplo, si la muestra es $\{1,5,10, 15,18,20\}$ así que $\ell = 6$ y digamos que $n= 30$ entonces hay una subsecuencia de longitud $4$ que están igualmente espaciados entre sí.

Answer 1

Aquí hay un intento. Parece que a menos que $\ell$ es una fracción constante de $n$ esperamos ver sólo progresiones aritméticas (AP) muy cortas. Por otro lado, si $\ell > \epsilon n$ para alguna constante $\epsilon>0$ entonces habrá APs de longitud logarítmica.

Aquí está la prueba:

Contemos primero cuántas progresiones aritméticas de longitud $t$ hay en el intervalo $[1,n]$ .

Reclamación1: El número de progresiones aritméticas de longitud $t$ en el intervalo $[1,n]$ es $\approx n^2/2t$

Prueba:El número de $t$ -APs con diferencia 1 es $n-t$ . El número de $t$ -APs con diferencia 2 es $n-2t$ . Y así sucesivamente. Por lo tanto, el número de APs en el intervalo $[1,n]$ es $$ (n-t) + (n-2t) + (n-3t) + \dots + (n - \frac{n}{t}t) \approx n^2/2t. $$

Fijemos un $t$ -AP. Nos preguntamos cuál es la probabilidad de que una muestra aleatoria $S \subseteq [n]$ de tamaño $|S| = \ell$ contiene este PA.

Reclamación2: $(\frac{\ell-t}{n-t})^t \leq \Pr[\{1,\dots,t\} \in S] \leq (\frac{\ell}{n})^t$ .

Prueba: Supongamos que elegimos $S$ sin repeticiones. A continuación, $\Pr[\{1,\dots,t\} \subseteq S] = \frac{{n-t \choose \ell - t}}{{n \choose \ell}}$ .

Por lo tanto, el número esperado de $t$ -APs en una aleatoria $S$ es $$ \frac{n^2}{2t} \cdot (\frac{\ell-t}{n-t})^t \leq \mathbb{E}[\text{number of $ t $-APs in $ S $}] \leq \frac{n^2}{2t} \cdot (\frac{\ell}{n})^t $$ Por lo tanto, si $t > \frac{2\log(n)}{\log(n) - \log(\ell)}$ Entonces no esperamos ver $t$ -APs en una muestra aleatoria de longitud $\ell$ .

Por otro lado, si $\ell > n^{1-2/t}$ entonces esperamos ver $t$ -APs.