XII-th stone: 時間がない？

よく、「忙しくて、時間がないんだよねー」という言葉を耳にする。これは本当だろうか？誰も時間の流れをとめることも変えることもできないはずである。誰にでも時間は同じように与えられているのだ。しかしこの言葉をよく耳にする。

この言葉、どういうときに使われるかによってもちょっと意味が違ってきそうだ。たとえば締め切り間近の作業なり仕事をしていて「どうやっても間に合わない、時間が足りない」という場合と、「何かをしたいと常々思っていて、気づくとぜんぜんできていないときなどに使ってしまう場合」があるんじゃないだろうか？

前者の場合はやはり、「時間が足りない」というべきである。きっとそれまでの自分の計画があまりよくなかったせいで時間が足りなくなるという状況に陥ってしまっている場合が多いと思う。

後者の場合、これは「本当にやりたいのか？」と自分に質問してみる必要があるようにおもう。本当にやりたいのであれば前回の投稿までに書いてきたように、「人間は自分で行動を選択できる」という事を信じて、自分で自分との約束を守るようにしていけば、おのずとできていくようになるだろう。

要（あまり要していないかもしれないが）するに、今回私が言いたいのは、忙しく動いていても「時間がない」という事態はあまり起こりえないのではないか？ということだ。誰も時間は管理できない、管理できるのは自分自身だけなのだ。
自分が何をしたいか、何をすべきか、どのようにそれを達成するか。という自己リーダーシップをうまくとっていれば、「時間がない」という言葉は出てこないのではないだろうか。

この投稿はほとんど「７つの習慣」の内容と僕の感じたことであるが、ここまで読んできて思ったのは

人間はいつでもどんな状況にあっても
・自分で現実をどう捉えるか選択できる
・自分を客観視し自分が行動をとった後のことを想像できる。
・自分でどう反応するか（行動するか）を選択できる

ということが非常に重要だと思う。自分というものは自分でどのようにでも影響できるのだ。直接影響できて一番近い存在なのは自分なのだ。自分の置かれた環境（社会）、他人に影響を与えることは簡単ではない。他人の場合はいつか書いた「心の扉は内側からしか開けることができない」というように、非常に困難である。それをこじ開けようと他人に対して強制したり、いやな態度をとれば、その扉はそれまで以上に硬く閉ざされてしまうだろう。それよりも自分を見て、自分がどう変われば、その扉が内側から開きやすくなるかを考え、自分を変えるほうがずっと簡単かもしれない。

人間は弱いもので（強い人も多いが）、自分が苦境に立つと、どうしてもそれから目を背けがちで、そうなった理由を自分以外に求めてしまう。非常にパワーのいることかもしれないが人間の自由意志や主体性を信じて、自分でできる限り最善の反応をとるように心がけ、自制できたらよいと思う。

それがスムーズにできるようになれば、きっと７つの習慣の中での影響の輪の拡大が実感できるのではないだろうか。
今回もひとつ「十戒」の監督、セシル・Ｂ・デミルによるquoteを紹介する
・It is impossible for us to break the law. We can only break ourselves against the law.

XI-th stone: getting back Pureness

--What I've thought--
人間は生れ落ちてから、数え切れないほどの出来事を経験するうちに物事に対する見方、以前IIIでは「レンズ」と書いたが、がどんどん構成されていく。これが強すぎるとバカの壁のようなものができてしまうように思う。また養老孟司 氏の「バカの壁」については読了しているのでいつか何か書きたい。

また、老婆と婦人の絵を出すが（これしかないのかといわれそうだが）、これはこの「レンズ」を体験するのにいい例である。
これでは、見る人がひとつの現象を異なった事実として捕らえている。これは単に事実だけではなく人がどう行動したかを見たときにも同じように当てはまる。

今回はこの心の純粋さについて書いてみたいとおもう。幼児を思ってみてほしい。幼児はよく、ささいな事で喧嘩するが、すぐ仲直りしてしまう。彼らは言葉の裏を読まないほど純粋なのだ。「ごめんなさい」と言うことですべてを許してしまうほど、この言葉が幼児たちにはストレートに吸収できるのだろう。
だんだん成長するにつれて、「人の心の動き」や「自分」といったものがわかってくる、レンズの形成だ。このレンズを通すことで「ごめんなさい」といった事実はそのままではなく、いろいろな形で吸収されることになる。このレンズはいったいどこからくるのだろうか？ではこれを取り外すためにはどうすればよいだろうか？
少なくとも、僕はこのようなレンズを通して物事を見るのは好きではない。常に取り除きたいとおもっている。幼児（子供）の純粋さをとどめたまま成長したいものだ。
芸術や音楽は大人でも子供の心のまま残せる領域である。というのを聞いたことがあるが、僕はこの言葉には賛成だが、足りないと思う。

