Desigualdad de concentración de Talagrand

Desigualdad de tipo isoperimétrico en espacios de productos

En el campo de la teoría de la probabilidad de las matemáticas , la desigualdad de concentración de Talagrand es una desigualdad de tipo isoperimétrico para espacios de probabilidad de producto . ^{[1] [2]} Fue demostrada por primera vez por el matemático francés Michel Talagrand . ^[3] La desigualdad es una de las manifestaciones del fenómeno de concentración de la medida . ^[2]

En términos generales, el producto de la probabilidad de estar en algún subconjunto de un espacio de producto (por ejemplo, estar en uno de algún conjunto de estados descritos por un vector) multiplicado por la probabilidad de estar fuera de un vecindario de ese subespacio al menos a una distancia , está limitado desde arriba por el factor exponencial . Se vuelve rápidamente más improbable estar fuera de un vecindario más grande de una región en un espacio de producto, lo que implica una densidad de probabilidad altamente concentrada para los estados descritos por variables independientes, de manera genérica. La desigualdad se puede utilizar para agilizar los protocolos de optimización al muestrear un subconjunto limitado de la distribución completa y poder limitar la probabilidad de encontrar un valor alejado del promedio de las muestras. ^[4] ${\displaystyle t}$ ${\displaystyle e^{-t^{2}/4}}$

Declaración

La desigualdad establece que si es un espacio de producto dotado de una medida de probabilidad de producto y es un subconjunto en este espacio, entonces para cualquier ${\displaystyle \Omega =\Omega _{1}\times \Omega _{2}\times \cdots \times \Omega _{n}}$ ${\displaystyle A}$ ${\displaystyle t\geq 0}$

${\displaystyle \Pr[A]\cdot \Pr \left[{A_{t}^{c}}\right]\leq e^{-t^{2}/4}\,,}$

¿Dónde está el complemento de donde esto se define por? ${\displaystyle {A_{t}^{c}}}$ ${\displaystyle A_{t}}$

${\displaystyle A_{t}=\{x\in \Omega \colon ~\rho (A,x)\leq t\}}$

¿Y dónde se define la distancia convexa de Talagrand como? ${\displaystyle \rho }$

${\displaystyle \rho (A,x)=\max _{\alpha ,\|\alpha \|_{2}\leq 1}\ \min _{y\in A}\ \sum _{i\colon ~x_{i}\neq y_{i}}\alpha _{i}}$

donde , son vectores -dimensionales con entradas respectivamente y es la -norma. Es decir, ${\displaystyle \alpha \in \mathbf {R} ^{n}}$ ${\displaystyle x,y\in \Omega }$ ${\displaystyle n}$ ${\displaystyle \alpha _{i},x_{i},y_{i}}$ ${\displaystyle \|\cdot \|_{2}}$ ${\displaystyle \ell ^{2}}$

${\displaystyle \|\alpha \|_{2}=\left(\sum _{i}\alpha _{i}^{2}\right)^{1/2}}$

Referencias

1. Alon, Noga; Spencer, Joel H. (2000). El método probabilístico (2.ª ed.). John Wiley & Sons, Inc. ISBN 0-471-37046-0.
2. Ledoux, Michel (2001). El fenómeno de la concentración de la medida . American Mathematical Society. ISBN 0-8218-2864-9.
3. Talagrand, Michel (1995). "Concentración de medida y desigualdades isoperimétricas en espacios de producto". Publications Mathématiques de l'IHÉS . 81 . Springer-Verlag: 73–205. arXiv : math/9406212 . doi :10.1007/BF02699376. ISSN  0073-8301. S2CID  119668709.
4. Castelvecchi, Davide (21 de marzo de 2024). «El matemático que domó la aleatoriedad gana el premio Abel». Nature. doi :10.1038/d41586-024-00839-6.