基本介绍 1. 1. 1.任意实数都可以表示为小数的形式：对于有限小数，在其末尾增加无限个 0 0 0，将所有的实数都统一为无限小数。因此实数的表示即为无限小数的表示。
2. 2. 2.考虑 ? x ≥ 0 \forall x\geq 0 ?x≥0，一定可以划分为整数部分 ? x ? \lfloor x \rfloor ?x?，以及小数部分 x ? ? x ? x-\lfloor x \rfloor x??x?，整数部分显然，小数部分可以表示为 ∑ i = 1 ∞ a i p ? i \sum_{i=1}^{∞}a_{i}p^{-i} ∑i=1∞?ai?p?i，即对于前缀 a 1 , a 1 a 2 , . . . . , a 1 . . . a j a_{1},a_{1}a_{2},....,a_{1}...a_{j} a1?,a1?a2?,....,a1?...aj?有以下表示 a 1 / p , ( a 1 p + a 2 ) / p 2 , . . . . , ( a 1 p j ? 1 + . . . + a j ) / p j a_{1}/p,(a_{1}p+a_{2})/p^{2},....,(a_{1}p^{j-1}+...+a_{j})/p^{j} a1?/p,(a1?p+a2?)/p2,....,(a1?pj?1+...+aj?)/pj。
分子部分是 p p p进制下 a 1 . . . a j a_{1}...a_{j} a1?...aj?的数值。
分母部分是正则表示式中 { 1 , . . . , p ? 1 } { 0 , . . . , p ? 1 } ? ∪ { ε } \{1,...,p-1\}\{0,...,p-1\}^{*}∪\{\varepsilon\} {1,...,p?1}{0,...,p?1}?∪{ε}中长度至多为 j j j的单词数量之和（ ( p ? 1 ) ∑ i = 0 j ? 1 p i + 1 = p j ) (p-1)\sum_{i=0}^{j-1}p^{i}+1=p^{j}) (p?1)∑i=0j?1?pi+1=pj)
3 3 3.通过刚才的方法可以表示出 [ 1 p , 1 ] [\frac{1}{p},1] [p1?,1]，为了得到 ? x ∈ [ 0 , 1 ] \forall x\in[0,1] ?x∈[0,1]，可以通过对 x x x乘一个 p k p^{k} pk使得p k x ∈ [ 1 p , 1 ] \ p^{k}x \in[\frac{1}{p},1]pkx∈[p1?,1]，对于指数 k k k很容易保存，这样就表示出了 x ∈ [ 1 p k + 1 , 1 p k ] x\in [\frac{1}{p^{k+1}},\frac{1}{p^{k}}] x∈[pk+11?,pk1?]，这里 x x x可以用和 [ 1 p , 1 ] [\frac{1}{p},1] [p1?,1]同样的方法处理，只是多了 k k k个前导零。因此我们需要关心的只有 [ 1 p , 1 ] [\frac{1}{p},1] [p1?,1]这一部分的实数了。
4. 4. 4.另外对于 x ∈ [ 1 p , 1 ] x\in[\frac{1}{p},1] x∈[p1?,1]，有可能存在超过一种表示。实际上在实数中， 1.999... 1.999... 1.999...与 2.000... 2.000... 2.000...都表示 2 10 \frac{2}{10} 102?，而在这里考虑的是 [ r p n , r + 1 p n ] [\frac{r}{p^{n}},\frac{r+1}{p^n}] [pnr?,pnr+1?]这样的区间。如果数 x x x在区间的端点上，那么它将会有两种不同的表示，否则就有唯一的表示。
前置知识： 1.语言和自动机
∑ \sum ∑：有限字符集
∑ ? \sum^{*} ∑?： 克林闭包
∑ + \sum^{+} ∑+：正闭包
∣ w ∣ |w| ∣w∣： 字符串 w w w的长度
# Q \#Q #Q： 有限集合 Q Q Q的基数
D F A DFA DFA：被 ∑ \sum ∑标记的一个有向图 ( K , s , F , ∑ , δ ) (K,s,F,\sum,δ) (K,s,F,∑,δ)， K K K代表状态的有限集合， s ∈ K s\in K s∈K是一个初始状态， F ? K F\subseteq K F?K是终止状态的集合， δ ： K × ∑ → K δ：K×\sum\rightarrow K δ：K×∑→K是转移函数
识 别 识别 识别：如果一个单词可以从初态出发不断转移最终到达终态，那么这个单词就被识别出来。
语 言 语言 语言：克林闭包的一个子集
正 则 语 言 正则语言 正则语言：如果一个语言中的单词都能够被识别出来，那么该语言被称为正则语言。
L k L_{k} Lk?： { x ∈ ∑ ? , δ ( k , x ) ∈ F } \{ x\in \sum^{*},δ(k,x)\in F\} {x∈∑?,δ(k,x)∈F}，而一般所说的 L L L就是 L s L_{s} Ls?
2.整数的表示
基数序：基数序是用来比较两个单词的大小，对于两个单词 x x x和 y y y，如果（ ∣ x ∣ < ∣ y ∣ ） |x|<|y|） ∣x∣<∣y∣）或者（ ∣ x ∣ = ∣ y ∣ |x|=|y| ∣x∣=∣y∣并且存在某个单词 δ ≤ τ δ\leq \tau δ≤τ,且有 x = w δ x ′ , y = w τ y ′ x=wδx^{'},y=w\tau y^{'} x=wδx′,y=wτy′)，我们就认为 x ≤ y x\leq y x≤y。
代数系统：代数系统定义为一个三元组 ( L , ∑ , < ) (L,\sum,<) (L,∑,<)， L L L是一个无限长度的正则表达式，这个代数系统用以实现 N N N和 L L L的一一映射。
r e p S ( n ) rep_{S}(n) repS?(n)：整数到单词的映射，代表 n + 1 n+1 n+1大的单词。
v a l S ( w ) val_{S}(w) valS?(w)：单词到整数的映射：如果 w w w是第 n + 1 n+1 n+1大的单词，那么 v a l S ( w ) = n val_{S}(w)=n valS?(w)=n。
文章图片
如上图，易见 r e p S ( 4 ) = a b rep_{S}(4)=ab repS?(4)=ab， v a l S ( a b a ) = 12 val_{S}(aba)=12 valS?(aba)=12。
对于 r e p S ( k ) rep_{S}(k) repS?(k)和 v a l S ( k ) val_{S}(k) valS?(k)，可以通过贪心算法构造出来。
更一般地，对于 ? k ∈ K \forall k \in K ?k∈K，通过 L k L_{k} Lk?构造出来新的代数系统 S k = ( L k , ∑ , < ) S_{k}=(L_{k},\sum,<) Sk?=(Lk?,∑,<)，相应的函数则为 r e p S k rep_{S_{k}} repSk??和 v a l S k val_{S_{k}} valSk??，在不混淆的情形下，大写的 S S S可以被省略。
u l ( k ) u_{l}(k) ul?(k)： u l ( k ) = # ( L k ∩ ∑ l ) u_{l}(k)=\#(L_{k}∩\sum^{l}) ul?(k)=#(Lk?∩∑l)，实际上就是所有从状态 k k k出发通过 l l l次转移正好被接收的单词的数量。
v l ( k ) v_{l}(k) vl?(k)： v l ( k ) = ∑ i = 0 l u l ( k ) v_{l}(k)=\sum_{i=0}^{l}u_{l}(k) vl?(k)=∑i=0l?ul?(k)，实际上就是所有从状态 k k k出发在 l l l次转移之内被接受的单词的数量。
特别地，对于 u l ( s ) u_{l}(s) ul?(s)和 v l ( s ) v_{l}(s) vl?(s)在不至引起混淆的情形下可以简写为 u l u_{l} ul?和 v l v_{l} vl?。
【正则表达式表示实数】定理1：如果 σ w ∈ L k σw\in L_{k} σw∈Lk?，并且满足 σ ∈ ∑ σ\in \sum σ∈∑， w ∈ ∑ + w\in \sum^{+} w∈∑+，那么 v a l k ( σ w ) = v a l k . σ ( w ) + v ∣ w ∣ ( k ) ? v ∣ w ∣ ? 1 ( k . σ ) + ∑ σ ′ < σ u ∣ w ∣ ( k . σ ′ ) val_{k}(σw)=val_{k.σ}(w)+v_{|w|}(k)-v_{|w|-1}(k.σ)+\sum_{σ^{'}<σ}u_{|w|}(k.σ^{'}) valk?(σw)=valk.σ?(w)+v∣w∣?(k)?v∣w∣?1?(k.σ)+∑σ′<σ?u∣w∣?(k.σ′)
证明：选取第一个字符 c ∈ ∑ c\in\sum c∈∑，若字符 c = σ c=σ c=σ为第一项，若字符 c < σ c<σ c<σ且长度为 ∣ w ∣ + 1 |w|+1 ∣w∣+1为第四项，若长度小于 ∣ w ∣ + 1 |w|+1 ∣w∣+1的为第二项，容斥掉 c = σ c=σ c=σ并且长度小于 ∣ w ∣ + 1 |w|+1 ∣w∣+1的重复的一部分。
定理2：如果 σ ∈ ∑ σ\in \sum σ∈∑，那么 v a l k ( σ ) = u 0 ( k ) + ∑ σ ′ < σ u 0 ( k . σ ′ ) val_{k}(σ)=u_{0}(k)+\sum_{σ^{'}<σ}u_{0}(k.σ^{'}) valk?(σ)=u0?(k)+∑σ′<σ?u0?(k.σ′)
证明：比较显然。
通过定理1和定理2，可以得到对于 w = w l . . . w 1 ∈ L k w=w_{l}...w_{1}\in L_{k} w=wl?...w1?∈Lk?，可以得到以下的公式：
v a l k ( w ) = v l ? 1 ( k ) + ∑ σ < w l u l ? 1 ( k . σ ) + . . . + ∑ σ < w 2 u 1 ( k . w l . . . w 3 σ ) ? v 0 ( k . w l . . . w 2 ) + v a l k . w l . . . w 2 ( w 1 ) val_{k}(w)=v_{l-1}(k)+\sum_{σ
v a l k ( w ) = ∑ q ∈ K ∑ i = 1 ∣ w ∣ ? 1 β q , i ( k , w ) u i ( q ) val_{k}(w)=\sum_{q\in K}\sum_{i=1}^{|w|-1}β_{q,i}(k,w)u_{i}(q) valk?(w)=∑q∈K?∑i=1∣w∣?1?βq,i?(k,w)ui?(q)
其中 β q , i ( k , w ) β_{q,i}(k,w) βq,i?(k,w)是一个常数，它的大小不超过 # ∑ + δ k , q \#\sum+δ_{k,q} #∑+δk,q?
3.无穷单词
∑ w \sum^{w} ∑w：定义为无穷长度正则表达式的集合。
子串：对于单词 w = w 0 w 1 . . . w ∣ w ∣ ? 1 w=w_{0}w_{1}...w_{|w|-1} w=w0?w1?...w∣w∣?1?，如果 0 < l ≤ r < ∣ w ∣ 0
如果某个单词序列 w n ∈ ∑ ? w_{n}\in \sum^{*} wn?∈∑?满足 ? l ∈ N , ? N ∈ N , ? n > N , w n [ 0 , l ] = w [ 0 , l ] \forall l \in N,\exist N \in N ,\forall n>N,w_{n}[0,l]=w[0,l] ?l∈N,?N∈N,?n>N,wn?[0,l]=w[0,l]。记为 l i m n → ∞ w n = w lim_{n\rightarrow∞}w_{n}=w limn→∞?wn?=w。
具体地说：对于任意长度的前缀，都满足存在一个自然数 N N N，并且这个序列存在 n n n，使得 n ≥ N n\geq N n≥N的 w n w_{n} wn?都和 w w w相同，那么 w n → w w_{n}\rightarrow w wn?→w。
另外一种定义极限的方法是定义两个串 x x x和 y y y的距离 d ( x , y ) d(x,y) d(x,y)。
d ( x , y ) = 2 ? n , n = i n f { j : x [ j , j ] =? y [ j , j ] , ( x =? y ) d(x,y)=2^{-n},n=inf\{j:x[j,j]\not = y[j,j],(x\not = y) d(x,y)=2?n,n=inf{j:x[j,j]?=y[j,j],(x?=y)
d ( x , y ) = ∞ , ( x = y ) d(x,y)=∞,(x=y) d(x,y)=∞,(x=y)
然后对于所有的有限单词 x x x都定义为 x τ w , τ ∈? ∑ x\tau^{w},\tau\not \in \sum xτw,τ?∈∑，那么 w n w_{n} wn?收敛于 w w w就对应为拓扑空间 ( ∑ ∪ { τ } ) w (\sum∪\{\tau\})^{w} (∑∪{τ})w上 w n w_{n} wn?的极限为 w w w。
如果 L L L是一个语言。
定义 L ∞ L_{∞} L∞?是有无穷多个前缀在 L L L中的无穷单词的集合， L ∞ = { w ∈ ∑ w ∣ ? w n : w [ 0 , n ] ∈ L } L_{∞}=\{w\in \sum^{w}|\exist^{w}n:w[0,n]\in L\} L∞?={w∈∑w∣?wn:w[0,n]∈L}，这里 ? w \exist^{w} ?w代表存在无穷多个 n n n。
定义 L ∞ = { w ∈ ∑ w ∣ ? ( w n ) n ∈ N ∈ L N : l i m n → ∞ w n = w } \mathscr L_{∞}=\{w\in \sum^{w}|\exist(w_{n})_{n\in N}\in L^{N}:lim_{n\rightarrow∞}w_{n}=w\} L∞?={w∈∑w∣?(wn?)n∈N?∈LN:limn→∞?wn?=w}
注意到有 L ∞ ? L ∞ L_{∞}\sub \mathscr L_{∞} L∞??L∞?
一些问题 分别要解决以下问题：
1. 1. 1.L ∞ L_{∞} L∞?和 L ∞ \mathscr L_{∞} L∞?的不可数性。
2. 2. 2. 极限 lim ? n → ∞ v a l S ( w n ) v ∣ w n ∣ \lim_{n\rightarrow∞}\frac{val_{S}(w_{n})}{v_{|w_{n}|}} limn→∞?v∣wn?∣?valS?(wn?)?的存在性。
L ∞ L_{∞} L∞?和 L ∞ \mathscr L_{∞} L∞?的不可数性 1.1 1.1 1.1L ∞ \mathscr L_{∞} L∞?的不可数性。
如果可以从 s s s到状态 k k k，那么说这个状态是 a c c e s s i b l e accessible accessible的。如果可以从状态 k k k到 F F F，那么说这个状态是 c o a c c e s s i b l e coaccessible coaccessible的。
定理3：集合 L ∞ \mathscr L_{∞} L∞?是不可数的当且仅当 D F A DFA DFA上存在两个互异的环 ( p 1 , . . . . p r , p 1 ) (p_{1},....p_{r},p_{1}) (p1?,....pr?,p1?)和 ( q 1 , . . . q t , q 1 ) (q_{1},...q_{t},q_{1}) (q1?,...qt?,q1?)满足以下的条件：
1. 1. 1.p 1 = q 1 p_{1}=q_{1} p1?=q1?，
2. 2. 2.{ p 1 , . . . . , p r , q 1 , . . . , q t } \{p_{1},....,p_{r},q_{1},...,q_{t}\} {p1?,....,pr?,q1?,...,qt?}存在一个 a c c e s s i b l e accessible accessible的状态，
3. 3. 3.{ p 1 , . . . . , p r , q 1 , . . . , q t } \{p_{1},....,p_{r},q_{1},...,q_{t}\} {p1?,....,pr?,q1?,...,qt?}存在一个 c o a c c e s s i b l e coaccessible coaccessible的状态。
证明：
充分性：定义 c c c是 a c c e s s i b l e accessible accessible， d d d是 c o a c c e s s i b l e coaccessible coaccessible，显然存在 w , w ′ w,w^{'} w,w′使得 s . w = c s.w=c s.w=c并且 d . w ′ ∈ F d.w^{'}\in F d.w′∈F，并且定义 y 0 , y 1 y_{0},y_{1} y0?,y1?分别为 ( p 1 , p 2 . . . p r , p 1 ) (p_{1},p_{2}...p_{r},p_{1}) (p1?,p2?...pr?,p1?), ( q 1 , q 2 . . . q t , q 1 ) (q_{1},q_{2}...q_{t},q_{1}) (q1?,q2?...qt?,q1?)的路径，显然可以构造出一个序列 w x y f ( 0 ) y f ( 1 ) . . . . y f ( i ) x ′ w ′ wxy_{f(0)}y_{f(1)}....y_{f(i)}x^{'}w^{'} wxyf(0)?yf(1)?....yf(i)?x′w′，对于 f =? g f\not =g f?=g，有 y f =? y g y_{f}\not=y_{g} yf??=yg?，本质上是一个实数的二进制表示，所以是不可数的。充分性得证。
必要性：假设任何一个状态转移的路径从 s s s开始到 F F F中某一个结束，最多只会属于一个环。换句话说，如果 x y z ∈ L xyz\in L xyz∈L，满足 s . x s.x s.x属于环 ( s . x , p 2 , . . . p r , s . x ) (s.x,p_{2},...p_{r},s.x) (s.x,p2?,...pr?,s.x)， s . x y s.xy s.xy属于环 ( s . x y , q 2 , . . . q t ) (s.xy,q_{2},...q{t}) (s.xy,q2?,...qt)，并且这两个环没有任何交集。
L L L可以写成以下的形式:
λ 1 μ 1 ? λ 2 μ 2 ? . . . λ j μ j ? λ j + 1 \lambda_{1}\mu_{1}^{*}\lambda_{2}\mu_{2}^{*}...\lambda_{j}\mu_{j}^{*}\lambda_{j+1} λ1?μ1??λ2?μ2??...λj?μj??λj+1?， λ i , μ i ∈ ∑ ? \lambda_{i},\mu_{i}\in \sum^{*} λi?,μi?∈∑?.
那么对于 m ∈ L ∞ m\in\mathscr L_{∞} m∈L∞?，按照定义它应该有无穷多个公共前缀，那么这些前缀应该是以下的形式之一：
λ 1 μ 1 w , λ 1 μ 1 n 1 λ 2 μ 2 w , . . . , λ 1 μ 1 n 1 λ 2 μ 2 n 2 . . . μ j ? 1 n j ? 1 λ j μ j w \lambda_{1}\mu_{1}^{w},\lambda_{1}\mu_{1}^{n_{1}}\lambda_{2}\mu_{2}^{w},...,\lambda_{1}\mu_{1}^{n_{1}}\lambda_{2}\mu_{2}^{n_{2}}...\mu_{j-1}^{n_{j-1}}\lambda_{j}\mu_{j}^{w} λ1?μ1w?,λ1?μ1n1??λ2?μ2w?,...,λ1?μ1n1??λ2?μ2n2??...μj?1nj?1??λj?μjw?， n 1 , . . . . , n j ? 1 ∈ N n_{1},....,n_{j-1}\in N n1?,....,nj?1?∈N
这个序列是可数的，这和 L ∞ \mathscr L_{∞} L∞?不可数是矛盾的，所以假设不成立。必要性得证。
1.2 1.2 1.2L ∞ L_{∞} L∞?的不可数性。
定理4：集合 L ∞ L_{∞} L∞?是不可数的当且仅当 D F A DFA DFA上存在两个互异的环 ( p 1 , . . . . p r , p 1 ) (p_{1},....p_{r},p_{1}) (p1?,....pr?,p1?)和 ( q 1 , . . . q t , q 1 ) (q_{1},...q_{t},q_{1}) (q1?,...qt?,q1?)满足以下的条件：
1. 1. 1.p 1 = q 1 p_{1}=q_{1} p1?=q1?，
2. 2. 2.{ p 1 , . . . . , p r , q 1 , . . . , q t } \{p_{1},....,p_{r},q_{1},...,q_{t}\} {p1?,....,pr?,q1?,...,qt?}存在一个 a c c e s s i b l e accessible accessible的状态，
3. 3. 3. 存在 i ≤ r , j ≤ t i\leq r,j\leq t i≤r,j≤t使得 p i p_{i} pi?和 q j q_{j} qj?都是终态。
证明和定理3是类似的，只是这里的条件有所加强，因为 L ∞ L_{∞} L∞?要满足对任意长度的前缀都成立，因此终态必须要落在环上。另外特别的，当 i = j = 1 i=j=1 i=j=1的时候，就只有一个终态。
基本假设 注意到 u n ( q ) u_{n}(q) un?(q)是一个常系数线性递归方程的解，所以 u n ( q ) u_{n}(q) un?(q)存在一个通解，使得 u n ( q ) = ∑ i = 1 r P i ( n ) μ i n u_{n}(q)=\sum_{i=1}^{r}P_{i}(n)\mu_{i}^{n} un?(q)=∑i=1r?Pi?(n)μin?。其中 P i P_{i} Pi?是一个多项式，而 μ i \mu_{i} μi?是一个复数。
这里先预先给出了一些假设。
假设 μ 1 \mu_{1} μ1?是一个实数并且满足 μ 1 > m a x i = 2... r { ∣ μ i ∣ , 1 } \mu_{1}>max_{i=2...r}\{|\mu_{i}|,1\} μ1?>maxi=2...r?{∣μi?∣,1}，并且定义多项式 P 1 P_{1} P1?的度数是 d d d。那么显然对于 u n ( q ) u_{n}(q) un?(q)，极限 lim ? n → ∞ u n ( q ) n d μ 1 n \lim_{n\rightarrow∞}\frac{u_{n}(q)}{n^d\mu_{1}^{n}} limn→∞?ndμ1n?un?(q)?存在。
（ 同时也观察到如果 m a x i = 1... r ∣ μ i ∣ max_{i=1...r}|\mu_{i}| maxi=1...r?∣μi?∣是小于 1 1 1的话，那么 u n ( q ) u_{n}(q) un?(q)是趋于 0 0 0的，对于足够大的 n n n， u n ( q ) = 0 u_{n}(q)=0 un?(q)=0，但此时 lim ? n → ∞ u n ( q ) n d μ 1 n \lim_{n\rightarrow∞}\frac{u_{n}(q)}{n^d\mu_{1}^n} limn→∞?ndμ1n?un?(q)?，一个典型的反例就是如果存在 j > 1 j>1 j>1，使得 ∣ μ 1 ∣ = . . . . = ∣ μ j ∣ > m a x i = j + 1 , . . . , r ∣ μ i ∣ |\mu_{1}|=....=|\mu_{j}|>max_{i=j+1,...,r}|\mu_{i}| ∣μ1?∣=....=∣μj?∣>maxi=j+1,...,r?∣μi?∣，有可能会出现振荡间断而不存在极限。）
假设：集合 L ∞ \mathscr L_{∞} L∞?对于所有状态 q q q都是不可数的，当且满足以下的条件之一：
(1)： ? N q ∈ N : ? n > N q ， u n ( q ) = 0 \exist N_{q} \in \mathbb N:\forall n > N_{q}，u_{n}(q)=0 ?Nq?∈N:?n>Nq?，un?(q)=0
(2)： ? θ q ≥ 1 , P q ( x ) ∈ R [ x ] , b q > 0 : lim ? n → ∞ u n ( q ) P q ( n ) θ q n = b q \exist \theta_{q}\geq 1,P_{q}(x)\in \mathbb R[x],b_{q}>0:\lim_{n\rightarrow∞}\frac{u_{n}(q)}{P_{q}(n)\theta_{q}^{n}}=b_{q} ?θq?≥1,Pq?(x)∈R[x],bq?>0:limn→∞?Pq?(n)θqn?un?(q)?=bq?
记号：由于讨论的是 L ∞ \mathscr L_{∞} L∞?，对于 q = s q=s q=s的情形，必定不会出现 ( 1 ) (1) (1)这种情形，这里用 θ , P , a s \theta,P,a_{s} θ,P,as?分别指代 θ , P s , b s \theta,P_{s},b_{s} θ,Ps?,bs?。
结论1：对于 ( 2 ) (2) (2)中的每个状态 q q q，要么 θ q < θ \theta_{q}<\theta θq?<θ或者 θ q = θ 并 且 d ( P q ) ≤ d ( P ) \theta_{q}=\theta并且d(P_{q})\leq d(P) θq?=θ并且d(Pq?)≤d(P)。简单地说，就是 u q ( n ) u_{q}(n) uq?(n)一定会被 u s ( n ) u_{s}(n) us?(n)所限制。
证明：假设存在 θ q > 1 并 且 P q ( x ) ∈ R [ x ] \theta_{q}>1并且P_{q}(x)\in \mathbb R[x] θq?>1并且Pq?(x)∈R[x]使得 lim ? n → ∞ u n ( q ) P q ( n ) θ q n = b q \lim_{n\rightarrow∞}\frac{u_{n}(q)}{P_{q}(n)\theta_{q}^{n}}=b_{q} limn→∞?Pq?(n)θqn?un?(q)?=bq?，并且 P q ( n ) θ q n P ( n ) θ n \frac{P_{q}(n)\theta_{q}^{n}}{P(n)\theta^{n}} P(n)θnPq?(n)θqn??是不收敛的。
因为存在常数 i i i使得 u n ( s ) > u n ? i ( q ) u_{n}(s)>u_{n-i}(q) un?(s)>un?i?(q)。
所以 u n ( s ) P q ( n ) θ q n ≥ u n ? i ( q ) P q ( n ? i ) θ q n ? i 1 θ q i P q ( n ? i ) P q ( n ) → b q θ q i > 0 \frac{u_{n}(s)}{P_{q}(n)\theta_{q}^{n}}\geq\frac{u_{n-i}(q)}{P_{q}(n-i)\theta_{q}^{n-i}} \frac{1}{\theta_{q}^{i}}\frac{P_{q}(n-i)}{P_{q}(n)}\rightarrow \frac{b_{q}}{\theta_{q}^{i}}>0 Pq?(n)θqn?un?(s)?≥Pq?(n?i)θqn?i?un?i?(q)?θqi?1?Pq?(n)Pq?(n?i)?→θqi?bq??>0
然而 u n ( s ) P q ( n ) θ q n = u n ( s ) P ( n ) θ n P ( n ) θ n P q ( n ) θ q n \frac{u_{n}(s)}{P_{q}(n)\theta_{q}^{n}}=\frac{u_{n}(s)}{P(n)\theta^{n}}\frac{P(n)\theta^{n}}{P_{q}(n)\theta_{q}^{n}} Pq?(n)θqn?un?(s)?=P(n)θnun?(s)?Pq?(n)θqn?P(n)θn?是趋于 0 0 0的
这两者是矛盾的，因此假设不成立。
结论2：对于每个 q q q极限 lim ? n → ∞ u n ( q ) P ( n ) θ n \lim_{n\rightarrow∞}\frac{u_{n}(q)}{P(n)\theta^{n}} limn→∞?P(n)θnun?(q)?都是存在的，并且把这个极限记为 a q a_{q} aq?。
实际上， u n ( q ) P ( n ) θ n = u n ( q ) P q ( n ) θ q n P q ( n ) θ q n P ( n ) θ n \frac{u_{n}(q)}{P(n)\theta^{n}}=\frac{u_{n}(q)}{P_{q}(n)\theta_{q}^{n}}\frac{P_{q}(n)\theta_{q}^{n}}{P(n)\theta^{n}} P(n)θnun?(q)?=Pq?(n)θqn?un?(q)?P(n)θnPq?(n)θqn??
前面一部分就是 b q b_{q} bq?，后面一部分由上面证明要么就是分子低阶，极限就是 0 0 0，要么就是同阶， a q a_{q} aq?就是 b q b_{q} bq?乘上一个常数，这里不多赘述。
一些极限 根据前文， lim ? n → ∞ v a l S ( w n ) v ∣ w n ∣ = lim ? n → ∞ ∑ i = 0 n β q , n ? i ( w ) u i ( q ) v n ( s ) \lim_{n\rightarrow∞}\frac{val_{S}(w_{n})}{v_{|w_{n}|}}=\lim_{n\rightarrow ∞}\frac{\sum_{i=0}^{n}\beta_{q,n-i}(w)u_{i}(q)}{v_{n}(s)} limn→∞?v∣wn?∣?valS?(wn?)?=limn→∞?vn?(s)∑i=0n?βq,n?i?(w)ui?(q)?
定理5：如果 q q q是 M l M_{l} Ml?的一个状态且有 a q > 0 a_{q}>0 aq?>0，那么有：
(1)： ∑ i = 0 n u i ( q ) ∑ i = 0 n u i ( s ) = a q a s \frac{\sum_{i=0}^{n}u_{i}(q)}{\sum_{i=0}^{n}u_{i}(s)}=\frac{a_{q}}{a_{s}} ∑i=0n?ui?(s)∑i=0n?ui?(q)?=as?aq??
(2)： u n ( q ) ∑ i = 0 n u i ( q ) = θ ? 1 θ \frac{u_{n}(q)}{\sum_{i=0}^{n}u_{i}(q)}=\frac{\theta-1}{\theta} ∑i=0n?ui?(q)un?(q)?=θθ?1?
(3)： lim ? n → ∞ ∑ i = 0 n β q , n ? i u i ( q ) u n ( q ) = ∑ j = 0 ∞ β q , j θ ? j \lim_{n\rightarrow∞}\frac{\sum_{i=0}^{n}\beta_{q,n-i}u_{i}(q)}{u_{n}(q)}=\sum_{j=0}^{∞}\beta_{q,j}\theta^{-j} limn→∞?un?(q)∑i=0n?βq,n?i?ui?(q)?=∑j=0∞?βq,j?θ?j
证明：
第一步： a q > 0 a_{q}>0 aq?>0：
记 P P P的度为 r r r，有 P = α n r + Q ( n ) P=\alpha n^{r}+Q(n) P=αnr+Q(n)，显然 d ( Q ( n ) ) < r d(Q(n))
u n ( q ) α n r θ n ? u n ( q ) P ( n ) θ n = u n ( q ) Q ( n ) P ( n ) θ n α n r → 0 \frac{u_{n}(q)}{\alpha n^{r}\theta^{n}}-\frac{u_{n}(q)}{P(n)\theta^{n}}=\frac{u_{n}(q)Q(n)}{P(n)\theta^{n}\alpha n^{r}}\rightarrow0 αnrθnun?(q)??P(n)θnun?(q)?=P(n)θnαnrun?(q)Q(n)?→0
因为有 u n ( q ) P ( n ) θ n → a q \frac{u_{n}(q)}{P(n)\theta^{n}}\rightarrow a_{q} P(n)θnun?(q)?→aq?
改写为 lim ? n → ∞ u n ( q ) n r θ n = a q \lim_{n\rightarrow∞}\frac{u_{n}(q)}{n^{r}\theta^{n}}=a_{q} limn→∞?nrθnun?(q)?=aq?
对状态 p ∈ { q , s } p\in\{q,s\} p∈{q,s}，一定存在 ( α p , n ) (\alpha_{p,n}) (αp,n?)收敛到 1 1 1，满足 u n ( p ) = α p , n a p n r θ n u_{n}(p)=\alpha_{p,n}a_{p}n^{r}\theta^{n} un?(p)=αp,n?ap?nrθn。而且对于 k > 1 k>1 k>1，一定存在 K > 1 K>1 K>1使得，当 n > K n>K n>K一定有 α s , n , α q , n ∈ [ 1 ? 1 k , 1 + 1 k ] \alpha_{s,n},\alpha_{q,n}\in [1-\frac{1}{k},1+\frac{1}{k}] αs,n?,αq,n?∈[1?k1?,1+k1?]
( 1 ) , ( 2 ) (1),(2) (1),(2)易证。
现在证明 ( 3 ) (3) (3)：
令 z n = ∑ i = 0 n β q , n ? i u i ( q ) u n ( q ) z_{n}=\frac{\sum_{i=0}^{n}\beta_{q,n-i}u_{i}(q)}{u_{n}(q)} zn?=un?(q)∑i=0n?βq,n?i?ui?(q)?.
对于 ? > 0 \epsilon>0 ?>0，我们给出 z n z_{n} zn?的一个上界。
z n ≤ ∑ i = 0 K β q , n ? i u i ( q ) u n ( q ) + a q ∑ i = K + 1 n β q , n ? i α q , i i r θ i a q α q , n n r θ n z_{n}\leq\frac{\sum_{i=0}^{K}\beta_{q,n-i}u_{i}(q)}{u_{n}(q)}+\frac{a_{q}\sum_{i=K+1}^{n}\beta_{q,n-i}\alpha_{q,i}i^{r}\theta^{i}}{a_{q}\alpha_{q,n}n^{r}\theta^{n}} zn?≤un?(q)∑i=0K?βq,n?i?ui?(q)?+aq?αq,n?nrθnaq?∑i=K+1n?βq,n?i?αq,i?irθi?
≤ k + 1 k ? 1 ∑ i = K + 1 n β q , n ? i ( i n ) r θ i ? n + ∑ i = 0 K β q , n ? i u i ( q ) u n ( q ) \leq\frac{k+1}{k-1}\sum_{i=K+1}^{n}\beta_{q,n-i}(\frac{i}{n})^{r}\theta^{i-n}+\frac{\sum_{i=0}^{K}\beta_{q,n-i}u_{i}(q)}{u_{n}(q)} ≤k?1k+1?∑i=K+1n?βq,n?i?(ni?)rθi?n+un?(q)∑i=0K?βq,n?i?ui?(q)?
∑ i = K + 1 n β q , n ? i ( i n ) r θ i ? n = ∑ i = 0 n ? K ? 1 β q , i ( 1 ? i n ) r θ ? i = ∑ i = 0 n ? K ? 1 β q , i θ ? i + ∑ j = 1 r C r j n ? j ∑ i = 0 n ? K ? 1 β q , i ( ? i ) j θ ? i \sum_{i=K+1}^{n}\beta_{q,n-i}(\frac{i}{n})^{r}\theta^{i-n}=\sum_{i=0}^{n-K-1}\beta_{q,i}(1-\frac{i}{n})^{r}\theta^{-i}=\sum_{i=0}^{n-K-1}\beta_{q,i}\theta^{-i}+\sum_{j=1}^{r}C_{r}^{j}n^{-j}\sum_{i=0}^{n-K-1}\beta_{q,i}(-i)^{j}\theta^{-i} ∑i=K+1n?βq,n?i?(ni?)rθi?n=∑i=0n?K?1?βq,i?(1?ni?)rθ?i=∑i=0n?K?1?βq,i?θ?i+∑j=1r?Crj?n?j∑i=0n?K?1?βq,i?(?i)jθ?i。
对于第二项：我们注意到级数 ∑ i = 0 ∞ β q , i θ ? i \sum_{i=0}^{∞}\beta_{q,i}\theta^{-i} ∑i=0∞?βq,i?θ?i是连续可微并且可以逐项微分。
所以有 ( θ θ d θ ) j ∑ i = 0 ∞ β q , i θ ? i = ∑ i = 0 ∞ β q , i ( ? i ) j θ ? i (\theta\frac{\theta}{d\theta})^{j}\sum_{i=0}^{∞}\beta_{q,i}\theta^{-i}=\sum_{i=0}^{∞}\beta_{q,i}(-i)^{j}\theta^{-i} (θdθθ?)j∑i=0∞?βq,i?θ?i=∑i=0∞?βq,i?(?i)jθ?i，显然左边式子是收敛的。
可以发现小于等于号右边全部收敛。
对于 ? > 0 \epsilon>0 ?>0，我们给出 z n z_{n} zn?的一个下界。
z n ≥ ( 1 ? 2 k + 1 ) ∑ i = 0 n ? K ? 1 β q , i ( 1 ? i n ) r θ ? i ≥ ∑ i = 0 n β q , i θ ? i ? ∑ i = n ? k n β q , i θ ? i + ξ n ? 2 k + 1 ∑ i = 0 ∞ β q , i θ ? i ? 2 ξ n k + 1 z_{n}\geq(1-\frac{2}{k+1})\sum_{i=0}^{n-K-1}\beta_{q,i}(1-\frac{i}{n})^{r}\theta^{-i} \geq\sum_{i=0}^{n}\beta_{q,i}\theta^{-i}-\sum_{i=n-k}^{n}\beta_{q,i}\theta^{-i}+\xi_{n}-\frac{2}{k+1}\sum_{i=0}^{∞}\beta_{q,i}\theta^{-i}-\frac{2\xi_{n}}{k+1} zn?≥(1?k+12?)∑i=0n?K?1?βq,i?(1?ni?)rθ?i≥∑i=0n?βq,i?θ?i?∑i=n?kn?βq,i?θ?i+ξn??k+12?∑i=0∞?βq,i?θ?i?k+12ξn??，
同样也是收敛的，结论得到证明。
定理6： lim ? n → ∞ v n ? 1 ( s ) v n ( s ) = 1 θ \lim_{n\rightarrow∞}{\frac{v_{n-1}(s)}{v_{n}(s)}}=\frac{1}{\theta} limn→∞?vn?(s)vn?1?(s)?=θ1?
证明： v n ? 1 ( s ) v n ( s ) = 1 ? u n ( s ) v n ( s ) → 1 ? θ ? 1 θ \frac{v_{n-1}(s)}{v_{n}(s)}=1-\frac{u_{n}(s)}{v_{n}(s)}\rightarrow1-\frac{\theta-1}{\theta} vn?(s)vn?1?(s)?=1?vn?(s)un?(s)?→1?θθ?1?
定理7： lim ? n → ∞ v a l S ( w n ) v ∣ w n ∣ = θ ? 1 θ 2 ∑ q ∈ K a q a s ∑ j = 0 ∞ β q , j θ ? j \lim_{n\rightarrow∞}\frac{val_{S}(w_{n})}{v_{|w_{n}|}}=\frac{\theta-1}{\theta^2}\sum_{q\in K}\frac{a_{q}}{a_{s}}\sum_{j=0}^{∞}\beta_{q,j}\theta^{-j} limn→∞?v∣wn?∣?valS?(wn?)?=θ2θ?1?∑q∈K?as?aq??∑j=0∞?βq,j?θ?j
证明： ∑ q ∈ Q ∑ i = 0 ∣ w n ∣ ? 1 β q , ∣ w n ∣ ? i ? 1 u i ( q ) u ∣ w n ∣ ? 1 ( q ) u ∣ w n ∣ ? 1 ( q ) ∑ i = 0 ∣ w n ∣ ? 1 u i ( q ) ∑ i = 0 ∣ w n ∣ ? 1 u i ( q ) ∑ i = 0 ∣ w n ∣ ? 1 u i ( s ) ∑ i = 0 ∣ w n ∣ ? 1 u i ( s ) ∑ i = 0 ∣ w n ∣ u i ( s ) \sum_{q\in Q}\frac{\sum_{i=0}^{|w_{n}|-1}\beta_{q,|w_{n}|-i-1}u_{i}(q)}{u_{|w_{n}|-1}(q)}\frac{u_{|w_{n}|-1}(q)}{\sum_{i=0}^{|w_{n}|-1}u_{i}(q)}\frac{\sum_{i=0}^{|w_{n}|-1}u_{i}(q)}{\sum_{i=0}^{|w_{n}|-1}u_{i}(s)}\frac{\sum_{i=0}^{|w_{n}|-1}u_{i}(s)}{\sum_{i=0}^{|w_{n}|}u_{i}(s)} ∑q∈Q?u∣wn?∣?1?(q)∑i=0∣wn?∣?1?βq,∣wn?∣?i?1?ui?(q)?∑i=0∣wn?∣?1?ui?(q)u∣wn?∣?1?(q)?∑i=0∣wn?∣?1?ui?(s)∑i=0∣wn?∣?1?ui?(q)?∑i=0∣wn?∣?ui?(s)∑i=0∣wn?∣?1?ui?(s)?
应用定理5和定理6即可证明。
综上所述，证明了极限 lim ? n → ∞ v a l S ( w n ) v ∣ w n ∣ \lim_{n\rightarrow∞}\frac{val_{S}(w_{n})}{v_{|w_{n}|}} limn→∞?v∣wn?∣?valS?(wn?)?的存在性。