僕の結論は、「自分」というものがどこまで固いかという点にある。このままでは意味不明かもしれない。うまく書き下せるかわからないが、詳しく説明してみる。人は成長するにつれて「自分とは何か」を形成していく。アイデンティティーの形成と言われるものだろう。通常の人はアイデンティティーは自分を限定するようなものになっていないだろうか。しかし、「自分」とはもっと精神的に深い存在なように僕は思う。僕はこの体で生まれてきて、「僕」という精神は生まれてからこの体に宿っている。この「僕」という体に宿っている「精神」こそが「自分」なのではないか。と最近は思っている。

変化を起こせないものもあるが、多くの場合、前回書いたように「自由意志」の力によって変更可能だとおもう。自分の性格、自分の心の動きのパターンの多くはレンズを変えたり、はずしたりすることで、どう感じるかも変わるし、どう反応するかも自分によって変えられるのだ。そう考えると、通常アイデンティティーを形成している多くのもの、ここでは上に書いたような自分の能力を限定してしまうようなもんだと仮定しているが、それは「自由意志」の力によって変えられるのだ。

この「自由意志」の力を備えた「僕」という体に宿った「精神」をアイデンティティーの要素の中心におけば、「自分」という物が非常に柔軟な物に変化するだろう。こんなことを書くと、すぐ心変わりをする自分のない人間じゃないか。といわれそうだが。自分のない人間とはなんだろうか？と逆に問いたい。そういった、よく心変わりをする、それを自分で選択するという心の動きが「その人」なのではないだろうか。

またの機会に書きたいと思っているが、７つの習慣によれば人間は「影響の輪」という物を持っている。これは自分が直接は変化を働きかけられる範囲を示している。自分と周りと人との人間関係が良好ならば、その人との関係も「影響の輪」に入れることができる。そして「自分」とはResponsibilityと自由意志（主体性）を発揮することによってすべてこの「影響の輪」の中に入っている。このことからもわかるように、人間というのは思ったほど硬くないように思える。人間は思ったよりもずっと柔軟なものなのだ。それには、このレンズの存在を実感し、自由意志の力を発揮しようと心がける事が非常によいと思う。

今回は、成長するにつれて数も多くなり、厚さも増してしまう「レンズ」について考えてみた。誰しもこのレンズは最初は持っていない状態で生まれてくるはずなのに、いつの間にかレンズが形成される。通常、この取り除くのが難しい「レンズ」が、なぜ取り除くのが難しいか。を考えてみた。

注) 本日comment機能を追加しました。なにかコメントや訂正がありましたら、お願いします。

X-th stone: The Power of FREE WILL

--what I've thought--
今回はVII-stoneの最後で書いた、自分に対してのリーダーシップを発揮する原動力になっている「自由意志の力」について書こうとおもう。この自由意志にはもちろんResponsibilityという言葉について考えたときに書いた、「反応する能力」をも含む大きな意味がある。反応する能力を発揮するのもしないのも、自分自身なのだ。

この自由意志、というより自由意志という存在の認識は自己管理をするのにはとても役に立つとおもっている。それは自分で何をするかを決定し自分でその決定に従い行動する力である。周りの影響に影響されず自分で主体的に実行する能力のことだ。

自由意志とか主体的に実行するといって、何も大きな変化、決定をし続ける必要なない。人間は生まれてから数え切れないほどの選択、決定をする。大きさにかかわらずだ。そして、その決定のほとんどが小さなものであるといっていい。ほとんどの人は気づいていないかもしれないが、いつも何気なく行っている小さな日々の決定に自由意志や主体性を発揮すれば、おどろくほど大きな成長ができるだろう。

「自分で自分に約束をし、その約束を守る。」この一見単純そうに見える自分に対して誠実に生きる続ける事ができれば、III-th stoneで紹介した最後のquoteにあった「人生を刈り取る」ことができるのではないだろうか？

これを実行するためには非常に大きな自制の力が必要である。自分の価値観や自分の方向性に照らし合わせて、衝動や瞬間における欲望や感情ではなく、「イエス」「ノー｣を自分に対して言える、そんな力が必要だ。それにはやはり自分がその選択をした場合を客観視し、自分がその反応（行動）をとったときに起こる結果や自分に対して誠実かどうかを判断し、それを考慮した上で行動すればいい。それがし続けることを私は目標としている。

