¿Hay un teorema que se refiere al calcular el número total de un objeto combinatorio con la selección de uno al azar?

Question

Un desafío algorítmico común es generar un objeto de cierto tipo, uniformemente al azar. Por ejemplo, generando una permutación aleatoria de tamaño $ k $ de un conjunto dado (multi) conjunto de $ n $ Personajes, como en esta pregunta .

Me he dado cuenta de que al resolver tales tareas, cualquier algoritmo para calculando el número de tales objetos combinatorios a través de una relación de recurrencia se puede transformar en un algoritmo a generar tales Objetos combinatorios. Mi pregunta es, ¿hay un nombre para esta técnica? ¿Hay un teorema que dice cuándo esto es cierto?

por ejemplo, Supongamos que quiero generar una secuencia aleatoria de $ n $ $ 1 $ s y $ 0 $ s, donde no hay dos $ 1 $ s. Puedo comenzar por dejar que $ a [n] $ sea el número de tales secuencias y observe que $$ a [n]= A [N-1] + A [N-2]. $$

(Esta es la relación Fibonacci). Esto me permite calcular eficientemente una tabla de $ a [i] $ para $ i= 1 $ a $ i= n $ . Ahora, si quiero generar una secuencia al azar, todo lo que tengo que hacer es:

Paso 1: generar un valor aleatorio $ r $ de $ 1 $ a $ a [n] $ .

Paso 2: Use la relación de recurrencia para localizar un subtículo que corresponda al $ r $ th secuencia:

• Si $ r \ le a [n-1] $ , encuentre recursivamente el $ r $ < / span> th Secuencia contada por $ a [n-1] $ y agrega un $ 0 $ .

• de lo contrario, si $ a [n-1] , establecido $ r '= r - a [n-1] $ y encuentra recursivamente el $ r' $ Th secuencia contada por $ a [n-2] $ , y agrega un $ 01 $ .

Lo que parece estar sucediendo aquí es que, dada cualquier relación de recurrencia para $ a [n] $ , puedo transformar esto en un algoritmo recursivo que devuelve el $ r $ Th objeto contado por $ a [n] $ . Estoy asumiendo que esto es conocido, por lo que me interesaría las referencias o los resultados clásicos sobre esto. En particular, esto no es solo específico del ejemplo $ a [n] $ , pero debe ser cierto para cualquier relación de recurrencia que satisface a Cierto propiedades.

también, creo que esto puede estar relacionado con alguna investigación sobre las pruebas aleatorias.

Answer 1

Estos son conocidos como Clasificación y funciones de increíble .Tienes razón en la correspondencia entre las relaciones de recurrencia para contar y algoritmos de increíble.