数理解析研究所講究録
第 1799 巻 2012 年 130-136130

ランダムグラフ上の多種ランダムウォークの全訪問時間
山内 由紀子 \dag er
穂坂 祐輔 *
小野 廣隆 \d ag er
山下 雅史 \dag er
来嶋 秀治 \dag er*
九州大学システム情報科学府情報学専攻\dag er 九州大学システム情報科学研究院情報学部門\d ag er 九州大学経済学研究院
を 1 回以上訪問するまでの期待遷移数であり，これらに関して多くのことが知られている．標準ランダムウォ
概要 ランダムウォークはインターネットのような巨 クとは隣接する頂点に等確率で遷移していくランダム
大なネットワークの探索に有効な手段である．全訪問時 ウォ-クであり，Aleliunae ら [2] らにより，頂点数 , 辺間はグラフ上のランダムウォークの重要な指標の一つで 数 の任意の (単純) グラフにおいて到達時間と全訪問あり数多くの研究がされている．ネットワークの探索に 時間の期待値が $O(mn)$ で抑えられるということが知らおいて複数のクローラを使うほうが 1 台のクローラで探 れている．ロリポップグラフはこの上界のタイトな例に

概要

ー

$n$

$m$

索をするよりも速くネットワーク全体を探索できることは明らかである．Alon ら (2011) は 個のトークンを使$k$

う多重ランダムウォークが完全グラフやランダムグラフなどの特定のグラフにおいて 1 台のものよりも 倍速く$k$

全探索できることを示したが，同時にサイウルやパスななっており，標準ランダムウォークの到達時間，全訪問である．到達時間，全訪問時間を短縮するために，Ikeda ら [7] は ランダムウォークを提案
時間が共に$\Omega(n^{3})$$\beta$している． ランダムウォークの頂点 からの隣接頂点$u$$\beta$$v$への遷移確率は次のように定義されている．

どのグラフでは $\log k$ 倍にしか高速化できないことも示
してる．

本研究では

(1)

$p_{u,v}= \frac{\deg(v)^{-\beta}}{\Sigma_{v’\in N(u)}\deg(v’)^{-\beta}}$

個のトークンが独立に個々の遷移確率行
トークンの多種ランダムウォークを提案する．また単一トークンのランダムウォークにお$k$

列に従って遷移する$k$$\deg(u)$ は頂点 $u$
ここで $N(u)$ は頂点 $u$ の隣接頂点集合，の次数であり， は任意の実数である．また Ikeda らはラン$\beta=0.5$ のときにける Matthews の不等式のように，多種ランダムウオー 任意の (単純) グラフにおいて，$O(n^{2})$ , 全訪問時間
クにおいて全訪問時間の上下界を到達時間から与える不 ダムウォークの到達時間の期待値が$\beta$$\beta$$O(n^{2}\log n)$ になることを示している．
等式を導く．さらに導出した上下界の式が，完全グラフ の期待値が一方でネットワークの探索を高速化させる別の手段とや完全二部グラフ，さらにはランダムグラフにおいてタ
して複数のクローラで探索を並列化することが考えられイトになることを示す．
る．Alon ら [3] は標準ランダムウォークをする 個の独立なトークン (だたし同期して遷移) からなる多重ランダ
ムウォークについて研究している．多重ランダムウォ1 はじめに
クでは到達時間を，特定の頂点に 1 つ以上のトークンがランダムウォークはネットワーク探索の強力で実用的 到達するまでの時間としており，全訪問時間を，全てのな手法の一つであり，局所的な情報のみから探索を実行 頂点が 1 つ以上のトークンに訪問されるまでの時間としできネットワーク全体の情報を必要としないため，特に ている．Alon らは 個のトークンによる多重ランダム
インターネットのような巨大なネットワークに対して効 ウオークが，完全グラフやランダムグラフなどの特定の果的である．有限グラフ上のランダムウォークの指標に グラフにおいて単一 (トークンの) ランダムウォークよ
$k$

$k$

到達時間と全訪問時間がある．前者はトークンが任意のり$k$

倍速く全訪問できることを示している．また同時に頂点に到達するまでの期待遷移数で，後者は全ての頂点 サイクルやパスのようなグラフに対しては $\log k$ 倍の高131

