Versiones no indistinguibles de procesos estocásticos

Esta entrada tiene por objeto mostrar un contraejemplo de dos procesos estocásticos tales que uno es versión del otro, pero no son indistinguibles. La mayoría de elementos de esta entrada se encuentran en el libro de Flemming y Harrington, Counting Processes and Survival Analysis (Wiley, 2005, pp. 16, 326-327).

Cuando definimos un proceso estocástico como en la entrada anterior y \Gamma=\mathbb R^+, se dice que la variable está indexada en el tiempo, y se define un camino aleatorio como la función X(\cdot,\omega):\mathbb R^+\rightarrow\mathbb R. Es decir, para cada elemento \omega\in\Omega, vemos cómo se comporta el proceso a medida que el tiempo va avanzando. Toda propiedad que adjudiquemos al proceso estocástico X, en realidad es una propiedad en un conjunto A\subset\Omega tal que A tiene probabilidad 1.

Ahora, dos variables aleatorias X,Y se dicen equivalentes si \textbf P[X\neq Y]=0, donde el evento \{X\neq Y\} está definido como

\{\omega\in\Omega: X(\omega)\neq Y(\omega)\}.

Quiere esto decir que las variables aleatorias son equivalentes si difieren a lo más en un conjunto de probabilidad nula.

Decimos que el proceso X es una versión del proceso Y si

\forall t\in\mathbb R^+,\ \ \textbf P[\omega\in\Omega:X_t(\omega)\neq Y_t(\omega)]=0,

es decir, el proceso X es una versión de Y si, dado un tiempo t\in\Gamma, se tiene que X_t y Y_t son variables aleatorias equivalentes.

Es posible imponer una restricción más fuerte: Decimos que dos procesos X, Y son indistinguibles si

\textbf P[\omega\in\Omega:\forall t\in\mathbb R^+, X_t(\omega)\neq Y_t(\omega)]=0,

es decir, los procesos son indistinguibles cuando los caminos aleatorios son iguales casi ciertamente (con probabilidad 1).

La diferencia entre versiones de procesos y procesos indistinguibles radica en que en el primer caso el cuantificador se encuentra fuera de la probabilidad, mientras que en el segundo caso es parte del evento de interés. Más aún, es claro que si los procesos X, Y son indistinguibles, entonces uno es una versión del otro. Sin embargo, es menos claro que si X, Y son versiones el uno del otro, entonces los dos procesos son indistinguibles. De hecho, no es cierto en general y se requiere la condición adicional de que los dos procesos sean continuos por derecha o los dos sean continuos por izquierda:

Teorema: Sean dos procesos X, Y ambos continuos por derecha. Se tiene que si X es versión de Y, entonces X, Y son procesos indistinguibles.

Demostración: Considérese \mathbb Q, el conjunto de los racionales. Para cada q\in\mathbb Q, tenemos que

\textbf P[\omega\in\Omega:X_q(\omega)\neq Y_q(\omega)]=0.

Si definimos N\subset\Omega como

N=\bigcup_{q\in\mathbb Q}\{\omega\in\Omega: X_q(\omega)\neq Y_q(\omega)\},

entonces \textbf P[N]=0. Considérense los caminos aleatorios de \omega en X y en Y. Como los dos procesos son continuos por derecha, para todo t\in\mathbb R^+, existe una sucesión de racionales \{q_n\} que decrece a t. De modo que, por la continuidad por derecha,

X_t(\omega)=\lim_{n\rightarrow\infty}X_{q_n}(\omega)=\lim_{n\rightarrow\infty}Y_{q_n}(\omega)=Y_t(\omega).

El teorema anterior también se cumple si la condición de continuidad por derecha se remplaza por la de continuidad por izquierda y su demostración es análoga. Dado el resultado, surge entonces el interés por un contraejemplo: ¿cuándo un par de procesos estocásticos X,Y son versiones el uno del otro pero no son indistinguibles? A continuación construimos dicho contraejemplo:

Ejemplo: Sea \Omega=[0,1], \mathcal B los conjuntos de Borel de \Omega y \textbf P la medida de Lebesgue en dicho espacio muestral. Definimos el proceso Y=\{Y_t(\omega):t\in[0,\infty)\} de la siguiente manera:

Y_t(\omega)=1      si t-\lfloor t\rfloor=\omega,

Y_t(\omega)=0      en otro caso,

donde \lfloor t\rfloor es la parte entera de t.   Entonces puede verse que para un \omega dado, el camino Y_t(\omega) tiene discontinuidades contables. Sin embargo, para t fijo, casi todos los caminos Y_t(\omega) son continuos en t, pues Y es continuo para todo \omega\neq\omega_t=t-\lfloor t\rfloor.

Si ahora definimos el proceso cero X_t=0, para todo t y todo \omega, entonces para todo t fijo tenemos que \textbf P[\omega\in\Omega:X_t(\omega)=Y_t(\omega)]=1, pero la probabilidad del conjunto en el que los caminos coinciden es cero.

Anuncios

Variables aleatorias uniformes en bolas abiertas en el infinito

El siguiente es el Lema 3 en un viejo artículo de Mathew Penrose que estoy estudiando.

Suponga que \textbf X(d) y \textbf Y(d) son variables aleatorias independientes y uniformemente distribuidas en la bola B(0,1) en d dimensiones. Entonces

1.

\lim_{d\rightarrow\infty}\textbf P[|\textbf X(d)|>3/4]=1

2.

\lim_{d\rightarrow\infty}(\sup {\textbf P[|\textbf X(d)-x|\leq1]:x\in\mathbb R^d,|x|\geq 3/4})=0

3.

\lim_{d\rightarrow\infty}\textbf P[|\textbf X(d)-\textbf Y(d)|\leq1]=0.

Prueba:

El número 1 es trivial, pero demostrémoslo aquí en aras de hacer el ejercicio completo:

\textbf P[|\textbf X(d)|>3/4]=1-\textbf P[|\textbf X(d)|\leq3/4]

=1-\frac{\pi_d(3/4)^d}{\pi_d}

=1-(3/4)^d

que tiende a 1 cuando d\rightarrow\infty . Aquí \pi_d es el volumen de la bola de radio 1 en d dimensiones.

Para demostrar el número 2, nótese que

|\textbf X(d)-x|^2=|x|^2+|\textbf X(d)|^2-2|\textbf X(d)\cdot x| .

Por la parte 1, es suficiente probar que |\textbf X(d)\cdot x| converge a 0 en probabilidad y uniformemente en \{x:3/4\leq |x|\leq 2\}. Escríbase \textbf X(d) en coordenadas, como (X^1(d), X^2(d),\ldots,X^d(d)) y x=\{x^1,\ldots,x^d\}. Por simetría (la bola unitaria es igual en todas las direcciones), puede suponerse que x es colineal a e_1=\{1,0,\ldots,0\}, luego \textbf X(d)\cdot x tiene la misma distribución que X^1(d)x^1 y por lo tanto también la misma distribución que |x|X^1(d). De nuevo, por simetría, las componentes de \textbf X(d) tienen todas la misma distribución (así no sean independientes unas de otras); así que, usando el hecho de que la suma de los cuadrados de las componentes es 1, obtenemos que \textbf E[|X^1(d)|^2]\leq 1/d , de modo que X^1(d) converge a 0 en L^2  y, por lo tanto, también en probabilidad.

El número 3 es consecuencia directa del número 1 y el número 2.

László Lovász sobre Very Large Graphs

Grafo original en la página de Rick Durrett

Grafo original en la página de Rick Durrett

