应用_用回归图对符号动力学进行半系统的分类_论可测变换或动力系统与度量函数的耦合暨微扰论的拓展

以相关性(correlation)为度量的回归图忠实地反映了基础元胞自动机(ECA)的动力学性质,可以很好地区分稳态和混沌态。

我对Logistic Mapping做了简单的耦合推广,并应用回归图找到了处在混沌边界的参数,有趣的是这种推广系统也处在混沌边界。

demo_log_torus

logistic__3-811_corrprofile

讨论:二维元胞自动机是一个幻象,它并不比一维元胞高明到哪里去,对于Glider和Pattern的分类看起来没有发展壮大的希望。CA和物理学的联系目前还是太弱了,需要一些契机把CA爱好者引导到更有建设性的道路上。Wolfram对Rule110的阐释是很有insight的,但是他本人最后也认识到CA有一些内在的缺陷使其不能模拟神经网络。我希望Derrida Plot的复兴可以改变这一情况,这一工具允许人们更加系统地对自动机的动力学性质进行分类,而且和微扰论有很深的联系,希望有更多的人参与到这个研究里来。

这里用一个二维BS元胞自动机为例子(B013468/S23,生命游戏是B3/S23),大致介绍一下Covariance Profile的具体操作办法,用一个常值分布随机取两个初始状态,计算它们的距离H(0),接下来用CA规则将两个初态分别迭代T次,并记录它们的轨迹。这样我们可以得到H(1),H(2),H(3)….H(T). 然后把上述操作重复N次。想象[H(1),H(2)]在平面内确定一个点,由于有N个样本,我们可以确定N个点,这时候我们可以计算H(1),H(2)的统计学关系(一开始我用的是相关性(Pearson Correlation),后面发现不够灵敏,于是换成了协方差(Covariance)

expanded6491tca

对于任选的H(t_a),H(t_b),我们都可以确定一个分布并且抽象成一个单值。将这些单值集合起来之后,我们就的到了刚刚看到的热相图。

collected6491tca

(这里的单值用的都是协方差。)

我的观察是,热相图的凹凸性可以很好地刻画原系统的动力学性质。可以看到这个热相图的对角线有一个凹扩散,这一般对应复杂的动力学(complex,相对于混沌 chaotic,稳定 stable而言)

待续

记录_论可测变换或动力系统与度量函数的耦合_暨微扰论的拓展_1

2017/02/14 L,叁,F

首先F抛出关于H1,H2和Derrida Plot的问题,询问在使用图论时原集合一般会内嵌在哪些度量空间(metric space)。

L:抛出了对图论联通性和拓扑联通性之间的区别。L指出联通图可以自然导出一个最短路径(通过广度优先搜索),从而定义一个有离散拓扑的度量空间,但是图之联通不能导出最短路径对应的离散拓扑之联通。原因在于,由于这个拓扑是离散拓扑,所以这个拓扑对应的图显然不连通(只要图中的元素大于等于两个),而且由于道路/路径联通蕴含连通性,所以图也就不道路联通了。

叁:单单给出一个集合(Set)并不能唯一地确定一个度量空间。额外地,我们需要赋予这个集合某些结构,比如说把它们按某种方法排成一排,计算距离就行了,但单单给出一个集合是不能确定度量空间的。

L:总之,图论中最完全的信息,由边和顶点共同提供,可以人为地给图定义一些度量空间,但是这个度量在使用时要当心(叁:估计刘大师的意思是,图里的metric(比如由连接两点的最少的边的数量决定)并不是一个真正的metric space里的metric)。或者说是在套用metric space的结论时,要小心图论和拓扑空间之间术语的区别。

叁:虽然我没有完全听懂,不过问题应该出在三角不等式 ,而不是连通性上吧?因为就算是真正的度量空间里面的开球也不一定是联通的。

L:嗯其实是个metric,主要是连通性不一致可能会出错。譬如图论中的道路和拓扑空间就有点不一样。

F:让我重新表述一下我的问题:
假设一个有限集合S 有一个测度  \mu(S) ,(L:为严谨,S的 \sigma代数是S的power set, \mu: \sigma(S) \rightarrow [0,1],而且 \mu满足并集相加),那么给定一个转移矩阵(Transition matrix ,也就是带强度的Edge matrix),令为 \pi 。那令 \mu_2=\pi * \mu_1,则 \pi是一个可测变换(这里的乘法定义是矩阵乘法)。根据马尔可夫链基本定理(THE FUNDAMENTAL THEOREM OF MARKOV CHAINS),如果 \pi的性质足够好,那么 \pi重复作用之后测度 \mu的是驻定的,但驻定这个条件还并不是最重要的。
现在有趣的是,S本身有一个内构的度量是汉明距离: H(S_a,S_b),(附:两条长度为n的有x个字符是不同的序列之间的汉明距离 H=\frac{x}{n},当然除以n 不是必要的,只是一步正规化)。现在如果 \pi对应一个有向图(directed graph),也就是说每个元素只能有一个下家,且定义这条边强度为1,那么给出 a_2=\pi(a_1),  b_2=\pi(b_2),现在我们考察 H(a_1,b_1), H(a_2,b_2)之间的关系 (简称  H_1,H_2)。
联系微扰理论(perturbation theory),讨论同一个微分方程 \frac{dx}{dt} = f(x),从x0开始会给出一条轨迹x(t),从x0+e会给出另一条轨迹x’(t),通过考察 \frac{d(|x' - x|)}{dt} =g(|x' -x|)可以得出系统的复杂度/渐进稳定性(这里g可以从f和x0导出)。注意到我们使用了一个度量|x’-x|,在微分动力系统中这个度量常常是L2-norm,也就是欧几里得距离,也就是说,我们考察的是L2度量在微分动力系统下的行为,以理解该动力系统的混沌性。相应的,在前一个例子中,我们考察的是汉明度量在可测变换下的行为,理论上这可以体现出该可测变换的混沌性。但是需要注意的是,经典微扰理论关心的是|x’-x|极小时的行为,离散扰动理论却被迫关心H1和H2之间的统计联系,因为对H1取极小并不是一个极为自然的选择。

A partial derivation of the RK4 ODE-solver // RK4积分器的部分推导

RK4
is an ODE solver similar to euler’s method, with the iterator taking
the
form:

RK-family
method relies on finding k_n iteratively, in RK4 the iteration
reads

However,
these relations
are
only useful

to derive k2, not from k1 directly, but
proxyed through
a complicated y. We now seek to eliminate this proxy. We wonder what
happened to the coefficients of k1 to k4. Thus, we should
taylor-expand k1 to k4, exploiting the aforementioned preserved
relation. Note this expansion has a 2D form if partial derivative is
taken. However we can exploit the principle of total derivative to
simplify the notation.(This is essentially dropping the dependency of
“f” on “y” to achieve a simpler notation).

By
the principle of total derivative:

Take
derivative wrt t:

Exchange
LHS with RHS, time both
sides
by

gives:

substitue
( II ) into ( I ) gives:

Note

,in
other words:

Compare
(III) against well-known Taylor expansion of y( t+h ):

We
obtain

*According
to Wikipedia, the full expansion of  (III) looks like 

Giving
up to:


and
thus