だからといって、自分の価値観のそぐわないことに対してすぐ「ノー｣を言えといっているのではない、それよりも燃えるような「イエス」をいえるような事項を自分の中に持つことが大切だと思う。その燃えるような「イエス」、すなわち自分の意思の固さ、または、その人にとっての重要さが、他の人に伝われば、「ノー｣を言ったところで人間関係が悪くなることはないと私は信じている。

こんな面白い話が載っていたので紹介する。ある教授が授業であるとき生徒にこういわれた。
「授業を休ませてくれませんか。テニスの合宿に行かなくちゃならないんです」
「行かなければならないのか、それとも行きたいのか。どちらだね」
「いやぁ、本当に行かなければならないんです」
「行かなかったらどうなるんだい」
「行かなかったらチームからはずされます」
「その結果についてどう思うかい？」
「いやです」
「つまり、チームからはずされないという結果がほしいから、行くことにしようと思ってるんだね。では授業に出なかったらどういう結果になるとおもう？」
「わかりません」
「よく考えてごらん。授業に出なかったら自然の結果としてどうなるだろう」
「単位を落とされたりはしませんよね？」
「それは社会的な結果だね。人がつくるものだ。テニスのチームに参加しなければプレーができない。それは自然の結果だ。クラスにこなかったら、その自然の結果としてどうなるだろう。」
「学ぶ機会を失うでしょうね」
「そうだ。だからその結果と他の結果を比較して選択しなければならない。私だったらテニスの合宿に行くことを選択するだろうね。しかし、何事にもねばならないとは絶対にいわないでほしい」
「では、合宿に行くほうを選びます」
と彼はもじもじ答えた
「なんだって、私の授業を休むって？」
と冗談半分に私は言い返した。

このエピソードは先の自由意志の力を教授が導いた良い例である。この話の中の「何事もねばならないとはいわないでほしい」という一言に非常に僕は感銘をうけた。自分がどうしたいのか？自分の目的、目標のために何を選択するのがベストなのか。それを考えれば「ねばならない」とはいえなくなるだろう。
とにかく、人間には「反応する能力」があり「自由意志」が存在するのだ。どの道を選択するのも、苦境等にさらされたときどう反応するかも、自分で選択できるのだと実感できる。

何か、要点のまとまらない散文になってしまったが、ここで終わることにする。

--INFORMATION--

最近、投稿の内容が勉強した内容が主体になりつつあり、MileStones to EVERPEACEというタイトルに合わない内容が多くなっているため、本日以降の私が日々学習した結果は

Study Notes of EVERPEACE

に移行します。そちらのほうのノートは私が日々興味をもって学習・研究している内容です。ノート形式で日々まとめていきますので、よろしくおねがいします。これからはこのページでは"what I've thought"、"What happened today"を中心にやっていくことにしよう

IX-th stone: Mixing Markov Chains(3)

前回couplingを使ったmixing time を算出した。今回はn-cube上のランダムウォークによって。2^n個のサイズを持つ空間がで許容誤差εを用いてO(n ln(nε^(-1)) ) 時間でサイズの見積もりが可能なことを示す（randomized アルゴリズムにすると、誤差がありながらもいかに時間が減るのかが実感できるよい例になっているだろう)

まずn-Cubeの定義をしよう
Definition: n-Cube Cn=(V,E) (undirected)
V={0...2^n-1},E={(a,b)| aとbを二進表現したときのHamming distanceが1}

再帰的に表現することもできて、 CnはCn-1 を２つ用意してそれぞれのCn-1の同じラベルを持つ頂点どうしをつなぐことで得られる。C0は頂点のみからなるグラフ。

さて、Cn上のMarkov Chain　MCc を考えよう。それは以下のとおり

MCc: random walk on Cn
starting vertex X0=0 repeat:
1.pick (i,b)∈　{1...n}×{0,1}
2.Xt+1 をXtのi-th bit をb に変更したものとする

こうすると任意の頂点間X,Yの遷移確率Pは

P(X,Y)=
1/2n if Hamming(X,Y)=1
1/2 if X=Y
0 otherwise

ここでMCcはirreducibleであることは自明。そしてもともとCnにはないselfloopも状態遷移に加わっているのでaperiodic.すなわちergodicである。しかもsymmetricである。よってこのMCcはuniform distributionに収束する。あとはMixing　Timeがどれくらいかである。それをcouplingを使って算出してみよう。

その前に、算出のために必要な面白い問題をひとつ。

coupon collecting problem:
n種類のクーポン券が無限にあります。クーポン券は毎回どの種類かはランダムに選ばれます。全種類集めるためには何回クーポン券をもらわないといけないでしょうか？
略解）　k種類集まった時点より後では、新しいクーポンをもらえる確率は毎回 1-k/n である。また、確率pの事象が起こるまでの回数の期待値は1/pであるから、答えは
Answer= sum(k=0,n-1) n/(n-k) = n(1/1+1/2+1/3+...+1/n) ≦n log n+n
よって回数の期待値はO(n log n)であることが分かる