Otra de las cosas que quiero hacer con este blog, es mantener informados a los lectores en nuevos escritos relativos a la probabilidad principalmente. Tanto artículos como notas de exposición que sirven de introducción a diferentes temas. La mayoría son interesantes porque tienen que ver con temas actuales de investigación probabilística.

Hoy quiero comenzar con unas de  László Lovász, uno de los matemáticos más conocidos en la combinatoria, ganador del premio Wolf y del premio Knuth en 1999 y el premio Bolyai en 2007, todos por sus contribuciones al área. Lovász subió a arXiv unas notas de exposición llamadas Very Large Graphs. El artículo cubre las relaciones de los grafos muy grandes (hum, no me suena bien en español) con «la probabilidad, el álgebra, la teoría de grafos extremos y el análisis»:

In the last decade it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks: separable elements, with connections (or interactions) between certain pairs of them.

These huge networks pose exciting challenges for the mathematician. Graph Theory (the mathematical theory of networks) faces novel, unconventional problems: these very large networks (like the Internet) are never completely known, in most cases they are not even well defined. Data about them can be collected only by indirect means like random local sampling.

Dense networks (in which a node is adjacent to a positive percent of others nodes) and sparse networks (in which a node has a bounded number of neighbors) show very different behavior. From a practical point of view, sparse networks are more important, but at present we have more complete theoretical results for dense networks. The paper surveys relations with probability, algebra, extrema graph theory, and analysis.

Algoritmo del matrimonio estable de Poisson y Lebesgue

En esta etrada todavía no va a encontrarse mucha cosa muy nueva. Pero sí es importante para las entradas futuras hacer una descripción de cómo sería el algoritmo. El algoritmo del matrimonio estable fue introducido para el caso discreto en el que hay n mujeres y n hombres. La idea en términos muy coloquiales es la siguiente:

DESCRIPCIÓN (MUY) HEURÍSTICA

Suponga que en su barrio solo viven parejas casadas, y suponga que su esposa preferiría estar casada con su vecino y no con usted. Suponga además que su vecino también preferiría estar casado con su esposa y no con la esposa de él. Entonces, como su esposa y su vecino se quieren tanto mutuamente, ellos son una pareja inestable.  Si no hay parejas inestables se dice que el barrio es estable. Note que no basta con que su esposa quiera más a su vecino que a usted pa’ que usted esté en problemas; su vecino también tiene que querer más a su esposa que a la de él. Los dos se tienen que querer más entre ellos que a sus respectivas parejas. Esa aquí es la definición de estabilidad. Intuitivamente esto es acorde con los conceptos de deseo y codicia definidos en la entrada anterior.

Note además que el algoritmo no es solo machista al imaginarse que la esposa es la mala del paseo. También puede verse desde el lado feminista: imagínese la situación de la esposa del vecino. El marido de ella y su esposa (la del lector, no la del vecino), en nuestro ejemplo, siguen siendo la misma pareja inestable. El comentario no busca ser políticamente correcto; más que eso, es una característica interesante del algoritmo y sus generalizaciones.

Eso a nivel matemático es lo que pide el modelo descrito en la entrada anterior: suponga que el conjunto de centros \Xi son los hombres del barrio y las mujeres son los puntos de \mathbb R^d,. Existe un algoritmo que genera un matrimonio estable para ese caso. El algoritmo puede verse como una generalización del propuesto por Gale y Shapley en los 60… así puesto, en la generalización que viene, vale la poligamia para los hombres.

¿Cómo funciona el algoritmo?

Piense de la siguiente manera: Cada hombre (cada centro \xi\in\Xi) tiene un volumen \alpha_\xi de mujeres con quienes se puede casar (lo que llamamos apetito en la entrada anterior).

Cada mujer (los puntos de \mathbb R^d) va a pedirle al hombre que más les gusta que se case con ella y el hombre va a recibirla si no ha copado su número máximo de matrimonios (satisfecho su apetito).