表 1: 2 つのランダムウォークに従うトークンからなる多重/多種ランダムウォークの全訪問時閲$\beta$

図 1: シミュレーションを行ったグラフいて議論する．単一ランダムウォークにおいては全

訪問時間の上下界を到達時間によって与える不等式が速化しかできないことも示している．Matthews [9] により知られており，21 節で詳しく述べ

本研究では多種ランダムウォークという，各トークンる．本稿では多種ランダムウォークにおける全訪問時間
が個別の遷移確率行列を持っ新たなランダムウォークのの上下界を到達時間で抑える不等式を示す．またその上モデルを提案し，その全訪問時間について考える．多種下界が完全グラフ，完全二部グラフ，ランダムグラフな
ランダムウォークとは，多重ランダムウォークを一般化どのグラフにおいてタイトであることを示す．
したものであり，各ト-クンンに異なる遷移確率行列を採用することで，同一の遷移確率行列の場合より高速に

ネットワークを探索させることを目指している．2

準備

多種ランダムウォークが多重ランダムウォークよりも21
高速に探索し得ることを端的に示すため計算機によるシ単一ランダムウォーク

ミュレーションの結果を紹介する．このシミュレーショ本稿では 1 つのトークンによるランダムウォークを単ンでは，異なる遷移確率行列で遷移する 2 トークンが全 一ランダムウォークと呼ぶ． 頂点のグラフ $G=(V,E)$$n$

頂点を訪問するまでのステップ数 (多種ランダムウォー が与えられ， 上の単一ランダムウォークの遷移確率行
クの全訪問時間に相当) を計測している．各トークンは 列を $P=(p_{uv})$ : $u,v\in V$ とする．ここで $\{u,v\}\in E$ の$G$それぞれ $\beta=05$ と $\beta=1.0$ の$\beta$

ランダムウォーク

(式 (1)) の遷移確率行列に従う．また比較対象として 2つのトークンが共に$\beta\approx 0.5$

, 共に $\beta=1$ , 共に $\beta=0$の遷移確率に従う 2 トークンが全頂点を訪問するまでのステップ数 (いずれも $\beta=0.5,$ $\beta=1,$ $\beta=0$ の多重

ランダムウォークの全訪問時間に相当) を計測した．シミュレーションを行うグラフは頂点数 のクリークと，ときに限り $p_{uv>0}$ とする．
$Definiti_{on}2.1$. 遷移確率行列に従うトークンが頂点 を出発して に到達するまでのステップ数の期待値を， から への到達時間と呼び $H_{G}^{P}(u,v)$ と記述を次のように定義する．また $G$ に対する到達時間
$u$

$P$

$v$

$u$

$v$

$H_{G}^{P}$

する．

$c$

頂点数 $n-c(c\geq n/2)$ のサイクノレからなり，クリークの$H_{G}^{P}= \max H_{G}^{P}(u,v)$

各頂点からサイクルの頂点への辺をちょうど 1 本もっ．
図 1 は $n=12,$ $c=8$ としたときのシミュレーション$u,v\in V$.

(2)

22. 遷移確率行列 $P$ に従うトークンが頂を出発して他の全- ての頂点に到達するまでのステッ$D\otimes Rnition$のグラフの例である．表 1 は多重/多種ランダムウォー 点$u$

クの全訪問時間のシミュレーション結果であり，頂点数 プ数の期待値を， からの全訪問時間と呼び$u$1, 000 のグラフにおいて 10, 000 回試行を行った平均値 記述する．またら [7] の研究によれば，$\beta=0.5$ のである．
ラに定義する．
ンダムウォークは $\beta=1.0$ の場合よりも高速なランダム$G$に対する全訪問時間$C_{G}^{P}$$C_{G}^{P}(u)$

と

を次のよう

$\ddagger keda$$\beta$ウォークであるが，シミュレーションでは $c=666,750$ ,そして 800 のグラフにおいて，多種ランダムウォークのほうが高速であった．

本研究では多種ランダムウォークの全訪問時間につ$C_{G}^{p_{=\max_{u\in V}}}C_{G}^{P}(u)$.

(3)

Matthews [9] により，到達時閲と全訪問時間について以下のような関係式が知られている．