この問題を使ってMCc上のcoupling時間を見積もることができる。
次回、実際にこのCoupling Timeを見積もってみる。

VIII-th stone: Mixing Markov Chains (2)

--What I've learned--
前回、finiteかつergodicなMarkov Chainは必ずstationary distributionに収束し、
そのChainがSymmetricな場合はuniformになることがわかった。

ではより複雑な定常確率分布(stationary distribution)に収束するようなランダムウォークはどのように構成すればいいのだろうか？そしてそれはどれくらいの長さをシミュレートしたらstationary distributionに収束するのだろうか？
これにはMetroPolis algorithmというものがある、このアルゴリズムは任意のstationary distributionに収束させることができるランダムウォーク構成法である。これは２０００年のComputing in Science and Engineering のTop10アルゴリズムにランクされているそうだ

The MetroPolis algorithm
これは非常にシンプルかつロバストなアルゴリズムで、任意の希望するstationary distriution π に収束させることができるランダムウォークを構成する。

The MetroPolis Algorithm
Starting at x, repeat;
1. Pick a neighbor y uniformly with probability 1/2Δ(max degree)
2. Move to y with probability min(1, π(y)/π(x))
3. With all remaining probability stay at x

このTransitionと、πは前回のThm2.を満たし、そしてuniqueなものにしか収束しないことがわかっているので、このπはstationary distributionとなる。

前回のindependent set すべての集合Ωに対しては任意の正定数λ＞0によって、
π(x)=λ^|x|/Z (Z=sum(λ^|x|))
とする。すると、(x,y)という辺がHにあるときπ(y)/π(x)=λとなる。

あとは、このランダムウォークがどのくらい速く収束するかがわかるといい。

そこでMixing Timeという概念を導入する。所望のstationary distribution πとシミュレーション途中のdistribution Ptに対してそのtotal variation distanceを定義する

Definition: The total variation is
||Pt,π||=max_{x}( 0.5sum_{y}(|Pt(x,y)-π(x)|))

この距離によってMixing Time τは

Definition: Given ε>0, the mixing time　τ(ε) is
τ(ε)=min{t : ||Pt',π||＜ε, forall t'≧t}

そして、あるMarkov Chain　MCについて、τ(ε)=Poly(n,log ε^{-1})となるとき、MC is rapidly mixingという。

また一般的なτのバウンドとしてTransition Matrix の固有値(eigen value)を用いたものがある。

Thm3. let q=min(π(x)), Define Gap(P)=1-|λ1|(λ1 is max eigenvalue), then
・τ(e)≦1/Gap(P) log(1/qe)
・τ(e)≧|λ1|/2Gap(P) log(1/2e)


もうひとつ収束時間をboundするための方法としてCouplingというものがある。

Coupling
coupling はΩ×Ω上のMarkov Chainで以下の２つの性質を満たす確率過程(Xt,Yt)とする1.Xt,YtはそれぞれもともとのM(Ω上のMarkov Chain)のコピーである。初期状態はそれぞれx0,y0
2.If Xt=Yt , then Xt+1=Yt+1

これは初期状態x0,y0から独立にスタートしたランダムウォークが時刻t以降同じパスを通るというものである。次に任意の初期状態の対x0,y0に対してTxy=min{t : Xt=Yt|X0=x0,Y0=y0}としてcoupling Timeを

Definition: coupling time T of M is
T=max_(x0,y0)(E[Txy])

とする。このcoupling time Tと 許容誤差ε(>0)を用いて収束時間τは以下で抑えられる

Thm4. τ(ε)≦ceil(T e ln(ε^{-1}))

このcouplingについても、E[Txy]をどうすればよいのか？という疑問がのこる。
これを解決したのがpath couplingという方法である。これはまた次回。

VII-th stone: 右でlead、左でmanage

--what I've thought--
以前から、リーダーシップとマネージメントには興味があって考えていたことがあったが、今日またそれについて思ったことがあるので書いてみたい。

「リーダーシップ」と「マネージメント」は私は別物だと考えている。英語で"manage"を辞書でひいてみると