Si el hombre no ha alcanzado su número máximo de esposas, recibe a las que le propusieron matrimonio hasta llegar a ese volumen permitido (cuando satisface su apetito). Si recibe más propuestas que su número de matrimonios permitido, va a escoger las que más le gustan entre las que le propusieron matrimonio hasta colmar su capacidad y va a rechazar a las otras.

Las mujeres que fueron rechazadas pasan a pedirle matrimonio al segundo hombre que más les gusta y las mismas consideraciones del párrafo anterior son válidas también para el segundo hombre. Así cada mujer le pide matrimonio por orden de gusto a todos los hombres hasta que uno de ellos acepte su propuesta… o hasta que se acabe la cantidad de hombres disponibles, en cuyo caso ella quedará soltera. Las muy pocas mujeres a las que dos hombres les gusten igual, salen del juego.

DESCRIPCIÓN FORMAL

Como \Xi es un conjunto discreto de centros en \mathbb R^d, es claro que la medida de Lebesgue de sitios de \mathbb R^d equidistantes a dos centros es nula, luego \mathcal L-c.t. sitio x\in\mathbb R^d no es equidistante a ningún par de centros (donde \mathcal L es la medida de Lebesgue en \mathbb R^d). Ese conjunto de sitios equidistantes a dos centros fue el que en la entrada anterior llamamos \Delta.

Para cada entero positivo n, la etapa n consiste de dos partes:

  1. Cada sitio x\notin\Delta aplica al centro más cercano que no lo haya rechazado en ninguna de las etapas   anteriores.
  2. Para cada centro \xi, sea A_n(\xi) el conjunto de sitios que aplican al centro \xi en la etapa n (a) y defina el radio de rechazo

r_n(\xi)=\inf\left\{r:\mathcal{L}\left(A_n(\xi)\cap B(\xi,r)\right)\geq\alpha_{\xi}\right\}

donde el ínfimo de vacío es \infty. Entonces el centro \xi alista a todos los sitios en A_n(\xi)\cap B(\xi,r_n(\xi)) y rechaza a todos los sitios de A_n(\xi)\setminus B(\xi, r_n(\xi)).

Considere el sitio x\notin\Delta. Puesto que \Xi es discreto lo siguiente es elemental. O  todo centro recahza a x (en orden de distancia creciente de x), o para algún centro \xi y alguna etapa n, x es alistado por \xi en toda etapa después de n. En el primer caso hacemos \psi(x)=\infty (luego x no es reclamado); en el segundo caso hacemos \psi(x)=\xi.

Note que este algoritmo es la mejor para los sitios (son ellos los que escogen a qué centro quieren ir) mientras que es la peor para los centros que no pueden sino recibir lo que les llega. Existe una construcción similar que es la mejor para los centros y la peor para los sitios. Cada uno de estos algoritmos es llamado algoritmo de Gale-Shapley óptimo para los sitios y algoritmo de Gale-Shapley óptimo para los centros, respectivamente.

TEOREMA DE EXISTENCIA

Con la función \psi(\cdot) así construida es muy fácil ya probar el siguiente teorema:

Para cualquier conjunto discreto de centros \Xi\in\mathbb{R}^d, con apetito aleatorio \alpha  de distribución F y realización de apetito \alpha_\xi para todo centro \xi\in\Xi, existe una asignación estable \psi(\cdot) (que corresponde a la descrita en la sección anterior), F-c.c.

Cuando el conjunto de centros \Xi\subset\mathbb R^d es escogido de acuerdo a un proceso puntual ergódico \Pi con ley \textbf P e intesidad finita \lambda, puede mostrarse que \textbf P-c.c. y F-c.c. existe una única función de asignación estable para \Xi=[\Pi], donde los corchetes simbolizan el soporte del proceso, en este caso el proceso  puntual \Pi. Cuando el proceso puntual es un proceso de Poisson entonces la función de asignación asigna conjuntos borelianos en \mathbb R^d con medida de Lebesgue igual al apetito de cada centro Poisson… por eso se llama matrimonio estable de Poisson y Lebesgue.