132$h_{n-1} \min_{u\neq v\in V}H_{G}^{P}(u,v)\leq C_{G}^{P}\leq h_{n-1}\max_{u\neq v\in V}H_{G}^{P}(u,v)$(4)個の頂点の順序集述できる．マルコフ過程の各状態はをマルコフ過程の状態の有合で定義し，$k$$\Omega=(V^{k})^{N\cup\{0\}}$

妬は調和級数で，ここで$h_{n}= \sum_{\dot{l}=1}^{n\underline{1}}.\cdot$

である．限順序列の全集合とする．また
を

2.2
$k$

$M(\Omega)$$\Omega$

上のマルコフ測度空間とする．

$S=(s_{1},s_{2}, \ldots, s_{k}),$ $S=(s_{1}’, s_{2}’, \ldots,s_{k}’)$$Sarrow S’$ の状態
をこのマルコフ過程の状態対とすると，

多種ランダムウォーク

遷移確率 $p(S, S’)$ は次のように定義される．

トークンの多種ランダムウォークでは，それぞれ$k$のトークンが個々の遷移確率に従って独立に遷移する．
頂点のグラフ $G=(V, E)$ が与えられ， 上の多種

$p(S, S’)= \prod_{\dot{l}=1}P:$( $8:,$ S\’i).

$G$

$n$

ランダムウォークの各トークンの遷移確率行列を $P_{l}=$$\omega i(u,v))$: $u,v\in V,$ $1\leq i\leq k$とする．また多種ランダ

ムウォークの現在の状態を $S=$ $(s_{1},s_{2}, ..., s_{k})\in V^{k}$ とし，各トークンの滞在している頂点は $s_{*}\in V$ で表わされるとする．このとき各ト列$=$

ここで $p_{i}(u,v)$ は多種ランダムウォークにおけるを初期状態 $So\in V^{k}$ を持つマルコフ測度としたときとする，つまり$\mu\in M(\Omega)$$\omega=(\omega_{0},\omega_{1}, \ldots)\in\Omega$

クンはそれぞれの遷移確率行$\mu(X_{0}(\omega)=S_{0})=1$の状態を $S’=(s_{1}’, s_{2}’, \ldots, s_{k}’)\in V^{k}$クンは同期して遷移する．

多種ランダムウォークの到達時間を以下のように定義番目のトークンの $uarrow v$ への遷移確率である．

に従って遷-移し，多種ランダムウォークの次とする．つまりトー が成立する．ここで$p_{i}(S:,S_{1}’\cdot)$

$i$

また任意の

$S\in V^{k}$,

番目の要素を表す．
について以下が成立する．
$X_{t}(\omega)$は$\omega$

の

$t$

.
する．
Definition 2.3.
$\sum_{S\in(V^{k})}p(S,S’)=1$$;=$
遷移確率行列集合に従う多種ランダムウォークが状$P^{k}$$(P_{1},P_{2}, \ldots,P_{k})$態 $S=$$(s_{1}, s_{2}, ..., s_{k})$から遷移を開始して，頂点$v$

また任意の $S,$ $S’,$$U_{l}\in V^{k}$$U_{0},$ $U_{1},$$\ldots,$と $t\in N\cup\{0\}$ にについて以下が成立する．

少なくとも 1 つのトークンが到達するまでの同期ス

テップ数の期待値を，状態$H_{G}^{P^{k}}(S,v)$$S$と記述する．また

から
$G$

$v$

の到達時間と呼びに対する到達時間を次のように定義する．

$H_{G}^{P^{k}}=$$mx$$H_{G}^{P^{k}}(S,v)$.

(5)$(P_{1},P_{2}, \ldots,P_{k})$$\mu(X_{i+1}(\omega)=S’|X_{i}(\omega)=U_{*}\cdot=S)=p(S, S’)$

ついて以下が成立する．

$;=$
2.4. 遷移確率行列集合に従う多種ランダムウォークが状$P^{k}$の頂点を少なくとも 1 つのトークンが訪問するまでのからの全訪問時間$G$ に対する全訪問時と呼びと記述する．また同期ステップ数の期待値を，状態$\mu(Y_{j}(X_{i+1}(\omega))=v|Y_{j}(X_{0}(\omega))=w_{0}$,$Y_{j}(X_{1}(\omega))=w_{1},$ $\ldots,Y_{j}(X_{l}(\omega))=w_{i}=u)$$=$$\mu(Y_{j}(X_{i+1}(\omega))=v|Y_{j}(X_{1}(\omega))=u)=pj(u, v)$,$S$$C_{G}^{P^{k}}(S)$$C_{G}^{P^{k}}$,さらに任意の $u,v,w0,w_{1},$ $\ldots,w_{i}\in V$ と $t\in N\cup\{0\}$ に

