Secuencia aleatoria de enteros en $\{1, 2, \dots, n \}$ que es "en todas partes probablemente en aumento" - ¿cuánto tiempo puede ser?

Question

Dejemos que $D=(d_1,d_2,\dots,d_k)$ sea una secuencia de variables aleatorias correlacionadas. $D$ es "en todas partes $r$ -probablemente creciente" si el evento $d_j > d_i$ tiene probabilidad $\geq r$ para todos $j > i$ .

Fijar $r \geq 1/2$ . ¿Cuánto tiempo puede durar una secuencia aleatoria de enteros en $\{1, 2, \dots, n\}$ ser, y seguir siendo $r$ -¿probablemente en aumento?

Quizás sorprendentemente, la respuesta no es $O(n)$ . Por ejemplo, la secuencia aleatoria que es $(1,1,1,2,2,2,3,3,3)$ con un 50% de probabilidad y $(1,2,3,1,2,3,1,2,3)$ con un 50% de posibilidades está en todas partes $1/2$ -probablemente en aumento. Es fácil generalizar esto para conseguir, cuando $r=1/2$ una secuencia de longitud $n^2$ . Con un poco más de trabajo, cuando $r=a/b$ se puede obtener una secuencia de longitud $\sim n^{b/a}$ .

Conjeturo que la respuesta es $O(n^{1/r})$ . Pero no puedo encontrar ningún documento relevante, y frustrantemente, ni siquiera puedo probar cualquier límite superior para cualquier $r<1$ .

Answer 1

Adapto un argumento de esta entrada de mi blog explotando la $\ell^2$ acotamiento de la transformada discreta de Hilbert (es decir La desigualdad de Hilbert ), para obtener un límite superior exponencial. No veo ninguna manera obvia de mejorar esto a un límite polinómico (EDIT: Una descomposición de Whitney parece hacer el truco, ver más abajo). El argumento se inspira en un resultado de estabilidad de Hrushovski (basado en el teorema de De Finetti) que muestra que algunos El límite finito es posible, aunque no es fácil extraer un límite cuantitativo del argumento de Hrushovski (y si se hiciera, seguramente sería peor que el exponencial); véase la Proposición 2.25 de ese trabajo.

Supongamos que ${\bf P}(d_j > d_i) \geq r$ para algunos $r>1/2$ y todos $1 \le i < j \leq k$ . Entonces, por supuesto $${\bf P}( d_j > d_i) - {\bf P}( d_j < d_i ) \geq 2r-1$$ para todos $1 \le i < j \le k$ . Lo ampliamos como $$ \sum_{1 \leq a < b \leq n} {\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b ) \geq 2r-1.$$ Multiplicar por la cantidad positiva $\frac{1}{j-i}$ y sumar para concluir que $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i < j \leq k} \frac{1}{j-i} [{\bf P}( d_j = b \wedge d_i = a ) - {\bf P}( d_j = a \wedge d_i = b )] \gg (2r-1) k \log k \qquad (1).$$ El LHS se puede reordenar como $$ \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} {\bf P}(d_j = b \wedge d_i = a ) $$ y reordenado como $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a}.$$ Por la desigualdad de Hilbert, tenemos $$ \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll (\sum_{1 \leq j \leq k} 1_{d_j=b})^{1/2} (\sum_{1 \leq i \leq k} 1_{d_i=a})^{1/2}$$ y $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq j \leq k} 1_{d_j=b}, {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i \leq k} 1_{d_i=a} \ll k n $$ así que por Cauchy-Schwarz $$ {\bf E} \sum_{1 \leq a < b \leq n} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_{d_j = b} 1_{d_i = a} \ll kn $$ y por lo tanto $$ kn \gg (2r-1) k \log k$$ lo que lleva al límite superior exponencial $$ k \ll \exp( O( \frac{n}{2r-1} ) ).$$

EDIT: Parece que se puede mejorar esto hasta el límite polinómico $k \ll n^{O(1/(2r-1))}$ utilizando el siguiente truco estándar de descomposición de Whitney (utilizado, por ejemplo, para demostrar el teorema de Rademacher-Menshov o el lema de Christ-Kiselev). En primer lugar, sin pérdida de generalidad, podemos tomar $n$ sea una potencia de 2. Entonces observe que si $1 \leq a < b \leq n$ entonces hay un único par de intervalos diádicos distintos $I,J$ en $\{1,\dots,n\}$ con el mismo padre, de manera que $a \in I$ y $b \in J$ Llamemos a estos pares "adyacentes". De este modo, el lado izquierdo de (1) puede reordenarse como

$$ {\bf E}\sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} \sum_{1 \leq i,j \leq k: i \neq j} \frac{1}{j-i} 1_J(d_j) 1_I(d_i).$$

