講演抄録/キーワード |
講演名 |
2015-01-30 13:00
Intrinsic randomness問題における2次の漸近レートのsmooth Renyiエントロピーによる表現について ○行川瑛一・植松友彦(東工大) IT2014-54 |
抄録 |
(和) |
一般情報源におけるintrinsic randomness問題とは、情報源の出力系列から写像によって一様分布に従う記号列を近似する問題である。乱数生成写像のレートを、生成される一様乱数のサイズの対数と情報源の出力系列長の比によって、また近似誤差を写像によって得られた乱数の確率分布と一様分布との間の変動距離によってそれぞれ定義する。無記憶情報源において、写像のレートが情報源のエントロピーより小さいときは、系列長を大きくするにつれて近似誤差が零に近づく写像が存在する。他方、写像のレートが情報源のエントロピーより大きいときは、どのような写像に対しても、系列長を大きくするにつれて近似誤差が1に近づく。 しかしながら、写像のレートが情報源のエントロピーと一致する場合、近似誤差の値がどのような値を取るかは未知であり、最良の近似誤差の極限値を知るためにはintrinsic randomnessの2次の漸近レートを調べる必要がある。本論文では、与えられた近似誤差に対する2次の漸近レートがsmooth R'{e}nyiエントロピーを用いて表現できることを明らかにし、2次の漸近レートの情報スペクトルを用いない新しい表現を与えている。 |
(英) |
The intrinsic randomness problem is to approximately generate uniform random numbers from output sequences of a general source by using a mapping. In this problem, the rate of mapping for generating random numbers is defined by the ratio of the logarithm of the size of generated random numbers to the length of output sequence of the source, and the approximation error is defined by the variational distance between the probability distribution of random numbers obtained by the mapping and the uniform distributuion. In memoryless sources, whenever the rate of mapping is smaller than the entropy of the source, there exists a sequence of mappings such that the approximation error vanishes as the length of sequences becomes longer. On the other hands, when the rate is greater than the entropy, the approximation error converges to one as the length of sequences becomes longer. However the value of the approximation error is unknown when the rate is equal to the entropy. Hence, we need to investigate the second order asymptotic rate of the intrinsic randomness to know the infimum value of the approximation error. In this paper, we clarify the second order asymptotic rate for a given approximation error in terms of the smooth R'{e}nyi entropy instead of the information spectrum. |
キーワード |
(和) |
intrinsic randomness / $delta$-intrinsic randomness / smooth R'{e}nyi エントロピー / 2次の漸近レート / / / / |
(英) |
Intrinsic randomness / $delta$-intrinsic randomness / smooth R'{e}nyi entropy / second order asymptotic rate / / / / |
文献情報 |
信学技報, vol. 114, no. 438, IT2014-54, pp. 1-6, 2015年1月. |
資料番号 |
IT2014-54 |
発行日 |
2015-01-23 (IT) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
IT2014-54 |
研究会情報 |
研究会 |
IT |
開催期間 |
2015-01-30 - 2015-01-30 |
開催地(和) |
千葉県 柏の葉 東京大学フューチャーセンター |
開催地(英) |
|
テーマ(和) |
一般(東京大学新領域創成科学研究科山本博資研究室と共催) |
テーマ(英) |
general |
講演論文情報の詳細 |
申込み研究会 |
IT |
会議コード |
2015-01-IT |
本文の言語 |
日本語 |
タイトル(和) |
Intrinsic randomness問題における2次の漸近レートのsmooth Renyiエントロピーによる表現について |
サブタイトル(和) |
|
タイトル(英) |
The second order asymptotic rates in intrinsic randomness problem in terms of smooth Renyi entropy |
サブタイトル(英) |
|
キーワード(1)(和/英) |
intrinsic randomness / Intrinsic randomness |
キーワード(2)(和/英) |
$delta$-intrinsic randomness / $delta$-intrinsic randomness |
キーワード(3)(和/英) |
smooth R'{e}nyi エントロピー / smooth R'{e}nyi entropy |
キーワード(4)(和/英) |
2次の漸近レート / second order asymptotic rate |
キーワード(5)(和/英) |
/ |
キーワード(6)(和/英) |
/ |
キーワード(7)(和/英) |
/ |
キーワード(8)(和/英) |
/ |
第1著者 氏名(和/英/ヨミ) |
行川 瑛一 / Eiichi Namekawa / ナメカワ エイイチ |
第1著者 所属(和/英) |
東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech) |
第2著者 氏名(和/英/ヨミ) |
植松 友彦 / Tomohiko Uyematsu / ウエマツ トモヒコ |
第2著者 所属(和/英) |
東京工業大学 (略称: 東工大)
Tokyo Institute of Technology (略称: Tokyo Tech) |
第3著者 氏名(和/英/ヨミ) |
/ / |
第3著者 所属(和/英) |
(略称: )
(略称: ) |
第4著者 氏名(和/英/ヨミ) |
/ / |
第4著者 所属(和/英) |
(略称: )
(略称: ) |
第5著者 氏名(和/英/ヨミ) |
/ / |
第5著者 所属(和/英) |
(略称: )
(略称: ) |
第6著者 氏名(和/英/ヨミ) |
/ / |
第6著者 所属(和/英) |
(略称: )
(略称: ) |
第7著者 氏名(和/英/ヨミ) |
/ / |
第7著者 所属(和/英) |
(略称: )
(略称: ) |
第8著者 氏名(和/英/ヨミ) |
/ / |
第8著者 所属(和/英) |
(略称: )
(略称: ) |
第9著者 氏名(和/英/ヨミ) |
/ / |
第9著者 所属(和/英) |
(略称: )
(略称: ) |
第10著者 氏名(和/英/ヨミ) |
/ / |
第10著者 所属(和/英) |
(略称: )
(略称: ) |
第11著者 氏名(和/英/ヨミ) |
/ / |
第11著者 所属(和/英) |
(略称: )
(略称: ) |
第12著者 氏名(和/英/ヨミ) |
/ / |
第12著者 所属(和/英) |
(略称: )
(略称: ) |
第13著者 氏名(和/英/ヨミ) |
/ / |
第13著者 所属(和/英) |
(略称: )
(略称: ) |
第14著者 氏名(和/英/ヨミ) |
/ / |
第14著者 所属(和/英) |
(略称: )
(略称: ) |
第15著者 氏名(和/英/ヨミ) |
/ / |
第15著者 所属(和/英) |
(略称: )
(略称: ) |
第16著者 氏名(和/英/ヨミ) |
/ / |
第16著者 所属(和/英) |
(略称: )
(略称: ) |
第17著者 氏名(和/英/ヨミ) |
/ / |
第17著者 所属(和/英) |
(略称: )
(略称: ) |
第18著者 氏名(和/英/ヨミ) |
/ / |
第18著者 所属(和/英) |
(略称: )
(略称: ) |
第19著者 氏名(和/英/ヨミ) |
/ / |
第19著者 所属(和/英) |
(略称: )
(略称: ) |
第20著者 氏名(和/英/ヨミ) |
/ / |
第20著者 所属(和/英) |
(略称: )
(略称: ) |
講演者 |
第1著者 |
発表日時 |
2015-01-30 13:00:00 |
発表時間 |
25分 |
申込先研究会 |
IT |
資料番号 |
IT2014-54 |
巻番号(vol) |
vol.114 |
号番号(no) |
no.438 |
ページ範囲 |
pp.1-6 |
ページ数 |
6 |
発行日 |
2015-01-23 (IT) |