manage[他動詞]
1.(事業などを）処理する、経営（管理）する
2.どうにかなしとげる
3.なんとかする

とでてくる。マネージメントとはマネージする事と考えられるので「処理すること」「なんとか成し遂げること」となる。では"lead"はどうだろうか。

lead[他動詞]
1.導く、案内する、先導する
2.先頭に立つ
3.連れて行く

となっている。リーダーシップとはleadする素質のことだと私は思っているが、そのためにはどうしても「leadすることとは？」を理解する必要があるだろう。ここで"manage"と"lead"の決定的な違いについて気づいてほしい。

"lead"というのは明らかに方向性をもった言葉である。何か（リーダーであればそのグループ）をleadするというのはそのleadする集合に進むべき方向性やゴールを与える事だろう。それに対して"manage"はどうだろうか？先の意味からもわかるように"manage"には方向性を含む意味は見当たらない。どちらかといえば、今の状態で目標や方向は別に与えられており、その目標を成し遂げるために全力を尽くして頑張るといった意味に取れる。

すこし抽象的な話なので例を挙げてみたい。森を切り開いて道路を作る集団があったとしよう。木を切り道を作るのは労働者。その労働者の後ろのほうで木を効率的に切る方法や工期どうりに進む方法、労働者たちのメンタルケアなどをつかさどるのがマネージャー達。そしてリーダーは何をしているかといえば、近くの一番高い木に登りどちらの方向へ進めばいいかを見定め、スケジュールをしそれを全員に伝えることである。

上の例で伝わったかどうかはいささか心配ではあるが、リーダーシップとは方向（目標）を与えるものであり、マネージはその方向（目標）をどう達成するか？にそれぞれ中心があるのだ。

では、「リーダーシップ」すなわち「リーダーに必要な事は？」という問いについての僕の考えを載せておきたい。それは以下の４項目にまとめられる。

1.状態の正確な把握

リーダーは必ず集団をリードしているその集団が現在どのような状態にあるかは正確に把握する必要があるだろう。先の例でいうとマネージがうまく行かず、労働者たちの効率が悪いにもかかわらず、厳しいスケジュールを出すようでは論外だろう。

2.要求の正確な把握

集団というのは必ず何かを要求している。その要求を正確に的確に把握し、それを満たしてやることがリーダーには必要だろう。マネージャーから工期の変更の要求があれば、本当にそれが妥当かどうか判断し、工期を変更しなければならないだろう。1.とあわせてこの2.も怠れば、4.の信頼関係というのはいとも簡単に崩れ去ってしまい、集団は進む道を失ってしまうだろう。

3.方向性の明確な提示

リーダーは集団の進むべき道を示す道標のような存在である。しかし、提示したい方向はあいまいに提示することは許されない。なぜならそれが曖昧であれば、集団の進むべき道が曖昧であることになり、マネージャーの"manage"も曖昧になってしまうからだ。
そして、明確な提示はリーダーとしての意思の固さや信頼感を集団に与えるのにとてもよい手段である。この明確な提示という点では、現在の日本の総理大臣である小泉純一郎氏はこれをとてもうまく実践できているように感じる。あの断固たる意志の固さや、それによって生ずる信頼感によって国民的な支持を受けているんだろう。

4.信頼関係の確立

これは1.2.3.を実践していれば自然についてくるような気がするが、信頼を失ってはどうしようもない。人間と人間はやはり相手を信頼することで初めて相手の意見に耳を傾けようとするのではないだろうか。ただ効率的だからとか、利益を生む方法だから、とかいった表面的な理由でしたがっているマネージャーや労働者たちよりも、やはりリーダーは集団全員から信頼されるべきだ。

以上の４つが私が考えるリーダーの素質である。しかしこの４つをうまく実践するためには非常に強い意志の力とプレッシャーに耐えなければいけないだろう。以前授業で聞いたのだが、授業をしている先生がUniversity of Californiaの学長さんに会ったときのことだそうだが、先生が学長さんに
「リーダーに必要なことは？」
と質問すると、
「3-Ps; Those are Plannning, Pursuation, Patience」
そしてその三つの比率についても言っていたそうだがPatienceが９０％で後の２つが１０％だそうだ。この話でもわかるように忍耐力というか、非常に強い意志が必要なの事がわかる。

今までは集団を自分以外にしてきたが、それは自分自身でもかまわない。私は「自分」とは「自分のリーダーでありマネージャー」であると思う。それを私は「自分とは自明なリーダーでありマネージャーである」といつも表現している。先の４つの条件に当てはめてみると、

1.自分は今どんな状態にあるか？
2.自分はこれからどこへ向かいたいのか？
3.自分は今どちらへ向かっていることを自覚する
4.自分で自分との約束を守り、自分を裏切らず、自分を信じる
（自分、自分、とかくとなにか哲学チックになって気がひけるのだが）

1.2.3は次の言葉でも置き換えられるかもしれない。
「常に進むべき方向（目標）を持ち、それを今自分のできる限りの方法で達成しようとし、その方法と方向を自覚すべきだ。」

あとは、それをするために十分な自分になればよいのだが多分これが一番難しいだろう
この、自分に対してリーダーシップを発揮するための原動力についてはまた別の機会に書くことにするが、この原動力についての同じような内容の私のすきなquoteを２つ紹介する

・"You shape your habits, then your habits shape you."
・"思いの種を蒔き、行動を刈り取り、
　　行動の種を蒔き、習慣を刈り取る。
　　習慣の種を蒔き、人格を刈り取り、
　　人格の種を蒔き、人生を刈り取る。"

タイトルの右と、左について触れるのを忘れていた。
リーダーシップとは、簡単に言えば方向性を与えることである。方向性を与え、そちらへ向かったときに望む結果がどう生まれるかはその方向しだいである。そういう時はイメージや感性をつかさどる右脳を使う必要があるだろう。
またマネージについては目標は設定されており、それをいかに達成するかという手段に中心があるので、論理や言語をつかさどる左脳を活用するとよいだろう。
そういった意味でこのタイトルをつけたのだが、本文の大部分を反映していないことを許していただきたい。

注)英語の訳は研究社中辞典による。