態 $S=(s_{1}, s_{2}, \ldots, s_{k})$ から遷移を開始して，他のすべて

間,$X_{1}(\omega)=U_{1},$ $\ldots,X_{*}\cdot(\omega)=U_{\dot{*}}=S)$$=$$S\in V^{k},v\in V$

Definition$\mu(X_{1+1}(\omega)=S’|X_{0}(\omega)=U_{0}$$H_{G}^{P^{k}}$ここで $Y_{j}(S)$ は $S\in V^{k}$ の $i$ 番目の要素を表す．そしてを次のように定義する．任意の$1\leq j\leq k$

測度は以下の$C_{G}^{P^{k}}=_{s} \max_{\in V^{k}}C_{G}^{P^{k}}(S)$.

(6)$N(u)$ を $u\in V$$G=(V,E)$ を $n$ 頂点の有限グラフとし，の隣接頂点集合とする． の次数は $d_{\mathfrak{X}}(u)=|N(u)|$ で$u$

表わす．多種ランダムウォークはマルコフ過程として記に対して上記の条件を満たすマルコフ$M^{+}$

により示される．

$M^{+}(\Omega)=\{\mu\in M^{+}(\Omega)|p(S,T)>0$

only if$\forall j$,Yj $(T)\in N(Y_{j}(S))\}$ .

133
3

多種ランダムウォークの全訪問時間の上下界が成立する．ただし,$T_{j-1}(\omega,\pi)<\tau(\omega,v_{j})\neq\acute{T}_{j-1}(\omega’,\pi)<\cdot\acute{r}(\omega’,v_{j})$Theorem $.1. $G=(V,E)$ を連結グラフとし，$P_{i}$であることに注意しなければならない．なぜなら多種ラ
1 ステップで複数の未到達の頂点に$(i=1,\ldots,k)$ を $G$ 上の任意の遷移確率行列として，ンダムウォークではとすると以下が成り立つ．訪問し得るため，以下の事象が成立する可能性があるた$P^{k}:=(P_{1},P_{2},\ldots,P_{k})$$h_{n-1}s\epsilon^{m_{k,}}v_{v}^{in(H_{G}^{P^{k}}(S,v)-1)\leq C_{G}^{P^{k}}}\epsilon\nu$(7)$\leq h_{n-1}sm_{k}a,x(H_{G}^{P^{k}}(S,v))$

(8)

めである．
$(T_{j-1}(\omega,\pi)=\tau(\omega,v_{j}))\wedge(T_{j-1}’(\omega^{r},\pi)<\tau^{J}(\omega’,v_{j}))$.

ゆえに，
ここで $h_{n}= \sum_{i=1}^{n}i^{-1}$ である．
$P_{u}(T_{j-1}(\omega,\pi)<T_{j}(\omega,\pi))$.

$p_{roo}g$

を

$\nu$

$V$

の順列の全集合をとする． の順列$V$

目の要素をっ$S_{V}$とし， 上の一様測度$S_{V}$$\pi=(v_{1},v_{2}, \ldots,v_{n})\in S_{V}$のとする．頂点 $u\in V$ と だけからなる順序集合 $U_{0}=(u,u,\ldots,u)\in V^{k}$ について， の$(\pi$$)=v_{j}$$\{\pi:\sigma_{1}(\pi)=u\}$$\mu$$=P_{u}(\gamma’(\omega’\sigma_{i}(\pi))<\tau’(\omega’,\sigma_{j}(\pi)),2\leq i<j)$

$u$

$\nu$

様に

$\leq P_{u}’(\tau_{j-1(\omega^{J},\pi)<\tau’(\omega’,v_{j})}’$番$i$を満たす条件付き測度を$\nu_{u}$,$= \int_{\omega}\nu_{u}(\{\pi:\tau^{J}(\omega’,\sigma_{i}(\pi))<\tau’(’\omega,\sigma_{j}(\pi))$とする．同$2\leq i<j\})d(\omega^{t})$の $\{\omega;Xo(\omega)=(u,u,\ldots,u)=U_{0}\}$ を満たす条件付き測度を$\mu_{u}$とする．一方で合とし，写豫$f$とする．また$\acute{\Omega}=V^{NU\{0\}}$をの直積測度を
を頂点の有限順序列の全集$\mu_{u}$と$= \int_{\omega}’\frac{(n-1)!}{(j-1)!(n-j)!}\cross\frac{(j-2)!(n-j)!}{(n-1)!}d\mu_{u}’(\omega’)$$P_{u}$$t\ovalbox{\tt\small REJECT}_{u}$1$=\overline{j-1}$

について$\omega=(\omega_{0},\omega_{1},\ldots)\in\Omega$$f(\omega)=\acute{\omega}=Y_{1}(X_{0}),Y_{2}(X_{0}),\ldots,Y_{k}(X_{0}),Y_{1}(X_{1})$$Y_{2}(X_{1}),\ldots.,Y_{k}(X_{1}),Y_{1}(X_{2}),\ldots$,,

で，すべての頂点を訪問するまでのステッ

任意の$\pi\in S\gamma$

プ数は$\tau_{n}(\omega,\pi)$なので)$C_{G}^{P^{k}}=E_{P_{V}}[T_{n}(\omega,\pi)]$つまり$X_{ki+j}(\omega^{J})=Y_{j}(X_{i}(\omega))$$= \sum_{j=2}^{n}E_{P_{t}}[T_{j}(\omega,\pi)-T_{j-1}(\omega,\pi)]$を満たす$\Omegaarrow\acute{\Omega}$とし， と$\acute{\mu}_{u}$$\tau^{J}(v),$するの全単射とする．さらに

if $0\leq i\leq k-1\}$ を満たす

