基本概念
- 随机过程X(t)X(t)是随机变量的集合。根据tt的取值和XX的取值特点,可以分为离散时间、连续时间、离散状态、连续状态
- 马尔科夫性(MP):Pr[Xt∣Xt−1,Xt−2…]=Pr[Xt∣Xt−1]Pr[X_t|X_{t-1}, X_{t-2}…] = Pr[X_t|X_{t-1}],另一种是Pr[Xt+1Xt−1∣Xt]Pr[Xt+1∣Xt]Pr[Xt−1∣Xt]Pr[X_{t+1}X_{t-1}|X_t]Pr[X_{t+1}|X_t]Pr[X_{t-1}|X_t]。
注意,马尔可夫性并不蕴含过去和未来独立,而是说过去对未来的影响都已经蕴含在了现在状态的取值里了。所以其实这个假设并不强,如果对现在的观察足够细致,那么马尔可夫性是可以满足的。后面研究的都是离散时间的,并且是有限状态或可数无穷状态的Markov Chain
- 一步转移矩阵:P=Pij=Pr[Xt=j∣Xt−1=i]P={P_{ij}=Pr[X_t=j|X_{t-1}=i]},由此带来的一系列表示不再赘述pt=pt−1Pp_t=p_{t-1}P,nn步转移PnP^n
- 首达概率rijtr^t_{ij}:从ii出发经过tt步,第一次到达jj的概率。
- 首达期望长度:hii=∑ttriith_{ii}=sum_t t r^t_{ii}
至此,我们只是给出来MC的定义,没有分析任何他的性质,但即使如此,就已经可以分析某些算法问题了。
应用1: 2-SAT算法
- 问题回顾:有nn个布尔变量组成L长度的合取范式(与),每一个子句有两个变量组成析取范式(或),找到一组变量赋值使其满足。
- 算法:一个直观的算法是两阶段思路,先随机指派,然后随机选一个不满足的子句,随机改变其中一个变量的值。直到合法。
- 分析:我们感兴趣的问题是算法需要执行多少次,才有可能以较大的概率返回正确结果。这个问题的分析就利用了MC。
状态表示:状态建模非常有技巧,定义XtX_t表示在t步时,赋值正确变量的数量。那总共会有n+1个状态0,1,…,n0,1,…,n
状态转移分析:P01=1P_{01}=1,对于一般情况Pi,i+1≥12,Pi,i−1≤12P_{i,i+1}ge frac{1}{2}, P_{i,i-1}le frac{1}{2}。这是因为,每次都会选择不合法的子句,那么这个子句里至少有一个变量的赋值是错的,所以选中并修改一个错误赋值的概率至少是12frac{1}{2}
MC的构建:因为上面的概率是个不等关系不好分析,但是如果概率取12frac{1}{2},那分析出来的肯定比实际情况要差,相当于找到了下界,那也是很有价值的。所以建立MC,他的状态是从0~nn,概率转移是P01=1,Pi,i+1=Pi,i−1=12P_{01}=1, P_{i,i+1}=P_{i,i-1}=frac{1}{2}。
步数分析:算法成功意味着从某状态jj转移到nn,中间走了多少步呢?利用期望分析。h0=1+h1h_0=1+h_1,hi=1/2(1+hi−1)+1/2(1+hi+1)h_i=1/2(1+h_{i-1}) + 1/2(1+h_{i+1})。联立一堆方程,可以求出h0=n2h_0=n^2。也就是说最惨假设初始条件一个也没猜对,n2n^2步之后,也期望能求出来正确结果了。如果走2n22n^2步,那不成功的概率就降低到1/21/2,如果是2mn22mn^2步,那就是12mfrac{1}{2^m}(这里不是12mfrac{1}{2m}是因为没有看成一次尝试转移了2mn22mn^2步,而是尝试了mm次算法,每次都走2n22n^2步)
应用2: 3-SAT算法
显然,上面的思路如果直接迁移似乎能解决3-SAT,分析基本一致,唯一的变化是转移概率变为Pi,i+1=1/3,Pi,i−1=2/3P_{i,i+1}=1/3, P_{i,i-1}=2/3。这是因为一个不满足的子句有3个变量,至少有一个不合法,所以随机改对一个的概率至少是1/3。和上面的期望计算一样,可以求出hj=hj+1+2j+2−3h_j=h_{j+1}+2^{j+2}-3,那算法的期望时间变成了Θ(2n)Theta(2^n),这和暴力枚举是一样的,并不好。
从链的角度考虑,这个因为向0移动的概率更大,所以执行步数越多越不好,所以把希望寄托在开局的随机选择上。我们把算法做出如下修改
- 算法:执行mm次:(随机选一个赋值组合,然后执行3n3n次修改)
先考虑初始随机指派,设随机选择的状态有jj个和正确答案不一样,那经过j+2kj+2k步可以到达状态nn的概率为Cj+2kk(2/3)k(1/3)j+kC_{j+2k}^k(2/3)^k(1/3)^{j+k}。相当于向nn行进比向0多了jj次,就可以保证最终到达nn。从jj移动到nn的概率下界qj=∑kCj+2kk(2/3)k(1/3)j+k≥C3jj(2/3)j(1/3)2jq_j = sum_k C_{j+2k}^k(2/3)^k(1/3)^{j+k}ge C_{3j}^j(2/3)^j(1/3)^{2j} (最后一步kk能取jj,这是因为算法修改的次数为3n3n(算法的设计),所以j+2kj+2k需要不大于3n3n,而jj不会大于nn(jj的取值上限是变量数),所以可以取到)。
利用sterlin公式,2πm(me)m≤m!≤22πm(me)msqrt{2pi m}(frac{m}{e})^m le m! le 2sqrt{2pi m}(frac{m}{e})^m,可以推出qj≥cj1/2jq_jge frac{c}{sqrt{j}}1/2^j。因为初始化是随机指派,所以jj的取值是一个满足1/2n1/2^n的均匀分布,所以最后的概率q≥∑jPr[j]qj≥c/n(3/4)nqge sum_j Pr[j]q_j ge c/sqrt{n}(3/4)^n。那期望次数就是1/q1/q,这是我们设置mm的参考。可以看到,虽然还是指数,但是base从2降低到4/34/3。
上面的两个应用只是简单利用了Markov链的建模,以及期望计算过程中的递归效果,下面更进一步挖掘其中的性质,对分析问题有更大帮助。
状态分析
- 相通:两个状态相互可达,即存在某n,使得Pijn>0P^n_{ij}>0。
如果所有状态相通,则链是不可约的。 - 常返:∑tri,it=1sum_t r_{i,i}^t = 1。
- 0常返:hii=E[t]=∑ttri,it=∞h_{ii}=E[t]=sum_t t r_{i,i}^t=infty
- 正常返:hiih_{ii}有限
- 性质:有限状态的MC,至少有一个常返且所有常返都是正常返。相通的状态要么都常返,要么都不常返。
可以这么理解,假设在链上不停转移,那访问的总次数是可数无穷的,但状态是有限的,所以至少有一个状态被访问无限次,那他就是常返的。此外,他被访问的次数是可数无穷,而两次访问的间隔塞不下一个可数无穷了,所以期望有限。
- 遍历:非周期的常返状态。
应用:赌徒问题
两个赌徒A和B,抛公平硬币,正面向上A赢1元,反面向上B赢一元,A和B的赌注分别是lA,lBl_A, l_B,谁先把对方的钱赢完谁就获胜了。分析两者胜率。
MC构建:很明显把A赢的钱设为状态XX,那么初始状态为0,两个结束状态分别是−lA,lB-l_A, l_B。状态转移概率都是1/2。就像拔河一样,一会向左一会向右,一旦越过了−lA-l_A或lBl_B,就结束了。
分析:MC具备非周期、有限的性质。(注意并非不可约,因为终止状态只进不出)。常返状态存在且是正常返。
容易验证,常返状态就是终止状态,因为中间的状态相通所以常返性一样,考虑终止状态相邻的一个状态,这个状态显然不可能常返,因为他一旦进入旁边终止状态就回不来了,因此中间的状态返回的概率不会超过1/2,不常返,又因为整个链至少有一个常返,所以终止状态是常返的。
设PitP_i^t是t步之后在i的概率,那么A的赢钱期望E[Wt]=∑iiPitE[W^t]=sum_i i P_i^t,因为每一步比赛公平,期望为0,那t步和也为0,所以E[Wt]=∑iiPit=0E[W^t]=sum_i i P_i^t=0,两侧取极限,Pit→0(t→∞)P_i^trightarrow 0(trightarrow infty),而P−lAt=(1−p),PlBt=pP^t_{-l_A}=(1-p), P^t_{l_B}=p。带入得,p=lAlA+lBp=frac{l_A}{l_A+l_B}
补充:结束的期望次数为lAlBl_Al_B
稳态分析
如果一个链不可约,那么每一个状态的常返性一样,状态转移看似永不停歇(不像前面赌徒的例子有终止状态)。但其实这里面存在一个动态平衡,即每个状态的访问次数的分布是稳定的。
- 定理:有限、不可约且遍历(非周期常返)的MC,有唯一的平稳分布π=πPpi=pi P,并且πi=limtPijt=limPiit=1hiipi_i=lim_t P^t_{ij}=lim P^t_{ii}=frac{1}{h_{ii}}
- 推广:任何有限MC都有平稳分布,但周期情况不是求极限可解的。
- 性质:平稳分布中,离开一个状态的概率=进入的概率(这说明了平衡)。这很容易想到用割来分析,因为平衡之后,每条边的通量是稳定的,正反向求和为0。
无向图的随机游动模型
- 模型定义:一个连通无向图G=(V,E)G=(V,E),随机选一个点开始,每次等概率转移到它相邻的点。
- 平稳分布:最后会收敛,并且πi=di2∣E∣pi_i = frac{d_i}{2|E|}
证明:这个分布满足进入概率等于离开概率
- 通勤时间性质:如果(u,v)∈E(u,v)in E,则huv+hvu=2∣E∣h_{uv}+h_{vu} =2|E|
- 覆盖时间性质:从一个点出发,访问完所有点的期望时间上界为2∣E∣(∣V∣−1)2|E|(|V|-1)
- 覆盖时间的上下界:H(n−1)minhuv,H(n−1)maxhuvH(n-1)min h_{uv}, H(n-1)max h_{uv}
马尔可夫链的耦合
定量描述到达平稳分布的过程
耦合技术主要用来分析一个MC多快可以达到平稳分布。那首先需要解决的问题是,如何定量描述达到了平稳分布?这里使用变异距离的概念。
- 定义:变异距离
可数状态空间S中的两个分布D1,D2D_1, D_2的变异距离为∣∣D1−D2∣∣=12∑x∈S∣D1(x)−D2(x)∣||D_1-D_2||=frac{1}{2}sum_{xin S}|D_1(x)-D_2(x)|。
很容易理解,就是把每个位置分布的差距求和了。并且乘1/2保证这个值在0~1之间。
对于上面的定义,可以挖掘出一个有用的性质∀A⊆S,∣∣D1−D2∣∣=maxA⊆S∣D1(A)−D2(A)∣forall Asubseteq S, ||D_1-D_2||=max_{Asubseteq S}|D_1(A)-D_2(A)|。这里分布里套集合表示把集合的每一个元素的概率都加起来。
证明:定义S+S^+是D1(x)≥D2(x)D_1(x)ge D_2(x)的元素集合,S−S^-是D1(x)<D2(x)D_1(x)<D_2(x)的元素集合。
有maxA⊆S(D1(A)−D2(A))=D1(S+)−D2(S+)max_{Asubseteq S}(D_1(A)-D_2(A))=D_1(S^+)-D_2(S^+) (就是说求差的最大值就是把所有D1>D2的元素都算进来,这时候差肯定最大)
类似有maxA⊆S(D2(A)−D1(A))=D2(S−)−D1(S−)max_{Asubseteq S}(D_2(A)-D_1(A))=D_2(S^-)-D_1(S^-)
又通过D1(S)=D2(S)=1=D1(S+)+D1(S−)=D2(S+)+D2(S−)D_1(S)=D_2(S)=1=D_1(S^+)+D_1(S^-)=D_2(S^+)+D_2(S^-),经过移项,发现刚好可以凑出前面公式的rhs,因此
D1(S+)−D2(S−)=D2(S+)−D1(S−)D_1(S^+)-D_2(S^-)=D_2(S^+)-D_1(S^-)
maxA⊆S(D1(A)−D2(A))=D1(S+)−D2(S−)=D2(S+)−D1(S−)max_{Asubseteq S}(D_1(A)-D_2(A))=D_1(S^+)-D_2(S^-)=D_2(S^+)-D_1(S^-),加上绝对值
maxA⊆S∣D1(A)−D2(A)∣=∣D1(S+)−D2(S−)∣=∣D2(S+)−D1(S−)∣max_{Asubseteq S}|D_1(A)-D_2(A)|=|D_1(S^+)-D_2(S^-)|=|D_2(S^+)-D_1(S^-)|
最后因为∣D1(S+)−D2(S−)∣+∣D2(S+)−D1(S−)∣|D_1(S^+)-D_2(S^-)|+|D_2(S^+)-D_1(S^-)|的含义恰好是所有状态在两个分布的概率差的和所以等于∑x∣D1(x)−D2(x)∣=2∣∣D1−D2∣∣sum_x |D_1(x)-D_2(x)|=2||D_1-D_2||。
上面两个公式导出结论。
把变异距离的概念套用到平稳分布上,我们定义Δx(t)=∣∣pxt−πˉ∣∣Delta_x(t)=||p^t_x-bar{pi}||。即以x为初始状态出发经过t轮,得到的分布和平稳分布之间的变异距离。并且令Δ(t)=maxxΔx(t)Delta(t)=max_x Delta_x(t)
有了上面的定义和性质(可以作为计算方法),我们有了可操作性的达到平稳分布的判定。接下来直指最核心的问题,需要经过多久达到平稳分布。为此,定义混合时间的概念:τx(ϵ)=min{t:Δx(t)≤ϵ},τ(ϵ)=maxsτs(ϵ)tau_x(epsilon)=min{t: Delta_x(t)le epsilon}, tau(epsilon)=max_s tau_s(epsilon)很直观不再赘述。
构造耦合分析混合时间
耦合的定义
设MtM_t表示一个状态空间为SS的MC,它的耦合是一个MC:Zt=(Xt,Yt)Z_t=(X_t, Y_t)满足:
Pr[Xt+1=x′∣Zt=(x,y)]=Pr[Xt+1=x′∣Mt=x]
Pr[X_{t+1}=x’|Z_t=(x,y)] = Pr[X_{t+1}=x’|M_t=x]
Pr[Yt+1=y′∣Zt=(x,y)]=Pr[Yt+1=y′∣Mt=y]
Pr[Y_{t+1}=y’|Z_t=(x,y)] = Pr[Y_{t+1}=y’|M_t=y]
可以这么理解:显然一个MC的两次独立采样是满足这个条件的。但通常没有用。我们希望让两个MC的实例在转移过程中发生一些关联,但这个关联不会改变他们单独运行的转移概率。后面给个例子去体会。
耦合引理
现在的问题是,这个耦合是如何帮助我们分析混合时间的?答案是耦合引理。它的内容如下
设ZtZ_t是MtM_t的一个耦合,如果存在TT使得对每个x,y∈Sx,yin S,有Pr[Xt≠Yt∣X0=x,Y0=y]≤ϵPr[X_tne Y_t|X_0=x, Y_0=y]le epsilon,则τ(ϵ)≤Ttau(epsilon) le T.
也就是说,如果经历一段时间,两个链不管从哪个状态出发最后状态都几乎是一样的,那混合时间不会超过这个时间。这个思路很像数学分析中的柯西收敛准则,在判断极限的时候不依赖外部给定的极限值,而是通过序列内部靠近的距离来决定。而在这里,我们判断达到平稳分布也不依赖于外部给定的平稳分布,而是通过两个耦合链内部的趋同来确定。
证明:构造耦合,令Y0Y_0是从平稳分布抽取的初始状态,X0X_0是任取的。对任意A⊆SAsubseteq S
Pr[XT∈A]≥Pr[XT=YT∩YT∈A]=1−Pr[XT≠YT∪YT∉A]≥1−Pr[XT≠YT]−Pr[YT∉A]=Pr[YT∈A]−Pr[XT≠YT]≥π(A)−ϵPr[X_Tin A]ge Pr[X_T=Y_Tcap Y_Tin A] = 1 – Pr[X_Tne Y_Tcup Y_Tnotin A] ge 1 – Pr[X_Tne Y_T] – Pr[Y_Tnotin A] = Pr[Y_Tin A]-Pr[X_Tne Y_T]ge pi(A)-epsilon
最后一行,ϵepsilon是按照定义,而πpi是因为Y0Y_0是平稳分布选取的。
对S−AS-A类似可证Pr[XT∈A]≤π(A)+ϵPr[X_Tin A]le pi(A)+epsilon。
所以max∣pxT(A)−π(A)∣≤ϵmax|p_x^T(A)-pi(A)|le epsilon,得证。
这里似乎有点问题,Y直接是平稳分布取的,那是不是要求我们在利用耦合引理时构造耦合必须有一个MC是平稳分布呢?不是的,因为我们可以取一个充分大的T,使至少一个链达到平稳分布。
案例:分析洗牌过程
洗牌的目标:均匀分布从全排列中选择一种
洗牌的操作:随机选一张牌,放到最上面。
问题:经过多少次洗牌,可以让洗牌的结果是全排列的均匀分布?
构造MC:状态是一个牌的排列,相邻定义为可以经过一次洗牌到达的状态。状态转移定义为一次洗牌操作之后到达的状态。因为洗牌操作牌是均匀取的,所以到达某个状态的概率是相等的,为1/n1/n。
根据前一章的分析,平稳分布是均匀分布,所以在这个MC上转移足够多的次数可以达到均匀分布。这也证明了我们这种洗牌操作的可行性。接下来就是最精彩的环节,利用耦合分析经过多少次操作可以实现均匀采样?
构造耦合:两个链XX和YY,初始状态任意。XX链是随机转移的,YY链每次转移选择的牌和XX链相同。容易证明这是一个耦合。因为每张牌在XX和在YY中被选中的概率都是1/n1/n,所以基于耦合ZZ来转移YY(Pr[Yt+1∣Zt]Pr[Y_{t+1}|Z_t])和YY自己去转移(Pr[Yt+1∣Yt]Pr[Y_{t+1}|Y_t]),转移到每个状态的概率是一样的。这里也许可以更好的理解前面耦合的定义。相当于YY把自己的随机性让渡给了XX,但是这个让渡的前提是转移概率保持不变。
分析Pr[XT≠YT]Pr[X_Tne Y_T]的概率。有了耦合,为了利用耦合引理,需要分析经过多长时间两个状态不等的概率就小于ϵepsilon了。这需要结合洗牌过程的特点。我们发现一旦一张牌在XX被选中放在开头,那么耦合的YY也选中了这张牌放在开头。从这之后这张牌的位置在两个链就是一样的了。那么如果每张牌都被选中一次,两个链的状态就完全一样了。因为每次选的牌都是等概率的,所以这就是一个赠券收集模型。预期H(n)=nlnn+cnH(n)=nln n + cn步之后,一张牌从未被选中的概率为(1−1/n)H(n)≤e−cn(1-1/n)^{H(n)} le frac{e^{-c}}{n},为了凑ϵepsilon,取c=−lnϵc=-ln epsilon。这样,T=nlnn−lnϵnT=nln n -ln epsilon n步,两个状态不相等的概率就低于ϵepsilon,按照耦合引理,可以确定混合时间比这个小。
其他可能用到的工具
-
同一条链的两个实例的分布变异距离只减不增:δx(T)=∣∣pxT−pyT∣∣≥δx(T+1)delta_x(T)=||p_x^T-p_y^T||ge delta_x(T+1)
-
几何收敛: 设PP是有限、不可约、非周期的MC转移矩阵,mjm_j是第j列的最小元素,m=∑jmim=sum_j m_i,那么∣∣pxt−π∣∣≤(1−m)t||p_x^t-pi||le (1-m)^t。
-
如果某个c<1/2c < 1/2,有τ(c)≤Ttau(c)le T,那么τ(ϵ)≤⌈lnϵ/ln(2c)T⌉tau(epsilon) le lceil ln epsilon/ln (2c) T rceil
习题
7.20 不公平赌徒破产问题
假设1/3的概率赢1元,2/3概率输1元,开始有ii,游戏结束要么全亏完,要么手上有nn元。设WtW_t是t轮后的总钱数。
- (a) 证明E[2Wt+1]=E[2Wt]E[2^{W_{t+1}}]=E[2^{W_t}]
引入条件期望,E[2Wt+1∣Wt]=132Wt+1+232Wt−1=2WtE[2^{W_{t+1}}|W_{t}]=frac{1}{3} 2^{W_t + 1} + frac{2}{3} 2^{W_t – 1}=2^{W_t}
两边取期望,E[E[2Wt+1∣Wt]]=E[2Wt+1]=E[2Wt]E[E[2^{W_{t+1}}|W_{t}]]=E[2^{W_{t+1}}]=E[2^{W_t}]
- (b) 利用(a)确定从i开始以0结束和以n结束的概率。
设qiq_i表示以0结束的概率,那么1−qi1-q_i为n结束的概率
因为E[2Wt+1]=E[2Wt]E[2^{W_{t+1}}]=E[2^{W_t}],那么递推可得E[2Wt]=E[2W1]=132i+1+232i−1=2iE[2^{W_t}]=E[2^{W_1}]=frac{1}{3} 2^{i+1} + frac{2}{3} 2^{i-1}=2^i
两侧取极限,limt→∞E[2Wt]=qi20+(1−qi)2n=2ilim_{trightarrow infty} E[2^{W_t}] = q_i 2^0 + (1-q_i) 2^n = 2^i
所以qi=2n−2i2n−1q_i = frac{2^n – 2^i}{2^n – 1}
- (c) 把1/3推广到任意的pp。
从(a)的分析可以看到,选一个合适的底数,推导过程是完全一样的。底数需要凑出那个形式,所以取c=1+1+4p(1−p)2pc = frac{1+sqrt{1+4p(1-p)}}{2p}
7.23 网络传播模型
nn台主机相互连通,最开始有一台主机产生了消息,再之后的时间里,每台主机随机选取一台发送消息。分析这个传播过程
- (a) 如何建模成Markov Chain
XkX_k表示kk轮后,收到消息的主机数
- (b) 在已知k−1k-1轮有ii台主机有消息的情况下,确定kk轮后有jj台收到消息的概率。
递推,令P(i,j, c)表示在某一轮,前c个机器选择后,从i台主机有消息变成j台有消息的概率。那么可以得到如下递推式
P(i,j,c)=Pk−1(i,j−1,c−1)n−1−(j−1)n−1+Pk−1(i,j,c−1)j−1n−1P(i,j, c)=P_{k-1}(i, j – 1, c – 1)frac{n – 1 – (j – 1)}{n – 1} + P_{k-1}(i, j, c – 1)frac{j – 1}{n – 1}
就是说,如果前c-1台选完后,已经有j-1台有消息了,那第c台必须再选一个没有消息的。如果第c台选的时候已经有j台有消息了,那必须选之前有消息的,才能保证总共还是j台。
7.26 狼吃羊的问题
假设一个圆盘,等距离标注了0~n-1个点,狼在0处,每次有1/2的概率向左或向右移动一个点,并在第一次到达一个点的时候把羊吃掉。问:哪个位置的羊最后被吃掉的概率最大。
直觉上应该是距离狼最远的位置,也就是0对面。但实际上每个点都是一样的。之所以反直觉,是因为靠近狼的位置并不是最后一个被吃掉的概率降低了,而是在前几次被吃掉的概率变大了,这是两回事。比如和狼紧挨的位置,第一次被吃掉的概率高达1/2,但这不妨碍他最后被吃掉的概率和其他人一样。因为你总是要被吃掉。。。
分析一下被吃掉的概率。首先考虑和狼紧挨的位置1,如果把环从1-2之间劈开(之所以可以劈开,我们只关心第一次到达1的情况,所以到达1之后就结束了,不需要考虑从1到2这条路,此外也不需要关心从2到达1的情况,因为如果从2到1,那其他羊都被吃完了,这样1确实是最后一个,也结束了),那这个问题就变成了赌徒破产问题,1最后被吃掉的概率和到2位置获胜概率一样,为1n−2+1=1n−1frac{1}{n-2+1}=frac{1}{n-1},由对称性,n-1位置也是这个概率。
对于其他位置,ii最后被吃掉,有两种情况:
1 A: 从0走到i-1(不经过i+1),B: 再从i-1走到i+1(不穿过i)
2 C: 从0走到i+1(不经过i-1),D: 再从i+1走到i-1(不穿过i)
每种情况都是两个赌徒破产问题,P=Pr[A]Pr[B]+Pr[C]Pr[D]=i−1n−11n−1+n−in−11n−1P=Pr[A]Pr[B] + Pr[C]Pr[D]=frac{i-1}{n-1}frac{1}{n-1} + frac{n-i}{n-1}frac{1}{n-1}