La contratación de una persona de n - rango y probabilidad

Question

Estoy estudiando algoritmos del libro CLRS. Trato de entender la diferencia entre

• probabilidad de contratación de la $ i $ ª persona fuera de $ n $ y
• probabilidad de contratación de la $ i $ ª persona fuera de $ n $ personas en base a filas.

Uso de la probabilidad normal, sabemos la respuesta a la primera es $ \ frac {1} {ni} $ y se le da la respuesta para el segundo como $ \ frac {1} $ {i} en el libro CLRS . Soy incapaz de entender el concepto aquí. ¿Cómo es $ \ frac {1} {i} $? ¿Puede ser también $ \ frac {1} {n-i} $ en la toma de filas, también?

Tenemos n candidatos alineados para un intertiew.Once un candidato es entrevistado se le da una rank.If la posición del siguiente candidato es mayor la corriente rango mayor es contratado y su rango ahora es el actual rango mayor

HireAssistant(n)
   best=0
   for i=1 to n
       interview candidate i
       if candidate i better than candidate best
          best=i
          hire candidate i

Answer 1

Cuando la gente se entrevistaron después de un al azar orden de llegada, la probabilidad de que el candidato $ i $ de ser contratado es $ \ frac {1} {i} $. Esto se deduce del hecho de que, suponiendo un orden aleatorio de las llegadas, por cada $ i $ $ el grupo de candidatos inicial i $ es al azar, por lo que el $ i $ -ésima candidato tiene una probabilidad $ \ frac {1} {i} $ de ser elegido, que pasa si él / ella está mejor calificado que la anterior $ i-1 $ candidatos.

Ahora, en lugar de considerar un orden aleatorio en las llegadas, imponer su propio orden , con base en filas: el primer candidato es el menos calificado, y el último es el que es el mejor en general . En este caso, si el grupo es de $ n $ candidatos, numerando desde $ 0 $ a $ n-1 $ que se obtiene por la $ i $ º candidato una probabilidad de ser contratado que es $ \ frac {1} {Ni } $, ya que los candidatos están llegando sobre la base de sus filas, y los $ i $ -ésima candidato es siempre mejor calificado que la anterior $ i $-1.

Esta es la razón por la que desea permutar el grupo de candidatos:. Para que ninguna entrada en particular provoca el peor comportamiento caso asociado a la permutación en la que los candidatos se clasifican según el rango

CLRS explica cómo este leves modificaciones le permite contratar, en promedio, $ O (\ lg n) $ candidatos en vez de $ n $ en el peor de los casos. Tenga en cuenta que esto sólo es una garantía probabilístico: nada impide que el generador pseudoaleatorio, si usted es realmente mala suerte, desde la generación de la permutación correspondiente a los candidatos ordenadas por rango. Pero no esperamos que esto suceda con frecuencia: la probabilidad de generar la mala permutación es sólo $ \ frac {1} {n} $ que, por grande $ n $, es muy baja

.