• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Information Theory, IEEE Transactions on >Optimal Algorithms for Universal Random Number Generation From Finite Memory Sources
【24h】

Optimal Algorithms for Universal Random Number Generation From Finite Memory Sources

机译：从有限内存源生成通用随机数的最佳算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We study random number generators (RNGs), both in the fixed to variable-length (FVR) and the variable to fixed-length (VFR) regimes, in a universal setting in which the input is a finite memory source of arbitrary order and unknown parameters, with arbitrary input and output (finite) alphabet sizes. Applying the method of types, we characterize essentially unique optimal universal RNGs that maximize the expected output (respectively, minimize the expected input) length in the FVR (respectively, VFR) case. For the FVR case, the RNG studied is a generalization of Elias's scheme, while in the VFR case the general scheme is new. We precisely characterize, up to an additive constant, the corresponding expected lengths, which include second-order terms similar to those encountered in universal data compression and universal simulation. Furthermore, in the FVR case, we consider also a twice-universal setting, in which the Markov order k of the input source is also unknown.
机译：我们研究在固定输入到可变长度（FVR）和可变输入到固定长度（VFR）体制下的随机数生成器（RNG），在这种通用设置中，输入是任意阶数的未知有限存储源参数，具有任意输入和输出（有限）字母大小。应用类型方法，我们描述了本质上唯一的最佳通用RNG，它们在FVR（分别为VFR）的情况下最大化了预期输出（分别最小化了预期输入）的长度。对于FVR情况，研究的RNG是Elias方案的推广，而在VFR情况下，常规方案是新的。我们精确地描述了一个相应的预期长度，直到一个加法常数为止，该预期长度包括类似于通用数据压缩和通用模拟中遇到的那些二阶项。此外，在FVR的情况下，我们还要考虑两次通用设置，其中输入源的马尔可夫阶k也未知。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号