$X_{i}=u$$\nu_{v}$の直積測度を$T_{j}(\omega,\pi)$’乃$(\omega’, 7f)$$\acute{P}_{u}$を$\{\omega’$:の条件付き測度$\acute{\omega}$とする．そして$\tau(\omega,v)$,$= \sum E_{P_{*}}n[T_{j}(\omega,r_{1})-T_{j-1}(\omega,\pi)$

:

$j=2$

をそれぞれ次のように定義$T_{j-1}(\omega,\pi)\neq T_{j}(\omega,\pi)]$$.$$\tau(\omega,v)=id\{t\geq 0:v\in X_{t}(\omega)\}$,$\tau’(\omega’,v)=inf\{\acute{t}\geq 0 :,v=X_{t}(\mathscr{O})\}$$\tau_{j}(\omega,\pi)=\max_{i\leq j}\tau(\omega,\sigma_{\dot{a}}(\pi))$$= \sum_{j=2}^{n}H_{G}^{P^{k}}(x_{r_{j-t(v,\pi)(\omega),v_{j})}}.\cdot$$P_{u}(T_{j-1}(\omega,\pi)\neq T_{\dot{g}}(\omega,7())$,$\leq\max\{H_{G}^{P^{k}}(S,v):v\in V,S\in V^{k}\}$$\acute{\tau}_{j}(\omega_{)}’n)=\max_{i\leq j}\acute{r}(\omega’,\sigma_{i}(\pi))$.

.
$\sum_{j=2}^{n}P_{u}(T_{j-1}(\omega,\pi)<T_{j}(\omega.\pi))$

ここで $x_{t}(\omega’)\in V$ は$\acute{\omega}$の$t$

番冒の要素である．このとき$T_{j-1}(\omega_{i}\pi)<T_{j}(\omega,\pi)\Leftrightarrow T_{j-1}(\omega,\pi)<\tau(\omega,v_{j})$である．さらに$T_{j-1}(\omega,\pi)<\tau(\omega,v_{j})\Rightarrow\acute{T}_{j-1}(\omega^{r},\pi)<\tau^{J}(\omega’,v_{j})$,$\leq m8x\{H_{G}^{P^{k}}(S,v):v\in V,S\in V^{k}\}\sum_{j=2}^{n}\frac{1}{j-1}$$\leq h_{n-1}\max\{H_{G}^{P^{k}}(S,v) :v\in V,S\in V^{k}\}$よって不等式 (7) の右辺が示された．

.

134
不等式 (7) の左辺を示すため以下を利用する．
$\tau(\omega,v)=r\frac{\tau’(\omega^{J},v)}{k}\rceil$$\geq$,$\frac{h_{\mathfrak{n}-1}}{k}\iota,\dot{m}vn\{Ep_{u}[’’$$\tau^{l}(\mathscr{O}, s)<\tau^{l}(\mathscr{O},v)]\}$$\geq h_{n_{*,v}}-1m_{\in}in_{V}\{E_{P_{u}}[\frac{\tau\prime(\omega\prime,v)}{k}-\frac{\tau’(\omega’,s)}{k}$$\tau_{j}(\omega,\pi)=r\frac{\Phi_{j}(\omega’,\pi)}{k}\rceil$.

$\neq(\omega^{l},s)<\tau’(\omega’,v)]\}$

また定義より以下も成立する．
$\acute{\tau}_{j-1(\mathscr{O},\pi)\neq _{j}(\omega’,\pi)}$$\geq h_{n_{s,v}}-1m_{\epsilon}in_{V}\{E_{P_{u}}[\frac{\tau’(\mathscr{O},v)}{k}-r\frac{\tau^{J}(\omega’,s)}{k}\rceil$:

子 $(\mathscr{O}, s)<\tau’(\omega’,v)]\}$$\Leftrightarrow\acute{T}_{j-1}(\omega^{J},\pi)<T_{j}’(\omega’,\pi)$$\Leftrightarrow\acute{T}_{j-1}(\omega’,\pi)<\neq(\omega^{l},v_{j})$:.

$\geq h_{\mathfrak{n}_{t}}-1\dot{m}_{v\in}n_{V}\{E_{P_{u}}[\lceil\frac{\tau’(\omega\prime,v)}{k}\rceil-\lceil\frac{\prime\prime(\mathscr{O},s)}{k}\rceil-1$

よって，

;

$\ovalbox{\tt\small REJECT}(\omega’, s)<\tau’(\omega’,v)]\}$$=h_{n-1} \min\{E_{P_{u}}s,v\in V[\tau(\omega,v)-\tau(\omega,s)]-1\}$$\geq h_{\mathfrak{n}-1}\min\{H_{G}^{P^{k}}(S,v)-1\}v\in V,S\in V^{k}$,

不等式 (7) の左辺も示された．
口

最後にもう一つ別の下界を示す．これは全訪問時間の定義より自明に成立する．
$Prop_{oS}ition3.1$$(i=1,\ldots,k)$ を $G$$(P_{1},P_{2},\ldots,P_{k})$. $G=(V,E)$ を連結グラフとし，:$P$上の任意の遷移確率行列として，$P^{k};=$とすと以下が成り立つ．

$\max$$H_{G}^{P^{k}}(S,v)\leq C_{G}^{P^{k}}$.

(9)$S\in V^{k},v\in V$

上下界のタイトな例
この節では定理 31 の多重標準ランダムウォークによるタイトな例を示す．

4.1

完全グラフ

$K_{n}$

また任意の開始状態 $S\in V^{k}$ と任意の目的頂点 $v\in V(v\not\in$$Ep_{u}[\tau(\omega,v)-\tau(\omega,s)$:$\tau(\omega,s)<\tau(\omega,v)]\geq\min_{k}H_{G}^{P^{k}}(S,S)S\in V$,, のについて，グラフの対称性より到達時間を次のように計算できる．

と合わせて，$H_{K_{n}}^{P^{k}}(S,v)= \frac{1}{1-(1-\frac{1}{n-1})^{k}}$(10)$C_{G}^{P^{k}}=E_{P}.[\tau_{n}(\omega,\pi)]$

トークン数$=E_{\oint_{u}}[ \lceil\frac{\Phi_{n}(\omega’,\pi)}{k}\rceil]$$k$について $k\leq n$ とすると，以下の不等式が得られる．
$1- \frac{k}{n-1}\leq(1-\frac{1}{n-1})^{k}\leq 1-\frac{k}{2(n-1)}$$\frac{E,_{u}[T_{n}’(\omega^{J},\pi)]}{k}$$\geq$

135
これを変形して，43$\frac{k}{2(n-1)}\leq 1-(1-\frac{1}{n-1})^{k}\leq\frac{k}{n-1}$.

ランダムグラフ$G_{n,p}$

単一ランダムウオークにおいて頂点 から開始したランダムウォークがステップ で を一度も訪問していない事象を $A_{s}(u,v)$ とすると，任意の $t>0$ について以下
$u$

$s$

よって

$v$

が成り立つ．

(11)$\frac{n-1}{k}\leq\frac{1}{1-(1-\frac{1}{n-1})^{k}}\leq\frac{2(n-1)}{k}$$H(u,v)= \sum_{s=1}^{\infty}Pr(A_{8}(u,v))\leq t+\sum_{s=t+1}^{\infty}Pr(A_{\theta}(u,v))$

式 (10) および (11) より

多重ランダムウォークにおいても各トー クンは独立に遷.

移することから以下が成り -つ．

$S \in V^{k},v\epsilon vS\in V^{k},v\in V\min H_{K_{n}}^{P^{k}}(S,v)=\max H_{K_{n}}^{P^{k}}(S,v)=\Theta(\frac{n}{k})$$\infty$さらに定理 31 より以下を得る．

$H(S,v)$$C_{K_{n}}^{P^{k}}=O( \frac{n}{k}\log n)$$\leq$$t+ \sum_{\epsilon=t+1}Pr(\bigcap_{u\in S}A_{s}(u,v))$,$=$$t+ \sum_{s=t+1}^{\infty}\prod_{u\epsilon s}Pr(A_{s}(u,v))$.

またこの上下界はタイトである．

の定常確率， を単一ランダムウォークの混合時間として以下の式を得る [4].
また42 完全二部グラフ$U,$ $W$$\pi_{v}$を$v$$t_{m}$$K_{m,n}$を完全一-部ク ラフ $K_{m,n}$ の a$Pr(A_{s}(u,v)|A_{s-1}(u,v))=1-\pi_{v}$ ,$*$$\lambda$

独立集合とし，$|U|=m,$ $|W|=n$ とする．また一般性を失わず，$m\leq n$

さらに標準ランダムウォークであれば，次数を用いて定と仮定できる．全てのトークンが同-の頂点から遷移 常確率が計算出来て，以下の式を得る．

を始めるので，$K_{m,n}$ で到達時間なるのは開始状態 $S$ が含まゎる頂的頂点が $v\in U$ のときである．同様 O 最大が最小に

$H_{K_{m.n}}^{P^{k}}(S,v)$

点，1 らなり，目$Wt_{\overline{\llcorner}}$

$F$

開始状態
$v\in W$$S$-

なるの ji,$\iota$$\ovalbox{\tt\small REJECT}$$\llcorner$

が $W$ に含まれる頂点からなり，目的頂点がのときである．よって$S\in,v\in VninH_{K_{m,n}}^{P^{k}}(S,v)$$=$$\deg(v)$$Pr(A_{\epsilon}(u,v)|A_{s-1}(u,v))=1-\overline{2|E|}$

また任意の$t<sl_{\llcorner}^{\wedge}$

ついて，以下が成り立つ．

$Pr(A_{s}(u,v))=Pr(A_{t}(u,v))\prod_{t’=t+1}^{s}Pr(A_{t},(u,v)|A_{trightarrow 1}(u,v))$,$\frac{2}{1-(1-\frac{1}{m})^{k}}-1$
また多重ランダムウォークのトー クン数を $k=|S|$ , とし$s\in \mathscr{W}_{1}^{H_{K_{\infty,n}}^{P^{k}}(S,v)}$$=$$\frac{2}{1-(1-\frac{1}{n})^{k}}$て，不等式 (11) を用いて，.

$H(S,v)$$\leq$$t_{m}+ \sum_{s>tu}r_{\epsilon}\iota_{s}(1-\frac{\deg(v)}{2|E|})^{\epsilon-t}$$=$$t_{m}+ \sum_{s>t}(1-\frac{\deg(v)}{2|E|})^{k(\epsilon-t)}$完全グラフ上の多重標準ランダムウォークと同様の解析
により
へ

.

$\min_{S\in V^{k},v\epsilon v}H_{K_{m,n}}^{P^{k}}(S,v)$$\geq$$\frac{2m-1}{k}$$s\epsilon^{\max_{v\in}H_{K_{m,n}}^{P^{k}}(S,v)}V^{k},V$$\leq$$\frac{4n}{k}$$(k<m)$$=$$(k<n)$ .

よって以下の不等式が得られる．
$\leq$$\frac{2m-1}{k}\log(m+n)\leq C_{K_{n.\mathfrak{n}}}^{P^{k}}\leq\frac{4n}{k}\log(m+n)$

この場含，定理 31- の上下界はになる．

.

$t_{m}+ \frac{1}{1-(1_{|B|^{1}}^{g\llcorner v}-\frac{de}{2})^{k}}$$t_{m}+ \frac{4|E|}{k\cdot\deg(v)}$

ここで $G(n,p)$ において $p$$\frac{n}{m}=\Theta(1)$のときタイトが十分大きく，高い確率でを満たすとすると， の混合時間が $O(\log n)$ である [11] ことと，辺数について$\min_{v\epsilon V}\deg(v)=\Theta(n)$$G_{n,p}$.

136$2|E|= \sum\deg(v)=\Theta(n^{2})$となることを合わせて以下のような到達時間の上界を得る．
$s_{\in V^{k}v\in V}^{m\epsilon,xH(S,v)} \leq\log n+O(\frac{n}{k})$,定理 31 を適応して以下を得る．
$C_{G}^{P^{k}}=O( \frac{n}{k}\log n)$$[4|$

C. Cooper and A. IFtieze: The cover time ofsparse random graphs, Random structures and Ab
gorthms, 30 (2007) 1-16.

[5] C. Cooper and A. Frieze: Random walks on random graphs. NANO-NET, Lecture Notes of the Institute for Computer Sciences, Social Infomatics
and Telecommunications Engineering, 3 (2009),

95-106.
-方 Alon ら [3] により密なランダムグラフ $G(n,p)$ 上のトークン多重標準ランダムウォークの全訪問時間$k$

は $e(\frac{n}{k}\log n)$ であることが知られいる．このことから

定理 31 の上界は密なランダムグラフ上の多重ランダムウォークにおいてタイトであることが分かる．

5

まとめ
本稿では多重ランダムウォークを一般化した多種ラン

ダムウォークを提案し，多種ランダムウォークの全訪問
時間の到達時間による上下界の式をいくつかのタイトな例とともに示した．しかしながら一般のグラフおいての高速な多種ランダムウォークを構成する遷移確率行列の組み合わせ方と，各遷移確率行列の設計方法，さらに出来上がった多種ランダムウォークが単一ランダムウオー

クと比べてどのくらい速いのかは到達時間，全訪問時間のどちらにおいても未解決で，挑戦的な課題である．

参考文献[1] D. J. Aldous: On the time taken by random walks
on finite groups to visit every state, Z. Wahrsh.
veiw. Gebiek 62(1983), 361-393.

[2] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovaasz, and C. Rackoff: Random walks, universal
traversal sequences, and the $\infty mplexity$ of mazeproblems, Proc.20th Ann. Symposium on Foundations of Computer Science 1979, 218-223.
[3] N. Alon, C. Avin, M. Koucky, G. Kozma, Z.
Lotker, and M. R. Tuttle: Many ranodm walks
are fSter than one, Combinatorics, Probability andComputing 20 (2011), 481-502.

[6] K. Efremenko and O. Raingold: How well \‘ao random walk parallehize, Lecture Notes in Computer
Science, 5687 (2009).
$476\triangleleft 89$[7] S. Ikeda, I. Kubo, and M. Yamashita: The hitting
and cover times of random walks on finite graphs
using local degree information, Theoretical Computer Science, 410 (2009), 94-100.
time of random walks
Probability
Combinatorics,,
on randomand Computing, 7 (1998), 265-279.

[8] J. Jonasson: On the$\infty ver$$\Psi^{aphs}$[9] P. Matthews: Covering problems for Markov
chain, The annals of probability, 16 (1988), 1215-

1228.
[10] Y. Nonaka, H. Ono, S. Kijima, and M. Yamashita:
How slow, or fast, are standard random walks?
analysis of hitting and cover times on tree, CR-–

PIT, 119 (2011),$6\triangleright 68$.

[11] A. Sinclair: Improved bounds for mixing rates ofMarkov chains and multicommodity flow, Lecture
Notes in Computer Science, 583 (1992), 474-487.