Las versiones al azar de los problemas deterministas

Question

¿Cuáles son los ejemplos de situaciones en las que "de forma aleatoria" un problema (o una parte de ella) y analizar el uso de técnicas probabilísticas de los rendimientos de un poco de perspicacia en su versión determinista?

Un ejemplo de lo que tengo en mente: es una conocida conjetura de que la dimensión de Hausdorff de la gráfica de la función de Weierstrass (en todas partes continua, diferenciable) está dada por una cierta fórmula simple, dependiendo de las amplitudes y fases de los cosenos en la serie. Esto es aún abierta; sin embargo, en el documento "la Dimensión de Hausdorff de Gráficas de Funciones de Weierstrass" Caza demostrado que si se agrega un distribuidos de manera uniforme independiente de azar "ruido" para cada fase, la conjetura fórmula sostiene con probabilidad 1. Así, mientras que el "aleatorio" enfoque no resuelve el problema original, que de alguna manera le da credibilidad a la conjetura original y por lo tanto nos da un poco de conocimiento sobre el problema.

Answer 1

Hay varias aplicaciones de la probabilidad para atacar los problemas deterministas. En general, este enfoque se conoce como el "método de probabilidades" o el método de probabilidades de Erdos, el primero que aplicó para resolver una amplia clase de problemas. Para un estudio de la técnica, echa un vistazo Noga Alon y Joel Spencer del libro "El Método de probabilidades".

Un ejemplo específico, debido a Erdos, es una respuesta a Sidón del problema. Sidón pregunta si o no se puede encontrar un conjunto de $B \subset \mathbb{N}$ tal que $|B \cap [1, N]| = N^{1/2 + o(1)}$ para todos los $N$, y de tal manera que $2B = $ {$b_1 + b_2 : b_1, b_2 \in B$ es igual a $\mathbb{N}$. Erdos respondió a esta pregunta en el positivo mediante probabilística de argumentos para demostrar que la $B$'s existe. En particular, si se considera el conjunto aleatorio $B$ definido por $\displaystyle p(x \in B) = \min\left(1, 10 \sqrt{\frac{\log x}{x}}\right)$,, a continuación, $B$ satisface Sidón la condición con probabilidad 1. Hasta la fecha, no explícita ejemplo de este tipo de $B$ se sabe que existe.

Answer 2

Neudecker y Williams demostró que un análogo de la hipótesis de Riemann tiene con probabilidad uno de los números extraídos de un estudio aleatorizado versión de la criba de Eratóstenes.

Answer 3

Hay muchos ejemplos de geometría fractal/sistemas dinámicos (incluyendo, por supuesto, el de la OP).

Por ejemplo, en general es muy difícil para el cálculo de la dimensión (cualquier tipo de dimensión fractal) de un conjunto de invariantes bajo un nonconformal sistema dinámico. Sin embargo, la adición de aleatoriedad hace que la situación sea mucho más fácil. Véase por ejemplo el documento "la dimensión de Hausdorff al azar perturbado auto-afín atractores" por Jordania, Pollicott y Simon.

Un ejemplo relacionado preocupaciones de Bernoulli circunvoluciones y más en general de auto-medidas similares con superposiciones. Muy poco se sabe de casos específicos, pero la aleatoriedad se añade la más fácil, la situación se vuelve. Véase, por ejemplo, el papel de "continuidad Absoluta en el que el azar los sistemas de función iterada con superposiciones" por Peres, Simon y Solomyak, en el que se establezca la continuidad absoluta de una familia de azar medidas, cuya determinista contraparte incluye una medida cuya continuidad absoluta se le preguntó por el Sinaí motivado por las conexiones con la conjetura de Collatz. Es decir, el Sinaí se le preguntó acerca de la continuidad absoluta de la distribución de $\mu_a$ de la serie al azar $$ 1+Z_1+Z_1 Z_2+Z_1 Z_2 Z_3+\ldots, $$ donde $P(Z_i=1+a)=P(Z_i=1-a)=1/2$ para algunos $a\in (0,1)$. (Los autores del artículo citado muestran que si $a>\sqrt{3}/2$ entonces $\mu_a$ es singular, mientras que si $a<\sqrt{3}/2$, entonces una variante de $\mu_a$ en que $Z_i$ tiene un multiplicativo de error aleatorio, es absolutamente continua.)

Answer 4

Estoy seguro de que usted está buscando algo más profundo, pero un ejemplo que me gusta donde el uso de un áspero probabilístico argumento en realidad, da la respuesta correcta es cuando se considera el número de alteraciones (punto fijo gratis permutaciones) de $\{1,2,\ldots, n\}.$ Poniendo el uniforme probabilidad de distribución en $S_n$, la probabilidad de que un determinado símbolo $i$ es fijo por una permutación aleatoria de $\tau$ es $1 - \frac{1}{n}$. Por lo tanto, usted puede esperar que el la probabilidad de que un determinado permutación debe fijar ningún símbolo sería de alrededor de $(1 - \frac{1}{n})^{n}$, por lo que alrededor de $e^{-1}$. Pero todos los tipos de injustificada la independencia supuestos que se han hecho aquí. Sin embargo, si hacemos un análisis más preciso, de inclusión-exclusión argumento muestra que el número de permutaciones en $S_n$ fijación de símbolo no es exactamente $\sum_{j=0}^{n-1} (-1)^{j}$ "n seleccione j" ` $|S_{n-j}|$. Dividiendo por $n!$, nos quedamos con la $n-1$-ésimo grado del polinomio de Taylor para $e^{-x}$ a $x =1$, que pronto se pone muy cerca de $e^{-1}$. El injustificado supuestos de independencia parecen ser compensada por el hecho de que $(1- \frac{1}{n})^{n}$ es sólo una aproximación a $e^{-1}$. De hecho, la proporción de derangments claramente enfoques $e^{-1}$ mucho más rápido que $(1- \frac{1}{n})^{n}$ lo hace.

En otra dirección, hay situaciones en las finita de la teoría de grupo, donde es posible mostrar que la probabilidad de que un determinado par de elementos con propiedades generar el grupo está muy unido a $1$, sin embargo, puede ser muy difícil para exhibir una explícita par de dichos generadores. Ver por ejemplo, el trabajo de Martin Liebeck y varios co-autores sobre este tema.

Answer 5

Uno de los problemas que me doy cuenta de que es el problema de encontrar la distribución de Poisson límite de un colector, que es la delimitada armónica de funciones. Hay un probabilística de la manera de abordar este problema mediante el movimiento Browniano (c.f. aquí), que ha evolucionado a partir de la probabilística de la prueba de la del teorema de Liouville.

Si dejamos $B=(B_t:t \geq 0)$ ser un movimiento Browniano y $Inv(B)$ ser el sigma-álgebra de eventos de la forma $\{B_t \in A\}$ fib $\{B_{t+s}\in A\}$ para todos los $s \geq 0$, entonces no hay una correspondencia uno a uno entre el $Inv(B)$ medibles variables aleatorias y delimitada armónica de funciones.

El teorema de Liouville se aferra $\mathbb{R}^d$ porque si podemos comenzar a dos Browniano movimientos en $x,y \in \mathbb{R}^d$ y el par en un tiempo finito, por lo que el invariante sigma álgebra es trivial. En los colectores donde Liouville del teorema no se cumple, entonces mirando el invariante de álgebra, se puede trabajar con todas las delimitada armónica de funciones.