Un diagrama de flujo para los límites de concentración.

21

Cuando enseño límites de cola, uso la progresión habitual:

  • Si su rv es positivo, puede aplicar la desigualdad de Markov
  • Si tiene independencia y también varianza limitada, puede aplicar la desigualdad de Chebyshev
  • Si cada rv independiente también tiene todos los momentos limitados, entonces puedes usar un límite de Chernoff.

Después de esto, las cosas se ponen un poco menos limpias. Por ejemplo

  • Si sus variables tienen media cero, entonces una desigualdad de Bernstein es más conveniente
  • Si todo lo que sabe es que la función de combinación es Lipschitz, entonces hay una desigualdad generalizada al estilo McDiarmid
  • si tienes una dependencia débil, entonces hay límites de estilo Siegel (y si tienes dependencia negativa, entonces la desigualdad de Jansson podría ser tu amigo)

¿Hay alguna referencia a un diagrama de flujo conveniente o árbol de decisión que describa cómo elegir el límite de cola "correcto" (o incluso cuando tiene que sumergirse en un mar de Talagrand)?

Estoy preguntando en parte para tener una referencia, en parte para poder señalarla a mis alumnos, y en parte porque si estoy lo suficientemente molesta y no hay una, podría intentar hacerla yo mismo.

Suresh Venkat
fuente
Creo que la respuesta simple es no y sí, por favor, a cualquiera que haga una.
Lembik

Respuestas:

11

Fan Chung y Linyuan Lu. Desigualdades de concentración y desigualdades de martingala: una encuesta disponible en http://projecteuclid.org/euclid.im/1175266369 o en la página web de Fan Chung Graham.

Chandra Chekuri
fuente
Si! esto es excelente ! He leído esta encuesta antes, pero la olvidé por completo.
Suresh Venkat
66
Es una encuesta muy buena, pero no veo nada parecido a lo que se solicita en la publicación original: "un diagrama de flujo conveniente o un árbol de decisión que describa cómo elegir el límite de la cola" correcta "para las variables aleatorias que tiene.
usul
No es exactamente correcto, pero hay diagramas de flujo que muestran cómo los diferentes teoremas se implican entre sí, lo cual es un comienzo.
Suresh Venkat