Método probabilístico de Erdős

Question

Mi pregunta se basa en la Erdos método de probabilidades. Estoy tratando de leer el papel aquí. La prueba del Teorema 1 contiene la declaración de

Desde una secuencia de bloque es monocromática con una probabilidad de $2^{1−k}$, se desprende de la linealidad de la expectativa de que el número esperado de monocromático k-término cuasi-progresiones en virtud de un azar coloración es en la mayoría de las $2N^2(c/2)^k/(k − 1)$.

Básicamente entiendo que la probablistic argumento debe ejecutar de la siguiente manera: La probabilidad de un evento en particular,$A$$2^{1−k}$. Podemos entonces concluir que la probabilidad de que el occuurence de alguno de estos eventos está acotada arriba por $2^{1−k}\times$ el número de eventos posibles. El número de posibles eventos está delimitado por encima como por los anteriores argumentos (de acuerdo a mi entendimiento) en el papel por $N(N-k+1)c^k/(k − 1)$, y obligando a $2N(N-k+1)(c/2)^k/(k − 1)$ a menos de $1$ nos dará un enlace para $N$ dentro de la cual si $N$ es elegido el evento deseado no está garantizada y, por tanto, tenemos un límite inferior.

Lo que estoy claro es acerca de los siguientes:

1. La referencia al número esperado ?
2. ¿Por qué es $2N(N-k+1)(c/2)^k/(k − 1)$ no se usa en lugar de $2N^2(c/2)^k/(k − 1)$ ?

Si hay alguna aclaración adicional necesaria estaré encantado de suministro.

Gracias.

Answer 1

(Tenga en cuenta que he usado tanto $K$ $k$ para el papel de la $k$.) Usted obtener fuera de la pista cuando dices

Podemos entonces concluir que la probabilidad de la ocurrencia de cualquier evento está acotada arriba por $2^{1−k}\times$ el número de eventos posibles.

Que producto es en realidad el número esperado de ocurrencias del evento. En ese punto, ha demostrado que si hay en la mayoría de las $c^k$ bloque de secuencias correspondientes a $k$-término cuasi-progresiones de diámetro $1$ tener un particular primer término y la baja diferencia, entonces el número de bloque de secuencias es en la mayoría de los $$(N-k+1)\cdot\frac{N}{k-1}\cdot c^k\;.$$ The probability that any one of them is monochromatic is $\dfrac1{2^{k-1}}$, so by linearity of expectation the expected number of monochromatic sequences is at most $$(N-k+1)\cdot\frac{N}{k-1}\cdot c^k\cdot\frac1{2^{k-1}}\le\frac{2N^2}{k-1}\left(\frac{c}2\right)^k\;.$$

Para poner el asunto en términos cotidianos, si usted es un jugador de baloncesto y tienen una probabilidad de $0.8$ de hacer un tiro libre, y se toma el $1000$ tiros libres, en promedio, usted puede esperar para hacer acerca de $800$ de ellos. Ese es el tipo de razonamiento utilizado aquí, y es matemáticamente justificable.

La sustitución de $(N-k+1)N$ $N^2$ es solo una conveniencia, útil debido a $k$ no está especificado. Incluso si $k=1$ esta versión funciona.

Answer 2

Re 1., la probabilidad de los tiempos de un evento en particular el número de tales eventos es igual al número esperado de eventos que ocurren, si los eventos son equiprobables. Más generalmente, el número esperado de eventos que ocurren es la suma de las probabilidades de los eventos.

Re 2., $(N-k+1)N\leqslant N^2$ simplemente simplifica cálculos posteriores. Si además $k\ll N$, incluso captura la mayor parte del fenómeno.

Answer 3

Un simple ejemplo del método de probabilidades:

Después de algunos cálculos, me parece:

El valor esperado de manchas negras en mi aleatoriamente compró apple es de 0.2. El valor esperado de las manchas marrones en mi aleatoriamente compró apple es 0.295.

Ahora puedo concluir que en la mayoría de los 20% de las manzanas tienen manchas negras (posiblemente menos, si algunas manzanas que tienen más de uno). Y que más del 30% de las manzanas tienen manchas de color marrón. (Tenga en cuenta que yo podría haber dicho 29.5% pero puedo sustituirlo por un simple número más grande y la frase sigue siendo cierto.)

Ahora, puedo concluir que hay manzanas sin puntos negros o marrones (en realidad, al menos el 50% de las manzanas).

En el típico azar gráfico de la aplicación de los números dependen del número de vértices y el número de bordes o en el borde de la probabilidad.

Esto significa que usted realice el mismo cálculo, posiblemente sustituyendo probabilites por simples más grandes expresiones. Y en el final se puede comprobar que para suficientemente grande $N$ (en función de los otros parámetros), la suma es menor que 100%.

Así, el valor esperado se utiliza para obtener un enlace en una dirección, esto también se llama el primer momento del método. Para obtener un atado en la otra dirección, puede utilizar la varianza, ver http://en.wikipedia.org/wiki/Second_moment_method