Introducción al matrimonio estable de Poisson y Lebesgue con apetitos aleatorios

Figura 1

Figura 1

Como hace días no escribo nada por estar tan concentrado en mi tesis, decidí hacer una entrada con la introducción formal al tema. Aquí va.

En un post anterior introduje en términos simples el matrimonio de Poisson y Lebesgue con apetitos aleatorios. Ahora voy a intentar hacer una definición más formal, con base en la descripción dada por los autores originales del modelo. No hay desarrollos nuevos aquí, solo una generalización simple. Tal vez en entradas siguientes introduzca algunos aspectos originales de mi investigación. Por ahora quiero es introducir el objeto de estudio.

Aquí y aquí se consideró el siguiente modelo, la única diferencia acorde con nuestros intereses radica en la aleatorización del parámetro llamado apetito,  que en el modelo original era constante.

Para preservar la notación original, sea \Xi  un conjunto discreto de puntos en \mathbb{R}^d con d\geq1. Los elementos \xi\in\Xi se llaman centros y los elementos x\in\mathbb{R}^d se llaman sitios. El apetito aleatorio es una variable aleatoria (v.a.) no negativa \alpha con ley F, independiente de los centros.  Tómese ahora una sucesión de v.a. i.i.d. no negativas. \left\{\alpha_i\right\} distribuidas como \alpha.

La función \psi:\mathbb{R}^d\rightarrow\Xi\cup\left\{\infty,\Delta\right\} se llamará asignación, donde \psi^{-1}(\Delta) es el conjunto de sitios equidistantes de dos centros diferentes, de modo que \mathcal{L}[\psi^{-1}(\Delta)]=0 porque \Xi es un conjunto discreto . \psi tendrá la propiedad que \mathcal{L}[\psi^{-1}(\xi)]\leq\alpha_{\xi}, para todo \xi\in\Xi donde \alpha_\xi es el apetito del centro \xi y \mathcal{L}(\cdot) es la medida de Lebesgue (volumen) de un conjunto de puntos en \mathbb{R}^d. El territorio de un centro \xi es el conjunto de sitios dados por \psi^{-1}(\xi). Diremos que el centro está satisfecho si \mathcal L[\psi^{-1}(\xi)]=\alpha_\xi e insatisfecho si la medida de Lebesgue del territorio  \xi es estrictamente menor que \alpha_\xi. Diremos que un sitio x es reclamado si \psi(x)\in\Xi, y no reclamado si \psi(x)=\infty lo cual quiere decir que el sitio x no fue reclamado por centro alguno. Adicionalmente, llamaremos \mathcal{C} a la clausura de los sitios reclamados, tal como fue hecho aquí.

Ahora, sea \xi un centro y sea x un sitio con \psi(x)\notin\left\{\xi,\Delta\right\}. Decimos que x desea a \xi cuando \left|x-\xi\right|<\left|x-\psi(x)\right| o cuando x es no reclamado, donde \left|\cdot\right| es la norma euclideana. Y decimos que \xi codicia a x cuando \left|x-\xi\right|<\left|x'-\xi\right| para algún x'\in\psi^{-1}(\xi) o cuando \xi no está satisfecho. Llamaremos a la pareja (x,\xi)  inestable para la asignación \psi si x desea a \xi y además \xi codicia a x. La asignación será estable si no hay parejas inestables.

Las Figuras 1 y 2 en esta entrada muestran el caso de un conjunto de puntos en un subconjunto finito de \mathbb R^2. Para el mismo conjunto de centros se tienen dos apetitos (constante para cada una de las figuras) donde el segundo es mayor que el primero. Las figuras son cortesía de Marcelo Freire… las mías para apetitos aleatorios, no las he hecho :-/

Figura 2

Figura 2