Sobre la Adivinanza en Dos Etapas
Autores: Graczyk, Robert; Sason, Igal
Idioma: Inglés
Editor: MDPI
Año: 2021
Acceso abierto
Artículo científico
2021
Sobre la Adivinanza en Dos Etapas
Categoría
Gestión y administración
Subcategoría
Gestión de la tecnología y la inovación
Palabras clave
Fuentes
Secuencias aleatorias
Adivinador
Tasa de crecimiento exponencial
Función determinista
Basada en código de Huffman
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 1
Citaciones: Sin citaciones
Las fuentes estacionarias sin memoria producen dos secuencias aleatorias correlacionadas Xn y Yn. Un adivinador busca recuperar Xn en dos etapas, primero adivinando Yn y luego Xn. Las contribuciones de este trabajo son dos: (1) Caracterizamos la tasa de crecimiento exponencial mínima alcanzable (en n) de cualquier momento positivo -ésimo del número total de adivinanzas cuando Yn se obtiene aplicando una función determinista f componente por componente a Xn. Probamos que, dependiendo de f, la tasa de crecimiento exponencial mínima en la configuración de dos etapas es menor que cuando se adivina Xn directamente. Además, proponemos una construcción simple basada en códigos de Huffman de una función f que es un candidato viable para la minimización de la tasa de crecimiento exponencial mínima en la configuración de adivinanza de dos etapas. (2) Caracterizamos la tasa de crecimiento exponencial mínima alcanzable del -ésimo momento del número total de adivinanzas requeridas para recuperar Xn cuando la Etapa 1 no necesita terminar con una adivinanza correcta de Yn y sin suposiciones sobre las fuentes estacionarias sin memoria que producen Xn y Yn.
Descripción
Las fuentes estacionarias sin memoria producen dos secuencias aleatorias correlacionadas Xn y Yn. Un adivinador busca recuperar Xn en dos etapas, primero adivinando Yn y luego Xn. Las contribuciones de este trabajo son dos: (1) Caracterizamos la tasa de crecimiento exponencial mínima alcanzable (en n) de cualquier momento positivo -ésimo del número total de adivinanzas cuando Yn se obtiene aplicando una función determinista f componente por componente a Xn. Probamos que, dependiendo de f, la tasa de crecimiento exponencial mínima en la configuración de dos etapas es menor que cuando se adivina Xn directamente. Además, proponemos una construcción simple basada en códigos de Huffman de una función f que es un candidato viable para la minimización de la tasa de crecimiento exponencial mínima en la configuración de adivinanza de dos etapas. (2) Caracterizamos la tasa de crecimiento exponencial mínima alcanzable del -ésimo momento del número total de adivinanzas requeridas para recuperar Xn cuando la Etapa 1 no necesita terminar con una adivinanza correcta de Yn y sin suposiciones sobre las fuentes estacionarias sin memoria que producen Xn y Yn.