通信网络 （2） 2012级 研究生课程,2. 通信网络分析的数学基础,2.1 随机过程的基本知识,随机过程/随机信号的基本概念确定信号：变化特性完全确知的信号如：当幅度、频率和相位为常数的余弦信号： 随机信号：变化特性不能完全预知的信号如： 其中幅度 、频率 和相位 三个参量中有一个或多个是随机变量的余弦信号。通信系统中的随机信号传输的信息是随机信号（如果是确定信号则不必传输）；各种自然界的干扰和噪声通常是随机信号。,华南理工大学,2.通信网络分析的数学基础,随机过程的概念：随机过程可由有限各或无限多个实现构成，其每个实现可看作某一时间信号，如下图所示：随机过程可表示： 随机过程的样本函数记为：在某一时刻ti ，随机过程实现的样值 为随机变量。通信系统的符号集所对应的信号集可看作随机过程的样本函数。随机过程的统计特性：随机过程的统计特性可由其分布函数、概率密度函数或其各阶矩的数字特征描述。,华南理工大学,2.通信网络分析的数学基础,第2章 信号分析基础,随机过程的概念(续),随机过程的统计特性随机过程的分布函数和概率密度函数：一维分布函数：一维概率密度函数：,华南理工大学,2.通信网络分析的数学基础,随机过程的多维分布函数和概率密度函数：n 维分布函数：n 维概率密度函数：,华南理工大学,2.通信网络分析的数学基础,随机过程的统计特性(续) 两个随机过程的nm维联合分布两个随机过程的nm维联合概率密度函数：,华南理工大学,2.通信网络分析的数学基础,随机过程的统计特性(续) 两个随机过程独立的充要条件对任意的n和m，有或有：,华南理工大学,2.通信网络分析的数学基础,随机过程的统计值 数学期望（均值）：方差：自相关函数：注意：随机过程的相关函数是在定义在统计平均意义的。随机过程的统计值通常是时间的函数,华南理工大学,2.通信网络分析的数学基础,随机过程的统计值(续) 互相关函数：自协方差函数：互协方差函数：,华南理工大学,2.通信网络分析的数学基础,随机变量函数的分布及数字特征 一维随机变量函数的分布 (1) 若 严格单调变化反函数有连续导数则,华南理工大学,2.通信网络分析的数学基础,一维随机变量函数的分布(续) (2) 若 在不重叠的区域逐段严格单调变化，且其相应的反函数有连续导数则,第2章 信号分析基础,随机变量函数的分布随机向量函数的分布函数 若 概率密度函数为则的分布函数,华南理工大学,2.通信网络分析的数学基础,随机变量函数的统计值(数字特征) 随机向量函数的均值可直接由自变量X的概率密度函数计算随机向量函数的均值。同理可得随机变量函数的其他统计特性值。,华南理工大学,2.通信网络分析的数学基础,平稳随机过程(1)严（狭义）平稳随机过程：对任意n和 满足如下关系式的随机过程称之为严平稳随机过程。严平稳随机过程的统计特性不随时间的平移而改变。,华南理工大学,2.通信网络分析的数学基础,平稳随机过程（续）(2)宽（广义）平稳随机过程：满足如下关系式的随机过程为宽平稳随机过程。宽平稳随机过程的一阶矩为常数，二阶矩只与时间差有关。（注：宽平稳随机过程只涉及了其一阶、二阶的统计特性）,华南理工大学,2.通信网络分析的数学基础,平稳随机过程的各态历经性（遍历性）：平稳随机过程的均值、相关函数等统计特性可用其时间平均来计算的随机过程称之（常数）对于各态历经的平稳随机过程：统计平均与时间平均等价,华南理工大学,2.通信网络分析的数学基础,示例 分析随机过程在（-,）上服从均匀分布。 的平稳性和各态历经性。因为所以该随机过程是广义平稳的。,华南理工大学,2.通信网络分析的数学基础,例 (续) 又因为有：比较前面的结果，可见该随机过程具有各态历经性。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(1) 独立过程若随机过程 在任意给定的时刻其分布函数均满足则称该过程为独立过程。独立过程任一时刻的状态与其他时刻的状态无关。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)(2) 马尔可夫过程若对任意的 ，随机过程的 的条件分布有即则称该随机过程为马尔可夫过程 (马氏过程)。马氏过程的特点是无后效性。即 时刻的状态 包含了所有的历史信息。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)(3) 独立增量过程定义 为随机过程在 在时间间隔上的增量。如果对任意的 ，增量是独立的，则称 为独立增量过程。独立增量过程的特点是，只要在时间区域中没有重叠，则该随机过程的增量的取值是独立的。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(4) 泊松(Poisson)过程对于随机过程： 其取值的状态空间为 是非负的整数。(这样的过程也成为计数过程。)若该随机过程满足条件：(a) 是独立增量过程；(b) 对任意的 增量 非负且服从参数为 的泊松分布则称 是具有参数 的泊松过程。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)(4) 泊松(Poisson)过程(续)泊松过程的基本性质a. 到达间隔 服从指数分布相应地其分布函数为从数学上来说，随机过程的到达间隔相互独立且同分布，其分布的概率密度函数服从参数为 指数分布；等价与该随机过程是参数为 的泊松过程。,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)泊松过程的基本性质b. 由可得,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)上面的结果说明：在一个 的充分小的时间内，该计数过程没有到达的概率为：有一个到达的概率为：有一个以上到达的概率为：其中 是 的高阶无穷小。可见在足够小的时间段内，有2个或者2个以上的到达是几乎不可能的小概率事件。c. 多个相互独立的泊松过程： 的和仍然是泊松过程，其到达率为各泊松过程到达率的和,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)示例：有红绿蓝三种颜色的汽车分别以 到达率到达某处，设这三种颜色的汽车的到达是相互独立的。(1) 求任两辆汽车之间的到达时间间隔的概率密度函数；(2) 如在 时刻到达的是一辆红车，下一辆车分别是红车、蓝车和非红车的概率。(3) 如在 时刻观察到一辆红车，接下来三辆是红的，然后来的一辆是非红车的概率。解：(1) 由三种车到达的独立性，总的到达率为其到达间隔的概率密度函数,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)(2) 用不同的下标表示某种车或复合车流的到达率和到达间隔。a. 下一辆车是红车对应事件 ，其概率b. 下一辆车是蓝车对应事件 ，仿上分析可得c. 下一辆是非红车对应事件 ，其概率,华南理工大学,2.通信网络分析的数学基础,几类典型的随机过程(续)(3) 即相当于连续三辆是红车，一辆是非红车的概率。连续三辆红车的概率为下一辆是非红车的概率上述事件均发生的概率相应地为,华南理工大学,2.通信网络分析的数学基础,马尔可夫链马尔可夫链：时间和状态参数取值都是离散的马氏过程。状态转移时刻是可列的：状态的集合是可数的对于马尔可夫链的时间序列 和相应的状态序列马尔可夫链具有性质若马尔可夫链的转移与时间无关，只与转移前后的状态有关 即有则该马尔可夫链称为齐次马尔可夫链。,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)马尔可夫链的概率 称为一步转移概率转移概率也可以用矩阵来描述,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)示例：某随机游走过程如图。图中包含5给停留点(状态)，若游走到两个端点时以概率1返回，在其他点处以1/2概率向左或者向右游走。则相应的转移概率矩阵 随机游走过程状态转移图,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)定义齐次马尔可夫链的 n 步转移概率若则有如下所谓的 ChapmanKolmogorov 等式n 步转移概率示意图,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)互通性：若存在整数 ，使则称状态 i 和 j 是互通的。周期性：在状态 i 下，如果存在某个整数 d ，使成立则称状态 i 是有周期性的；如果马氏链中没有一个状态是有周期性的，则称该马氏链是非周期的。,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)稳态概率：若存在如下的关系式则称 为马氏链的稳态分布。稳态分布反映了系统达到稳态后，处于各个不同状态的概率。状态 j 的稳态分布概率可表示为即无论从哪一个初始状态出发，最终稳定在状态 j 的概率。稳态分布也可直接根据概率来定义,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)全局平衡方程因为从任意状态 j 转移到所有可能状态的概率和总是为1，即因此有因为可得即在稳态情况下，从某一个状态转移出去的概率等于其他所有状态转移进该状态的概率。全局平衡方程可从一个状态推广到一个状态的子集S从某一子集S转移出去的概率等于其他子集转移进子集S的概率。,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)示例：已知状态转移矩阵求各个状态的稳态概率。由稳态概率与状态转移概率间的关系和概率的基本关系式可解得,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)生灭过程：状态转移只可能发生在自身或者相邻状态间的马尔可夫过程。在稳态情况下，有,华南理工大学,2.通信网络分析的数学基础,马尔可夫链(续)示例：已知，求生灭过程的稳态分布。由关系式可得由递推关系得有解的条件由概率的基本关系式最后解得,华南理工大学,2.通信网络分析的数学基础,2.2 图论基础,图论的基本概念图论是瑞士数学家欧拉(1707-1783)创造的。肯尼希城堡的7桥问题肯尼希城堡位于普雷格尔河中的两个小岛，共有7座桥与两岸及彼此相连。问题：从陆地或者岛上任何一个地方出发，能否通过每座桥一次且仅通过一次就能回到原地？欧拉在1736年解决了此问题。欧拉的结论：存在单行曲线的充要条件是，奇次顶点(连接顶点的线段数为奇数)的数目是零。因此上述问题不可能。,2.通信网络分析的数学基础,华南理工大学,图论的基本概念(续)四色问题：一张画在平面或球面上的地图，相邻国家如果涂以不同的颜色，只用四种颜色是否足够？该问题是一位名叫弗南西斯格思里（FrancisGuthrie）英国地图绘图员提出。在随后的一个多世纪都未被证明。1939年证明推进到22国以下的地图可只用四种颜色着色；1950年推进到35国；1960年推进到39国；随后又推进到了50国 美国伊利诺大学哈肯在1970年与阿佩尔合作在两台不同的电子计算机上，用了1200个小时，作了100亿判断，最终完成了四色定理的证明。,