VI-th stone: Mixing on Markov Chains

--What I've learned--
このページにリンクがあるLance Fortnow氏のMy Computational Complexity WeblogにFOCS2003でのDana Randall氏のMarkov chainでのMixingに関するTutorialの記事がのっていた。組み合わせ理論に興味があるのに伴って、いやべつに伴っていないかもしれないが、特定の条件をみたす組み合わせが何通り存在するかという数え上げにも興味がある。その数え上げの方法のひとつしてMarkov Chain Monte Carloというものがある。それは対象とする組み合わせ全体の集合を考えてその上にランダムウォークを定義する。するとその集合のサイズがある程度の誤差のもとでわかるというものらしい。実際誤差を縮めようとすればするだけ計算時間がかかる。しかしそれはすべてその誤差の逆数の多項式で抑えられる。

そして今日は以前図書館に頼んであったarc coloring is NP-Completeの証明ののっている論文もとどいた。これはまた次に読むことにしよう。Complexity WeblogにのっていたEli Upfal氏のPerformance Analysis of Dynamic Network Processesも興味深い。また時間をとって読むことにするか。もしかしたら読まないかもしれないが。

Mixing on Markov Chains
Markov Chain Monte Carloとは非常に大きく、そして複雑な集合を計算機的に解析するための一般的なフレームワークである。メインのアイデアはある特定の性質(ergodicかつsymmetric)を満たすマルコフ課程上のランダムウォークを定義してそれを何ステップかシミュレートするとそれがuniform distributionに収束する。すなわち何ステップが後にはそのランダムウォークで各状態にいる確率がすべて等しく1/（空間のサイズ）となるものである。

ここからは例をつかって説明していこう。あるグラフG=(V,E),|V|=nの独立点集合全体の集合を考えよう。Ω={all independent set of G},and connect I and I' iff |I XOR I'|=1として状態空間を構成する。そして次にこの有向グラフH上のランダムウォークPを構成する。それは次のとおり

Transition P:
Random walk on H starting at x:
1.Pick a neighbor y.
2.Move to y with prob. P(x,y)=1/Δ
3.With all remaining prob. stay at x.

ここでMarkov Chain MCがergodic(エルゴード的)であることの定義をしよう。

Definition: Markov Chain MC is ergodic if it is:
1. irreducible: for all x,y∈Ω, there exists t s.t. Pt(x,y)>0; Hがconnectedを示している。どこからスタートしてもどの状態へもたどり着けるということ。
2. aperiodic: for all (x,y)∈E(H),g.c.d{t:Pt(x,y)>0}=1;xからyへ遷移する確率が０でないステップの最大公約数は1。すなわちxからyへ遷移することが周期的には起こらないということ。

そしてfiniteかつergodicなMarkov Chainに対して以下の２つの定理が成り立つ。

Thm1. Any finite and ergodic MC converges to a unique stationary distribution.
Thm2. The stationary distribution Pi satisfies: Pi(x)P(x,y)=Pi(y)P(y,x)

先に作ったランダムウォークはsymmetricなのでPi(x)=P(y)が成り立つ。よってPiはuniformになる。あとはどうやって収束の早いランダムウォークを作り、それがどのくらいのステップで収束（stationary distributionに近づく)かを調べなくてはいけない。

これ以降は明日につづく。

V-th stone: サブタイトル

