2017-08-26

CRT上の酔歩ラベル付けとそれが表すメトリック〜ブラウニアンマップ『私のためのBrownian map構成法』

ブラウニアンラベルでは、 $T_e$ 上に値を貼り付ける
ブラウン散歩 $e$ での時刻0での点に対応する $T_e$ の点 $\rho$ では、このラベルは0 ( $Z_\rho = 0$
そして、ラベル値Zは酔歩でランダムに決めるが、「どれくらい離れているときに、どれくらい遠くまで歩いているか」という意味合いで酔歩を決めるとき $E[(Z_a-Z_b)^2] = d_e(a,b)$ と書く。これは、 $T_e$ 上の２点 $a,b$ について、その間の「木的な距離 $d_e(a,b)$ 」を酔歩する時間とみなしたときに、到達する座標変化が $Z_a-Z_b$ の値になるように酔歩してZを決めよ、と言う意味である
具体的には、木 $T_e$ の節ごとに酔歩を定めて、それを分岐部でつなぐことで、 $\rho$ の座標を0としたときの各所の座標 $Z$ を定める、というもの
さて。 $T_e$ とその上の値ラベル $Z$ が与えられた
2点 $a,b \in T_e$ 間に、以下のような「擬距離」を定める
定めるにあたって２ステップを踏む
第１ステップ
- - 木をaからbへ周回するか、bからaへ周回することにするとして、その周回にあたっては、わざわざ遠回りせずに、行き先に近い方の木のサイドから出発し、到着したらそれでOK、ということにする
  - そのようにするとしたうえで、周回中に出会う、最小のZ値のうち、大きめの方を採用して、そこを基準水位として、2点のZ値から基準水位まで降りた高さの和を、2点間の $D^\circ(a,b)$ とする、というもの
  - $Z_a=Z_b$ であって、その周回路に $Z_a=Z_b$ より小さい値がなければ $D^\circ (a,b)=0$ である、ということであり、そのような関係の2点は「同一視」する、ということ
第２ステップ
- 上記のように定めた $D^\circ(a,b)$ を用いて、「本当の2点間の擬距離 $D^*(a,b)$ を次のように定める
- 定義式には複数の書き方がある
  - 一つ目は木上の点ではなく、それに対応するブラウン散歩の時刻を使って与えるものである(複数の時刻が同一の木上の点に対応することに注意)
    - $D^*(s,t) = \inf \{\sum_{i=1}^k D^\circ (s_i,t_i); k \ge 1, s=s1,t=t_k,d_e(t_i,s_{i+1})\}$
    - 木上の点 a,bについて、対応するブラウン散歩時刻を適当に取り(複数とれるとしても、同じaに対応する2時刻 $s1,s2$ については $d_e(s1,s2)=0$ なる関係にあるので、上の式条件で「バイパスして距離を通算できる」ので問題ない
  - - ここでは、木上の始点と終点とは固定されているが、その途中で何個の点を介してもよく(kの値は何でもよい)、その上で、ひたすら、下限をもたらす木上の点列を探索せよ、と言っている
- 後掲のRmdの中では、「バイパスしてよい2点間」の距離を0にした上で、通ってよい点すべてをノードとする完全グラフの、グラフ上最短経路を計算することで、 $D^*$ を計算している