随机数生成的基本信息论问题及其在稀缺资源分配中的应用

This project investigates the fundamental information-theoretic problems of random number generation. The main issues to be studied include: 1) the problem of universal random number generation; 2) the problems of random number generation in a network, such as the intrinsic randomness of correlated sources, the resolvability of multiple-access channels, and so on; and 3) the unified-abstraction issue of the information-theoretic approach and the methodology issue about the combination of information theory and computational complexity theory. The approaches adopted include the information-spectrum approach, the decision-theoretic approach of mathematical statistics, the polar-code-related methods, and the computational-complexity-theoretic approach. As a special application of this research, a novel lottery scheme for solving the social problem of scarce resource allocation will be designed and implemented. Different from existing lottery schemes, this scheme is completely open and transparent, and in particular, immune to fraud.

本项目研究随机数生成的基本信息论问题。主要研究的问题包括：1、通用随机数生成问题；2、网络场景下的随机数生成问题，如相关信源的内在随机性、多接入信道的可解性等；3、信息论方法的统一抽象化问题和信息论与计算复杂性理论相结合的方法论问题。采用的方法包括信息谱方法、数理统计的决策论方法、Polar码相关的方法和计算复杂性方法。作为该项研究的一个特殊应用，本项目将设计实现一个新颖的摇号方案用于解决稀缺资源分配的社会问题。不同于现有的摇号方案，该方案完全公开透明，特别是防作弊。

随机数生成问题是信息科学中的一个基本问题。本项目主要研究了随机数的生成方法以及与其相关的边信息在编码系统中的作用。具体研究内容包括相关信源的定长随机性问题、基于区间算法的随机数生成算法的设计、安全的随机数生成算法的设计、内蕴信道容量问题、编码端拥有含噪信道状态信息的信道容量的噪声阈值现象等。项目取得的重要结果包括：1.设计了一种安全的针对概率分布未知的离散平稳无记忆信源的生成随机数的方法，该方法可以有效阻断攻击者通过操纵部分信源数据来操纵随机数的生成，基本解决了基于公开可见证信源的随机数生成（如摇号）的“防作弊”问题；2.在二元输入信道和广义除删边信道条件下确定了边信道除删概率关于信道容量的普适阈值，首次发现并证明了概率空间中三点共线的概率分布之间相对熵比值的一个紧的上界与下界，这一结果揭示了基于相对熵的概率空间的几何特征；3.提出并分析了信道的最大和最小内蕴容量问题，发现并证明了一个推广的Birkhoff-von Neumann定理。