Dados n trabajos y m procesadores. Utiliza el límite de Chernoff para determinar los límites superior e inferior de los trabajos a completar del tiempo de procesamiento?

Question

En el libro de texto de Mitzenmacher y Upfal, Probabilidad y Computación tenemos una pregunta en el capítulo 4 sobre el límite de Chernoff.

(Mitzenmacher y Upfal) 4.17 Supongamos que tenemos n trabajos para distribuir entre m procesadores. Para simplificar, suponemos que m divide a n. Un trabajo tarda 1 paso con probabilidad p y k>1 pasos con probabilidad 1-p. Utilice el límite de Chernoff para determinar los límites superior e inferior (que se mantienen con alta probabilidad) sobre cuándo se completarán todos los trabajos si asignamos aleatoriamente exactamente n/m trabajos a cada procesador.

Para simplificar la pregunta, supongamos que tenemos una máquina y n trabajos. Ahora, puedo definir una variable aleatoria X_i que es el evento donde los trabajos toman i pasos. Así que, X_i = p si k=1, y X_i= (1-p) si k>1. ¿Cómo resolverías este tipo de pregunta, si das una pista sería suficiente porque la variable aleatoria que definí todavía no es aplicable para el límite de Chernoff; porque no es un camino de Poisson.

Answer 1

Dejemos que $X_i$ sea una variable aleatoria indicadora tal que $$ X_i = \begin{cases} 1 & \text{ the $i$-th job takes $k$ steps} \\ 0 & \text{ otherwise} \end{cases} $$ y $T$ sea la finalización de todos los trabajos. Definir $$ S = \sum_{i=1}^n \left\{k\cdot [X_i=1] + 1\cdot [X_i = 0]\right\} = n + (k - 1)\cdot\sum_{i=1}^n X_i $$ donde $[X_i = 1]$ es igual a $1$ si $X_i = 1$ y $0$ en caso contrario; de forma similar para $[X_i = 0]$ . Tenga en cuenta que $S$ es el tiempo para completar todos los trabajos utilizando una sola máquina. Por lo tanto, $$ \frac{S}{m} \leq T \leq S \tag{$ \N - Traje de espadachín $} $$ Aplicando el límite de Chernoff, se pueden encontrar límites para $\sum_{i=1}^n X_i$ (y por lo tanto $S$ ) con alta probabilidad.