Aplicamos la desigualdad de Hilbert para acotar esto por $$ \pi {\bf E} \sum_{2^l < n} \sum_{I,J: |I|=|J|=2^l, \hbox{adjacent}} (\sum_j 1_J(d_j))^{1/2} (\sum_i 1_I(d_i))^{1/2}$$ que por Cauchy-Schwarz y la disyunción de la $I,J$ puede ser acotado por $$ \pi \sum_{2^l < n} k^{1/2} k^{1/2} \ll k \log n$$ lo que lleva a $$ k \log n \gg (2r-1) k \log k $$ y por lo tanto $k \ll n^{O(1/(2r-1))}$ .

Answer 2

Utilizando el análisis de Fourier en el $d$ variable, podemos obtener el límite superior óptimo. Como en el argumento de Tao, si existe una distribución de secuencias para la que cada par es $r$ -probablemente creciente, debe haber una única secuencia $d_i$ : tal que:

$$\sum_{1\leq a <b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} >(1+ o(1)) (2r-1) k \log k$$

Podemos reescribir el lado izquierdo como

$$\sum_{1\leq a ,b \leq n} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} 1_{d_i = a} 1_{d_j=b} 1_{a<b}$$

Ahora utiliza la descomposición "llevando el 1":

$$ 1_{a<b} = \frac{b}{n} - \frac{a}{n} + \frac{ a-b \operatorname{mod} n}{n}$$

Los dos primeros términos son bastante sencillos. El primer término es:

$$\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} \frac{d_j}{n} = \sum_{1 \leq j \leq k} \frac{d_j}{n} \log \left( \frac{j}{k-j} \right) \approx k $$

y el segundo término es similar.

Ahora hemos sustituido $1_{a<b}$ con un operador de convolución. Así que tomemos la transformada discreta de Fourier:

$$\frac{1}{n}\sum_{0 \leq \xi \leq n-1} \sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right) \left( \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right)$$

Por la desigualdad de la transformada de Hilbert:

$$\left|\sum_{1 \leq i,j \leq k, i\neq j} \frac{1}{j-i} e\left( \frac{d_j \xi}{n}\right) e\left( \frac{- d_i \xi}{n}\right)\right| \leq \pi k$$

Así que el límite es

$$\frac{\pi k}{n}\sum_{0 \leq \xi \leq n-1}\left| \sum_{x=0}^{n-1} \frac{x}{n} e \left( \frac{x \xi}{n} \right)\right| \approx \frac{\pi k}{n} \sum_{0 \leq \xi \leq n-1} \frac{n}{2 \pi \min(\xi,n-\xi)} \approx k \log n$$

Esto da:

$$k \log n > (1+o(1)) (2r-1) k \log k$$

Por lo tanto:

$$n > k^{ 2r-1 +o(1) }$$

Tenga en cuenta que el truco de la notación base en el post original nos permite eliminar el $o(1)$ en el exponente limitado por la amplificación.

---

Aquí está el límite inferior correspondiente:

Supongamos que tengo dos secuencias de $k$ números, uno de los cuales es una secuencia de números de $1$ a $n_1$ que aumenta con la probabilidad $r_1$ y una que es una secuencia de $1$ a $n_2$ que aumenta con la proobabilidad $r_2$ . Para cualquier fracción $a/b$ puedo construir una secuencia de $k^b$ números de $1$ a $n_1^a n_2^{b-a}$ que aumenta con la probabilidad $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ de la siguiente manera:

Escriba un número de $1$ a $k^b$ en la base $k$ notación como $b$ números de $1$ a $k$ . Elige al azar $a$ de los números y aplicar la primera secuencia, obteniendo un número de $1$ a $n_1$ . Para el resto, aplica la segunda secuencia, obteniendo un número de $1$ a $n_2$ . Codifique esta secuencia de números lexicográficamente como un único número de $1$ a $n_1^a n_2^{b-a}$ (generalizando la notación base).

Para dos números cualesquiera $i$ y $j$ , considere el primer lugar donde no son iguales. En ese lugar, $j$ debe ser mayor que $i$ . $d_j$ es igual a $d_i$ en todos los lugares anteriores. Por lo tanto, mientras $d_j> d_i$ en este lugar, $d_j>d_i$ . La probabilidad de que sea mayor en este lugar es al menos $r_1$ si se elige este número y $r_2$ si no lo fuera, por lo que la probabilidad total es al menos $\frac{a}{b} r_1 + \frac{b-a}{b}r_2$ .

Esto demuestra que podemos tomar $k=n^{1/f(r)}$ para una función convexa $f$ . En particular, porque podemos tomar $f(1)=1$ (secuencia totalmente determinista) y $f(1/2-\epsilon)=0$ (totalmente al azar), sabemos $f(r) \leq 2r-1+\epsilon$ , por lo que podemos obtener $k$ al menos $n^{1/(2r-1)-\epsilon}$

---

Una explicación de por qué $1/(j-i)$ es de hecho la función de peso correcta. Básicamente, este método de delimitación inferior invierte una cantidad igual de trabajo en mejorar la probabilidad de que $d_j>d_i$ para $j-i$ a cualquier escala. Por lo tanto, la función de peso debe hacer que todas las escalas tengan el mismo valor, lo que $1/(j-i)$ lo hace.