Pが対象行列の場合、xnはすべての要素の値は等しい。(一様分布になる)1.以外の場合は、xnはx0の値によらない。(エルゴード性)少しだけ補足。1.はベクトルに単位行列かけるだけなので確率分布がかわらないのは当たり前。2.は、次に特定の事象がおこる確率は、現在の状況に依存しないことを表している。サイコロをふる場合など。これはマルコフ性を持つ事象とは呼ばないのかもしれない。R^2のときは感覚的に分かりやすい。天気の推移にマルコフ性があると仮定して晴れの次が晴れの確率を0.9晴れの次が雨の確率を0.1雨の次が晴れの確率0.1雨の次が雨の確率0.9とする。このとき確率推移行列は対称行列である。晴れになるとなるべくその状態を保とうとするし、一旦雨になるとなるべくその状態を保とうとする。これは感覚的に分かりやすい。R^nの場合はどうか?これは対称行列を写像として見たときの意味を考えるか、対角化して極限を取るみたいなことをして数学的に証明できるのかもしれないが、大変そうなので直感的に理解する方法を考えてみる。オートマトンみたいな状態遷移図を書けば分かりやすそう。3次元の場合も、以下の図をみると直感的には定常状態では均等に落ち着きそうです。持っているところからはたくさん出て行き、少ししかないところからは少ししかでていかない。同じ色の線は同じ遷移確率を持るのがポイントです。(電子回路のオペアンプをバッファとして使う場合に定常状態がどうなるかを考えるのに似ているかも。確率遷移行列が単位行列以外の場合は、定常状態が初期状態によらないことを意味している。初期状態が何でもいいというのは、シミュレーションをする場合にとてもありがたい特性である。初期状態によらないということは、マルコフ性を持つ確率モデルは遷移行列によってのみ特徴づけられることを意味している。固有値とか固有ベクトルとかがここでも使えそうである。editorの略らしい。それはどうでもよくて、sedの正規表現のマッチングの小技的なものをメモとして書いておく。HTMLをパースする場合を考える。bump.y...のようなデータからHTMLのタグだけを消して、意味のある値だけを取り出したいとする。bump.y...のような出力をえたい。test.htmlみたいな書き方をすると悲しいことになる。(行全体にマッチしてしまい、すべて空行になってしまう。)これは、複数のマッチングが考えられる場合なるべく長いものにマッチする(最長一致)からである。この性質はsedに限ったことではなくて正規表現全般に言えることで、デフォルトでは最長一致である。最短一致を利用するためのオプションを持つ言語もあるが、sedには無いので何らかの工夫が必要となる。今回の場合は、閉括弧が現れた時点で一旦マッチングをやめるようにすればいいので、以下のように書くと思惑のデータがえられる。test.datとする。(スペースを用いるので''で第一引数を囲む。''を使うとエスケープ文字の扱いが変わるので<>はエスケープしない。※注)※注)シングルクオーテーションで囲んだ場合、シングルクオーテーション以外の文字は普通の文字と同じ扱い。ダブルクオーテーションで囲んだ場合は、"$`\以外の文字は普通の文字と同じ扱いになるそうです。UNIX2011年10月20日木曜日エピメニデスのパラドックス昔、クレタ人のエピメニデスはこう言った。「すべてのクレタ人は嘘つきである。」これはパラドックス(矛盾)である。彼の言ったことが本当だとする。本当のことを言った彼は嘘つきではない。彼はクレタ人は嘘つきだと言っているので、彼自身は嘘つきということになる。彼の言ったことが嘘だったとする。彼は嘘を言ったので嘘つきである。彼は嘘をいっているので真実は「すべてのクレタ人は正直者である」となる。いうことは彼は正直者であるはずである。上の論法には引っかかるところがある。「すべてのクレタ人は嘘つきである。」の反対は、「すべてのクレタ人が嘘つきだとは限らない。これをふまえて彼が嘘をついた場合をもう一度考えてみる。彼の言ったことが嘘だったとする。彼は嘘を言ったので嘘つき。彼は嘘を言っているので真実は「すべてのクレタ人が嘘つきだとは限らない。これは彼が嘘つきだという仮定に矛盾しない。いうことは、上記の命題は「偽」ということで実は矛盾ではない。元の命題を変えてみる。エピメニデスは言った。」この場合は、矛盾である。エピメニデスが正直者なら「私は正直者だ。」というはずだし、嘘つきなら嘘を付いて「私は正直者だ。ここでまた面白い問題が浮かんでくる。嘘つき(嘘しかつかない人)と正直者(嘘は絶対つかない人)しかいない村があります。通りがかりの人に質問をして、その人が嘘つきか正直者かを確かめたいです。あなたは何と質問すればいいでしょう?(「あなたは正直ものですか?」と聞いてもどちらも「はい。・・・・(自分で考えたい人は、ここから先は後で読んでください。答えは、2とおりあります。『お前は人間か?』と質問をする。『「あなたは正直者か?」という問いに「はい」と答えますか?』と質問する。Japan決勝の問題B「バクテリア」が非常におもしろかったので、オイラーの定理について以下の本で復習したことをまとめておきます。(数論の入門書としてかなりお勧めです。オイラーの定理、フェルマーの小定理、拡張ユークリッド互除法、中国の剰余定理などプロコンに頻出の定理はほぼ網羅しています。)※一部自分の考えも入っているため、間違えている箇所がありましたらご指摘ねがいます。nで割った余りについて考えます。pm^kmと素因数分解できるとします。pm^amとおきます。(Aはnと互いに素な数)。考えられるパターンは、以下の3つです。1なので、φ(n)はa^Nをnで割った余りの列の周期になります。kmとなるようなNに対してa^Nをnで割ったあまりは0となります。十分に大きなNに対しては、φ(n)はa^Nをnで割った余りの列の周期になります。nとすればよさそうです。mにおいてa^Nを評価して結果を中国の剰余定理で統合するようなことをしています。この場合もφ(n)はa^Nをnで割った余りの列の周期になります。断言はできませんが、こちらも式を追う限りだと、最悪でもN=nとすれば周期的になりそうです。プログラムでテストしてみます。0;}以下、実験結果。ランダムに2つの正の整数を取ったとき、半分以上の確率でお互いに素になるようです。iがjの素因数をすべてカバーするケースはまれでMAX_Nが大きくなるに従って減っていくように見えます。MAX_Nと見積もっておけば十分だといえます。2については、式と結果から考えてlogオーダーっぽい。sieveは難しすぎてまだ無理。sieveというのがあったので、これなら実装できそうである。110桁程度までだと、GNFSよりQSの方が効率がいいらしい。sieveだが、大抵の数は小さな素因数に分解できるというところが大きなポイントとなる。numberと呼びます。numberってどれくらいあるのでしょうか?以下の問題設定をします。numberの数がN/2を超えるのはkがいくらのときでしょうか?このkが小さければ、小さいほどQSを実装する側としては嬉しいわけです。他にも面白い解法がありそうですが、取りあえずパソコンのパワーを信じてがりがりエラトステネスで篩にかけます。普通のエラトステネスの場合は、素数か合成数かをマークしますが、今回は最大の素因数をキャッシュしていきます。numberの数がN/2以上になるkの値です。numberまで調べれば、2個に1個は使える数が入っているということです。篩にかける際に、実際に必要となるメモリのサイズは、p(53773)の二乗程度です。p(x)はxが何番目の素数かを表します。log(x)で概算します。4937程度の行列なら特別なこと(非ゼロの要素だけもつようなデータ構造)をしなくても、普通にメモリに格納できます。この感覚だと100桁程度の数をQSで分解しようとすると、スパースな行列を扱うためのアルゴリズムが必要になりそうです・・・。N}の集合全体の何%を占めるかを示します。横軸がk、縦軸が占める割合です。予想どおりのグラフの形になりました。100,000,000のときです。数学apacheのログを見て遊ぶ最近、apacheのログの見方が分かるようになりました。整形して遊んでみると面白いです。デフォルトでは、/var/log/apache2にログが吐かれます。基本的なことしかできないですが、一応まとめ。$1、$11などと書きましたが、これはapacheの設定によって違うので、自分の環境にあわせて適当に変えてください。あと、IPから場所を特定できるサイトがあるので、これと組み合わせるとおもしろいです。Analyticsだと都市名までしか出てきませんが、このサービスを使うと、大学名や企業名まで分かります。有名な海外大学からアクセスがあったりするとテンションがあがります。このサイトからは、APIが公開されていてHTTPでxmlデータを取り込むことができます。非商用のクエリは100件まで無料ということです。場所の対応データを溜めていくのもおもしろいかもしれません。T-shirtsゲットです!!Aが早く解けてしまって、暫く10位台だったので、かなり興奮してましたが、その後何もできませんでした。BとCトライしましたが、WAでした。やったことを書きます。角度が等しいので、三角形の面積は辺の長さによってのみ決まります。長い辺同士を掛けた方がお得なので、greedyに入れて行きます。アンテナが円の形をしているので、双方向キュー(STLのdeque)を使って実装しました。本番は直観のまま突き進んで、今回は運よくACだったけど、証明せずにsubmitっていうのはあまりよくない習慣です。証明を考えてみました。二番目に長いエレメントをx2とおく。x2の項が存在しています。これを背理法で証明してみます。x1*x2の項がないと仮定する。xqのxqとx2を交換する。すると、x1*xq、xp*x2という項ができる。xq)だけ変化したことになります。この変化分は負なので、x1*x2という組み合わせは最適値に含まれます。以下同様にしてgreedyにとっていけばOKです。バクテリアの増殖ただの繰り返し二乗法じゃない?と思ってやったけど最後のサンプルがあわない。何度やってもあわない。Aの採点方式が間違っているというアナウンスがあったため、Bのサンプルおかしいんじゃない?と疑いだす始末。してレッドコーダーの人達がACし出すので、おそらく何か勘違いしてるんだろうなと思いだす。コンテスト終わって、modのところで大きな勘違いをしているのに気付きました。