信息熵与经验熵:弱典型集

发布时间:2023年12月30日

目录

一. 弱典型集

1.1 基本介绍

1.2 补充弱大数定律

1.3 渐进等分性(AEP)

二. 联合弱典型集

2.1 基本介绍

2.2 联合渐近等分性

2.3互信息相关

三. 与物理层安全的关系

结论


一. 弱典型集

1.1 基本介绍

我们说一个序列很“典型”,通常指的是这个序列能反映总体分布的一些性质。如果一个序列的经验熵(empirical entropy)与随机变量的香农熵非常接近,我们就说这个序列属于弱典型集(weakly typical set)。

接下来我们将以离散型随机变量进行举例子,你可以直接推广到连续型随机变量。不要忘记离散型对应的熵的叫香农熵H,连续型的随机变量对应的熵叫微分熵h.

假定P(X)为某概率分布,\epsilon>0为一个很小的值,一个n长的序列满足如下的条件,就可以被称之为弱典型序列:

|-\frac{1}{n}logP(x^n)-H(X)|\leq \epsilon

其中,-\frac{1}{n}logP(x^n)就可以看成这个序列的经验熵,H(X)为变量真实的香农熵,两者相差不大则称之为弱典型序列。如果将所有的弱典型序列都放在同一个集合中,则形成弱典型集,写做\mathcal{A}_\epsilon^n(X).

引入弱大数定律(weak law of large numbers),可形成信息论安全中很有意思的一个性质叫渐进等分性。

1.2 补充弱大数定律

弱大数定律最早由伯努利发现。当抛硬币次数越多, “正面朝上”的频率越稳定的时候, 某种规律呼之欲出。历史上第一个证明这个规律的人是伯努利。他在《推测术》中以“缶中抽球”的例子来证明的。当然, 抛硬币与缶中抽球本质上是一致的, 为了更加直观,我们还是以抛硬币进行举例。
记 N 次抛硬币中, 事件 A“正面朝上”的次数为X。伯努利企图证明的是:用 \frac{X}{N}估计 p 可以达到事实上的确定性———他称为“道德确定性”( moral certainty) 。其含义很明显, 即用估计 p, 犯错误的概率不超过另外一个极小正数 σ。

这个理论看起来简单,我们尝试把它总结为一个数学定理:

就是现今常见的弱大数定律的表达形式了。
?

1.3 渐进等分性(AEP)

弱大数定律告诉我们,当取的序列长度n足够长时,其频率值是接近概率值的。换句话说,也就是当n足够大时,序列极大可能是属于弱典型集的,如下:

P[X^n\in \mathcal{A}_\epsilon^n(X)]>1-\epsilon

我们知道信息熵是衡量随机变量的不确定程度的,也就是概率值与熵是互相对应的,那么当一个序列属于弱典型集时x^n\in \mathcal{A}_\epsilon^n(X)时,其概率可以根据熵近似计算:

P(x^n)\approx 2^{-nH(X)}

如果你对信息论安全中的渐进性质有过了解的话,这个概率更准确的表达如下:

2^{-n(H(X)+\epsilon)}\leq P(x^n)\leq 2^{-n(H(X)-\epsilon)}

把所有这些弱典型序列集合放在一起,其数量也可以近似计算:

\mathcal{A}_\epsilon^n(X)\approx 2^{nH(X)}

这个数量更准确的表达如下:

(1-\epsilon)2^{n(H(X)-\epsilon)}\leq |\mathcal{A}_\epsilon^n(X)|\leq 2^{n(H(X)+\epsilon)}

二. 联合弱典型集

2.1 基本介绍

P_{XY}代表联合概率,如果X符合弱典型集,Y符合弱典型集,(X,Y)符合联合熵的性质,则说明(X,Y)属于联合弱典型集。这个过程,有三个条件需要满足:

以上式子中出现了联合熵,可以快速回顾下:

H(XY)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}P(x,y)logP(x,y)

总结以上,联合弱典型集表示为\mathcal{A}_\epsilon^n(XY)

2.2 联合渐近等分性

首先,抽取一个序列,它属于弱联合典型集的概率很大,如下:

P[(X^n,Y^n)\in \mathcal{A}_\epsilon^n(XY)]>1-\epsilon

在弱联合典型集中抽取一个联合序列(x^n,y^n)\in \mathcal{A}_\epsilon^n(XY),该联合序列的概率可根据联合熵计算:

2^{-n(H(XY)+\epsilon)}\leq P(x^n,y^n)\leq 2^{-n(H(XY)-\epsilon)}

当序列的长度足够长时,弱联合典型集的基数可计算:

(1-\epsilon)2^{n(H(XY)-\epsilon)}\leq |\mathcal{A}_\epsilon^n(XY)|\leq 2^{n(H(XY)+\epsilon)}

2.3互信息相关

物理层安全中有一个概念,叫互信息,如下:

I(X;Y)=H(X)-H(X|Y)

把H(X)看成一个圈,H(Y)看成一个圈,互信息很像交集的理解。

我们知道联合概率P(x,y)与单个的概率之间是有关系的。假如我分成两步,首先从P_X抽取一个随机序列\tilde X^n,接着首先从P_Y抽取一个随机序列\tilde Y^n,如果不考虑联合分布的话,这样抽取出的序列符合联合弱典型集的概率可以用互信息的角度来衡量,如下:

三. 与物理层安全的关系

ALICE和BOB先互发导频信号,并据此进行信道估计,从而获取L bits的信道信息序列,EVE在此
过程中实施被动窃听。假设ALICE和BOB之间的信道为h_{AB}h_{BA},而ALICE,BOB和EVE之 间 信 道 为h_{AE}h_{BE},通过信道估计得到的是他们的近似值。如下图:

ALICE在t时刻广播发送导频序列,BOB和 EVE通过信道估计得到各自的信道。随后BOB广播发送导频序列,ALICE和和 EVE通过信道估计得到各自的信道。现有的研究结果表明:

(1)合法通信的有效性

通信双方的信道具有短时互易性

(2)安全性

当 EVE与ALICE及BOB的间距超过信号波长的一半时,就可以认为窃听信道与合法通信信道间不相关,而这种情况通常在无线通信中也是普遍存在的,所以EVE估计的信道信息与ALICE及BOB均
不相关。

假设信道慢变的情形,则通过信道估计可以根据导频信号中多个符号得到同一信道特征的不同估计值。鉴于ALICE和BOB估计出的信道具有很高的相关性,可以看作是根据一组独立同分布随机变量产生的序列,不一致位看作是引起的扰动。

根据以上讨论的典型集理论,可得:

结论

随着序列长度L的增大,提取序列为典型序列的概率趋近于1。

证明:

序列的型是字符集中每个字符出现次数的比例,典型集理论相当于集合中的大数定理,当序列中的随机变量服从相同的分布,随着序列长度增大,序列中出现次数比例与随机变量分布越来越接近,所提取序列越接近典型序列。

首先,利用通信双方信道互易性和唯一性的特点,通过估计信道并量化信道响应提取出高度相关但并不完全一致的信道特征序列,然后基于信息论安全和信道编码理论可完成物理层安全通信,借助双方信道特征序列中蕴含的私密共享信息量优势,使合法通信方正确编解码,而第三方只能靠猜测消息码字实施攻击,从而建立不需要密码算法的物理层安全框架。利用典型集理论和窃听信道模型实现了安全性分析,当码本长度趋于无穷大时,攻击性能上下界趋于一致,从而证明了这种方法的可行性。

文章来源:https://blog.csdn.net/forest_LL/article/details/135298099
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。