--What happend today--
もう、１６日か。weblogのつけはじめだからかもしれない、いや絶対そうだと思うが、すごいペースでマイルを獲得中だな。
さっき友人のO君とページのタイトルについて話していたら、
「サブタイトルつけるといいね」って話になった。彼の最初に書いてくれたのは「dreaming when I achieve」というものだった。僕のタイトルの意味を理解しているいいサブタイトルだと思う。個人的には「dreaming the day I'll achieve」と「day」のほうがいい響きかなと思ったりもする。他のサブタイトルも考えてみて是非サブタイトルをつけたいと思う。

IV-th stone: タイトルパクリ疑惑浮上！

--What happened today--
今日、Y君がこのページについて一言
「このタイトルみたときにロードオブメジャーに似てるとおもった」と。
な、なんですと？？？ていうか、なにそれ？？どこかで聞いた事はあるけど、なんですか？それ？
聞いてみるとどこぞの音楽グループだとか。はいはい、そんなどこぞの音楽グループといっしょにしないでいただきたいんですけど。
まぁ意味的に似ていないことはないと思うが、僕はそのロードだかなんだかには興味は一切なし。したがって、その名前は僕の頭には微塵もない。よって、断じてパクリにはなりえない。

しかも、絶対僕のタイトル「MileStones to EVERPEACE」のほうが単語の選び方ひとつとってもセンスがいいと思うのですが。いい機会なのでこのタイトルの意味を説明しておくと、
・MileStone=古代ローマ帝国が築いたローマ街道において１ローママイルごとに道路の両側に立てられていた石のこと。通常長い道のりの通過地点として比喩的に用いられる
・EVERPEACE=これは僕のハンドルネームである。そして「ever+peace=永遠の平和」という意味も含んでいる。ちなみに英語にはこの単語は存在しないようだ。僕による造語である。
この２つをつなげると「EVERPEACEへの布石」となる。EVERPEACEとは自分、すなわち「終わる事のない「成長しつづける自分」への布石」を意味している、私の綴る思いが成長していく自分の記録となり、自分のこれからの進む道を選ぶときに過去をふりかえり、指針とするための布石(MileStone)として記録していこうというのがこのweblogの目的である。それに加えて「EVERPEACE（永遠の平和）への道もまた果てしないもの」という意味も若干ではあるがかけてある。ということで、ロードなんちゃらとは完全に別物です。

III-rd stone: Responsibility ⇔ Response + Ability

--What I've thought--
最近、また「七つの習慣」を読み直している。第一章にあるタイトルの言葉に久々に衝撃をうけた。私の解釈を交えながら、その本の内容を紹介したい。

Responsibilityは日本語では「責任」とよく訳されているが、この「責任」とはいったいなんだろうか。

人間は、他の動物とは決定的に違った能力を持っている、「記号の操作」ができることが決定的な違いだともいわれるがもうひとつ、「自分を客観視」できるという能力が他の動物とは決定的にちがっているそうだ。また、人間は生きていく上で無数の選択をする。自分の置かれている状況で自分を見て（主観的にも客観的にも）、そして自分がどう行動するか常に選択し続けているのである。

もうひとつ、興味深い事実としてそれぞれの人が感じる真実はひとつではないという事実を紹介する。人は生まれてから様々な環境の中で様々な経験をする。その経験の中でひとつの現実を見たときにその現実をどう受け止めるかという「レンズ」のようなものを形作っていくのである。
老婆にも見えるし婦人にも見えるという絵をご存知だろうか？最初にこの絵を見たとき、ある人は「老婆」に見え、ある人は「婦人」に見える。
この事例は少し単純すぎるかもしれないが、本質をよく表現している。人々の感じる真実とはひとつではないということだ。この白と黒のまざった図柄には「老婆」という真実と「婦人」という真実が混在している。どちらも正しいのだ。

ここで、「責任(Responsibility)」という言葉に話を戻そう。ここでは、この「責任」を社会的なものではなく個人的な責任という意味でとると、非常に説得力のあるものに思えてくる。どんな状況でも人間は反応を選択できるのだ。どんな環境、どんな苦境においても、人は自分の反応を選択できるのだ。その能力の高い人が真に「自分の人生に責任を持って生きる」事ができるのではないだろうか。

レンズの話にしてもそうだ。通常の人はこのレンズに気づいてはいない。「パブロフの犬」にあるように特定の刺激に対して特定の反応を示すことが当然だと思っている。しかし、私はそうではないと思っている。何か周りの環境から自分に対して刺激があったとき、どのレンズを通してその刺激を感じ取るかは選択できる。しかも、その刺激に対してどんな風に反応するかは、これもまた選択できるのだ。

また、注意しなくてはいけないのは、反応は選択できるが「結果」は決して選択はできないということである。ある選択をして、行動し、その結果が望まないものになるか、望むものになるかは選択できないのだ。しかし、「成功は失敗の彼方にある」という言葉のように、失敗から何が失敗だったかを導き、同じ過ちを犯さないよう学習していけば、きっと成功への道は開けていくのだろう。

この「反応は常に自分で選択できる」という事実をよく描いているquoteがいくつかあるので紹介したい。
・エリナー・ルーズベルト"あなたの許可なくして、誰もあなたを傷つけることはできない”
・マハトマ・ガンジー"自分で投げ捨てさえしなければ、誰も私たちの自尊心を奪うことはできない"
もうひとつ"心の扉は決して外側からは開かない。その人自身が内側から開けることをしなければ"のようなものがあった覚えがあるが、正確に覚えていない。また思い出したら、載せることにする。
ちょっと違うかもしれないが、最後に好きな出典不明のquoteをもうひとつ
" 夢は決して破れることはない。自分が夢をあきらめたとき、破れたようにみえるだけだ"

出典： 「七つの習慣」 スティーブン・Ｒ・コーヴィー著（キングベアー出版)

コメント：　アップしてすぐ、友人のＹ君からケチつけられて「＝」じゃなくて「等価(⇔)」のほうがいいっていわれて訂正（涙

II-nd stone: 屈辱の二撃

--What happened today--
今日は３連休に続いて４日目のオフ。気持ちよく休日を過ごしているところへ、友人からのメール「本日履修登録締切日」と。
すっかり頭からぬけきっていたため、慌てて学校へいって登録。登録も終了してほっとしているところへ今日の屈辱の２撃が。

第１撃
今日、後輩I君からminimum vertex coverの近似アルゴリズムの質問を受ける。
これと等価なmaximum independent setを研究していた身で質問に答えられなくて、結構屈辱的。一から勉強しなおしだ。
頂点の次数の高い順にとっていくという単純なものだが、このアルゴリズムの近似率がTheta(lg n)になるというのが理解できず（涙
ひとつlg n 倍になるインスタンスを見つければ下界だけでもいえるのだが。その後、自分で作ることができたわけではないが、googleで発見。
lg n　の近似率のところは\sum 1/k =O(lg n)を利用。

bipartite(L,R) graph を作る。Lは最適解,Rはgreedy solution.
|L|=m, |R|=(m+m/2+...+m/m)edgeの張り方は、以下のとおり
・それぞれのm/i 個のR内の頂点からはLのi個の頂点へ重なることなくedgeをはるすなわち、m/i 個のうちひとつの頂点からはi本のedgeをLのi個の頂点へ張る。そしてm/i個のうちのどの２つも共通のLの頂点へ辺は引かないようにする。

こうすることで、greedy ではRを、最適解はL であるので
|R|/|L|=lg n となり、めでたしめでたし。
あとは上界の証明がのこる。木曜のゼミを待とう。

第２撃
自分の居室とは別の部屋で後輩I君とmin vertex coverについて話していると、別の後輩のH君が登場。挨拶をしてみたが、鼻であしらわれる。かなり挑戦的な態度だった。

ぜんぜん関係ないが、ヤフオクでLoveStories I,II,IIIがセットで現在5250円だった。どうしようかな。迷うなぁ。

The First MileStone to EVERPEACE

Hello.
This is the start of my weblog history.
I don't know what I'll write in my weblog but I hope this weblog would be memories
of my usual days or history of my thoughts.
And, in the future, I wish this weblog would be a clue to choose my direction.
I'm thinking that I would write mainly two things.
One is "What happened Today?". I 'll write just what happened to me in this section.
Another is "What I've thought." . I 'll write my thoughts which I was thinking today.
I personally wish to write more things in this section than "What happened."

Let's start introduction of myself.
My handle name is Everpeace, of course I eager for the world in peace.
I love John Lenon's Song "Imagine". This handle name was born in my heart when I'm listening "Imagine".
These are my mental aspects, I introduce physical? aspcets of myself below.
I am a Master student of Nagoya Institute of Technology.
I belong to Wada Laboratory in Dept. of Electorical and Computer Engineering.
And I am majored in Computer Science.
My Interests are Combinatorics, Computational Complexity, Approximation Algorithms, Graph Drawing and so on.
Now I'm working in VLSI layout for full binary-tree in Optimal Area Rectangles with arbitrary aspect ratio.
I want to write more of my self but It's time to sleep.
I keep this weblogging, so I'll have enough chance to introduce of myself.


--What happen's today--
I went to Apita(Nagakute) for exchanging dog's cloths which I bought yesterday.
Because size of those were too small for Judy. oh, Judy is my sweet sweet pet.
If I have a chance, I'll upload his photos.