サンプリング定理が帯域幅のみに依存し、周波数の基準値に依存しないことの証明

数学 勉強メモ

　1. 概要

　サンプリング定理(標本化定理)とは、帯域制限された信号についてその帯域幅の半分の周波数で信号を測定すれば、元の信号を完全に再現できるという定理である。数学的には以下のようにしばしば表現される1,2。

よく見られるサンプリング定理
信号f(t)は、W[Hz]より大きい周波数成分を持たない信号であるとする。この時、時刻n/2W (n=0, \pm1, \pm2, ...)における信号値、x_n = f(n / 2W)を測定するだけで、元の関数f(t)を完全に復元できる。すなわち、 f(t)は、 
 
 \displaystyle {
f(t) =\sum_{n = -\infty}^{\infty}x_n \frac{\sin\pi(2Wt-n)}{\pi(2Wt-n)} \tag{1}
}
という関係式で完全に復元される。

　この証明は、例えば引用元の参考文献を参照すれば書いてあるので気になる方は各自読んでほしい。甘利さんの本は、シャノンの論文で触れているサンプリング定理の簡単な証明過程をより丁寧に補足して説明してあった。 また、ここでは敢えて「よく見られるサンプリング定理」というクドい言い回しをしている。というのも、本定理の真に強力なところは、帯域が0[Hz]から数えてW[Hz]ではなくても、任意の周波数f[Hz]からf+W[Hz]の帯域幅のみを持つ信号に対しても成立することだ。
　シャノンによる論文のサンプリング定理(式(1))の証明後にも以下のような記述のみがある。

"A similar result is true if the band W does not start at zero frequency but at some higher value, and can be proved by a linear translation (corresponding physically to single-sideband modulation) of the zero-frequency case. "

　しかしこの証明をググってみても全く出てこない(というかちゃんとわかる人たちには自明過ぎてわざわざ数式にする意味がないのだろう)。仕方ないので正しいと思われる証明を自力で行ったのでメモとして残しておくことにした。

2.問題設定と証明

　改めて、どのような問題を解くか以下のように整理する。前述した「よく見られるサンプリング定理」と比較して「真のサンプリング定理」と呼ぶことにする。

真のサンプリング定理
信号f(t)は、f[Hz]以上f+W[Hz]以下の周波数成分のみを持つ帯域制限信号であるとする。この時、時刻n/2W (n=0, \pm1, \pm2, ...)における信号値、x_n = f(n / 2W)を測定するだけで、元の関数f(t)を完全に復元できる。

証明

信号f(t)のフーリエ変換F(\omega)は、f \leq\omega\leq f+W において、


\displaystyle{
F(\omega) =\frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} f(t) e^{-i\omega t}dt    \tag{2}
}

F(\omega)のフーリエ逆変換は、|\omega| \lt f , f+ W \lt |\omega|においてF(\omega) = 0より、


\displaystyle{
\begin{eqnarray}
f(t) &=&\frac{1}{\sqrt{2\pi}} \int_{-\infty}^{\infty} F(\omega) e^{i\omega t}d\omega \\
&=&\frac{1}{\sqrt{2\pi}} \int_{-2(f + W)}^{-2\pi f} F(\omega) e^{i\omega t}d\omega 
+\frac{1}{\sqrt{2\pi}} \int_{2\pi f}^{2\pi(f+W)} F(\omega) e^{i\omega t}d\omega \tag{3}
\end{eqnarray}
}

ところで、フーリエ変換の性質には次のような関係がある。
\displaystyle{ F(\omega + a) = F(\omega)e^{-iat} }
これを用いると、


\displaystyle{
\begin{eqnarray}
\frac{1}{\sqrt{2\pi}} \int_{-2(f + W)}^{-2\pi f} F(\omega) e^{i\omega t}d\omega 
&=&\frac{1}{\sqrt{2\pi}} \int_{-2 \pi W}^{0} F(\omega - 2\pi f) e^{i(\omega - 2\pi f)t}d\omega \\
&=&\frac{1}{\sqrt{2\pi}} e^{i 2\pi f} e^{-i 2\pi f} \int_{-2 \pi W}^{0}  F(\omega) e^{i\omega t}d\omega \\
&=&\frac{1}{\sqrt{2\pi}} \int_{-2 \pi W}^{0}  F(\omega) e^{i\omega t}d\omega \\
\\
\frac{1}{\sqrt{2\pi}} \int_{2\pi f}^{2\pi (f+W)} F(\omega) e^{i\omega t}d\omega
&=&\frac{1}{\sqrt{2\pi}} \int_{0}^{2\pi W} F(\omega + 2\pi f) e^{i(\omega + 2\pi f)t}d\omega \\
&=&\frac{1}{\sqrt{2\pi}} e^{-i 2\pi f} e^{i 2\pi f} \int_{0}^{2\pi W} F(\omega) e^{i\omega t}d\omega \\
&=&\frac{1}{\sqrt{2\pi}} \int_{0}^{2\pi W} F(\omega) e^{i\omega t}d\omega
\end{eqnarray}
}

途中式で、\omegaの変数変換も行っている。以上より、式(3)は、


\displaystyle{
\begin{eqnarray}
f(t) &=&\frac{1}{\sqrt{2\pi}} \int_{-2\pi W}^{2\pi W} F(\omega) e^{i\omega t}d\omega \tag{4}
\end{eqnarray}
}

　式(4)は、信号f(t)が、0[Hz]からW[Hz]に帯域制限されているときのF(\omega)のフーリエ逆変換の結果に他ならない。すなわち、「真のサンプリング定理」の証明はこれ以降、「よく見られるサンプリング定理」と全く同じ議論で行うことができる。

3.参考文献

  1. 甘利俊一(2011)『情報理論』ちくま学芸文庫↩

  2. Shannon, C. E. (1949). Communication in the presence of noise. Proceedings of the IRE, 37(1), 10-21.↩

Raspbian busterを32GBより大きい容量のmicroSD(SDXC)にインストールする手順

勉強メモ Linux RasberryPi

1.SDカードのフォーマット

公式サイトに従ってSDカードをフォーマットする。
1.1.Ridgecrop Consultants Ltdをインストール
1.2.以下の設定でstartを押す。
f:id:moratoriumer:20200421153708p:plain

2.imgファイルのダウンロードとインストール

2.1.国内のコピーサイトからイメージファイルをダウンロードした。2020-02-14のzipをダウンロードし解凍した。

2.2.公式サイトで推奨されていたbalenaEtcherをダウンロードし、実行した。2.1.でダウンロードし解凍したイメージファイルを選択しSDカードにインストールした。
実行完了後、以下のように1 Failed deviceと出るが、問題ないらしい。
f:id:moratoriumer:20200421161031p:plain

VirtualBoxでのCentOS7インターネット接続メモ

プログラミング Linux

1.環境

ホストOS : Windows 10 Home
ホストOS version : 10.0.18363
VIrutualBox version: 6.1.0.r135406
ゲストOS: CentOS 7.7.1908

2.VirutualBox内での設定

以下の書籍のChapter2を参考。
gihyo.jp
[設定]→[ネットワーク]
[割り当て]をブリッジアダプターに選択。
[名前]をホストOSがインターネット接続に利用しているアダプタ名にする。

※ホストOSがインターネット接続に利用しているアダプタ名の特定方法
[コントロールパネル]→[ネットワークとインターネット]→[ネットワーク接続]
アイコンの3行目にアダプタ名が表記されている。

3.CentOSでの設定

ネットワークインターフェースを探して、ifupコマンドで有効にする必要がある。



# ls /etc/sysconfig/network-scripts/ifcfg-*

/etc/sysconfig/network-scripts/ifcfg-enp0s3  /etc/sysconfig/network-scripts/ifcfg-lo

# ifup enp0s3

#ping google.com
ping google.comで応答が帰ってくることを確認できたら成功。

mod逆元を用いたCombination計算の証明

プログラミング 勉強メモ 数学

1. 用いる道具

1-1. モジュラ逆元

定義
モジュラ逆元xとは、
\ a,\ m \in \bf Zについて、ax \equiv 1(mod \ m)を満たす整数xであり
a^{-1} \equiv x(mod\ m)
と表記する。

1-2. フェルマーの小定理

条件
a\in \bf Z , \ p \in prime\ number
aとpは互いに素 \Leftrightarrow a\not \equiv0(mod \ p)
フェルマーの小定理
a^p \equiv 1 (mod \ p)
補題
フェルマーの小定理より、
a^{p-1}a \equiv 1 (mod \ p)
a^{-1} \equiv a^{p-1}

2. Combinationの余り

{}_n C_k = \frac{n!}{k!(n-k)!}\\ \Leftrightarrow k!(n-k)!{}_nC_k = n!\\
この式について p\in \bf Zを法とした合同式を書くと、
k!(n-k)!{}_nC_k \equiv n!\\ \Leftrightarrow ((k!)^{-1}k!)(n-k)!{}_nC_k \equiv n! (k!)^{-1}\\ \Leftrightarrow (n-k)!{}_nC_k \equiv n! (k!)^{-1}\\ \Leftrightarrow {}_nC_k \equiv n! (k!)^{-1}((n-k)!)^{-1}
合同式の積の結合法則を用いた。ここで、pが素数のとき、上述した補題から
(k!)^{-1} \equiv (k!)^{p-2}
((n-k)!)^{-1} \equiv ((n-k)!)^{p-2}
を代入すると、

{}_nC_k \equiv n!(k!)^{p-2}((n-k)!)^{p-2} (mod\ p)
Permutationについても、同様にして、

{}_nP_k \equiv n!(k!)^{p-2}(mod\ p)

共に、n!までのpを法とする剰余を求めれば良いのでO(n)で計算可能。
10^9 + 7 \in prime\ numberなので、
p = 10^9 + 7, 入力nについてn < pの時はこの計算が可能。

じゃんけんに2分探索の発想を取り入れてあいこをなくしたいという話

その他

以下の動画を見ていたらあいこを極限まで減らせる方法を思いついたので紹介したい。

www.youtube.com

ルール

グーとパーで2手に別れるアレをやる→少人数だった側が勝ち抜け。引き分けならパーを出した人たちの勝ち。
これを1人勝ちまたは2人になるまで続ける。
1人になった場合その人の勝ち。
2人になったら普通にじゃんけんして決着をつける。
以上

これだと人数N人に対してO(logN)回程度の勝負で決着がつきます。最悪でも、2人の最終じゃんけん対決まではN-2回やれば到達出来るのでN>=3において普通のじゃんけんより高速に終わりえます。また、少人数が勝ち抜けなので自分と同じ手を出そうと味方を作って呼びかけるような工作活動も暗に抑制できています。

肝であり怪しい部分があるのは引き分けならパーを出した人たちの勝ちってところです。引き分けなら再戦にすると自分が手を代えた場合大人数側に回ってしまうため膠着状態(将棋で言う千日手)になっていつまで立っても決着がつかない状態になります。
そのため引き分けならパーの勝ちという処理にしました。それにこれだとグーとパーどちらを出すかの読み合いが発生してゲーム的にもおもしろいかなと。ただ一方で読み合いをせずにランダムにグーとパーを出すとグーの方が勝ちやすいバイアスがかかっていることも事実です。

代替案としては人数が絞れて来て、上記のバイアスの影響が大きくなった頃からは、それぞれのチームの代表者がふつうにじゃんけんをしてチームの命運を決める。もしくは取り敢えずここで決着は決めずにわかれたチーム内でさらにグーとパーで別れる処理を行って最後に決勝を行うといった具合か。

そもそもこの境界条件を考えているうちに、普通にじゃんけんをしてあいこにわかれた時、もっとも少人数な手をだした人達が勝ち抜けでも良いのではとも思い始めた。こちらのほうが一度のじゃんけんでごっそり人数を減らせるし。

いずれにせよ2人対戦以外の時はあいこをなくして少人数勝ち抜きルールを提唱したい。
ただすぐ気づけば誰でも気づくこんな単純なことが流行っていないのはやはりあいこになったときのあのなんとも言えない緊迫感がじゃんけん勝負の醍醐味でもあるのかもしれない。そのようなことはどうでもよく、あいこで無駄な時間を過ごしたくないときなどはお試し頂きたい。

【人狼ジャッジメント】9人デフォルト村で初日狩人回避をした時の狼吊りの確率

人狼 その他

はじめに

人狼ジャッジメントができて1年経とうとしているが、デフォルトの9人村で未だに狩りCO周り(特に初日の狩人回避貫通について)の進行が完成されていないなとい印象を受ける。できるだけ最適な進行をやりたいマンの私としてはそろそろこの問題を真面目に考えて解決するべきではと思い始めた。
そこで、まずは初日狩人COしたときの狼吊りの確率はどのくらいだろうとググッてみた。が、以外な事に確率を求めて議論しているブログが1つもないではないか。
そこでそもそもの前提として、狩人回避進行を初日行うことで、どのくらいの確率で初日に狼を吊ることができるのかを各グレー数に応じて求めた。

ルール

レギュレーション

配役:占1、霊1、狩1、村3、狂1、狼2
初日占い:初日ランダム白
役職欠け:なし
狩人の連続護衛:あり

議論する上での仮定(重要)

初日に占い師COと霊能社者COを行う。占い師候補は2人現れるとする。
偽占い師は狂人のみとする。
真狩人が狩COしても狼が対抗狩COを行わないとする。

各グレー数において、狩人回避進行を行った場合の狼の初日吊り確率

まずは、グレー数が4、5、6人の全ての場合において狩人回避進行をとった場合、貫通進行に比べて、どの程度狼を初日に吊ることができるかの確率を求めた。

グレー4人の場合

初日の盤面
占いCO
①ｰ>④白
②ｰ>⑤白
霊能CO
③
グレー
⑥⑦⑧⑨

真占いはランダム白なので、霊狂狩村村村の6通り。
狂人は狼にも白を出せるので霊狂狩村村村狼狼の8通り。

各占い先の実現確率
村村→ 3/6 \times 3/8 - 3/6 \times 1/8= 6/48
村狩→ {3/6 \times 1/8 + 1/6 \times 3/8= 6/48}
村狼→ {3/6 \times 2/8 = 6/48}
狩狼→ {1/6 \times 2/8 = 2/48}
よってグレー4人になる確率は
{6/48 + 6/48 + 6/48 + 2/48 = 5/12}

狩人回避にした場合の狼吊りの確率

各占い先に対する狼指定確率
村村→ {2/3}
村狩→ {2/4}
村狼→ {1/3}
狩狼→ {1/4}
以上より、グレー4人の時の狩人回避による狼吊りの確率は
{(6/48 \times 2/3 + 6/48 \times 2/4 + 6/48 \times 1/3 + 2/48 \times 1/4) \div 5/12= \bf{47.5\%}}

狩人貫通にした場合の狼吊りの確率

占い先に対する狼指定確率
村村→ {2/4 = 50\%}
村狩→ {2/4 = 50\%}
狩村→ {2/4 = 50\%}
村狼→ {1/4 = 25\%}
狩狼→ {1/4 = 25\%}
より
{(6/48 \times 2/4 + 6/48 \times 2/4 + 6/48 \times 1/4 + 2/48 \times 1/4) \div 5/12= \bf{40\%}}

グレー5人(確定白ができた)の場合

初日の盤面
占いCO
①ｰ>④白
②ｰ>④白
霊能CO
③
グレー
⑤⑥⑦⑧⑨

そもそも良く誤解されているが、初日確定白ができたパターンのグレー5と、そうでない場合(片白しかできない場合)のグレー5は本質的に全然違う。前者は100%グレーに狼が2匹いる一方、後者は片白が狼である場合もある。つまり、前者と後者とでは初日狼吊りの確率が変わるからだ。
そのため「グレー5」ではなく、「確定白のグレー5」と「片白のグレー5」のように呼び分けをするべきだ。そしてグレー4で回避派のみなさんは確定白のグレー5の時も必ず回避進行を取らなければならないことをここで示そう。

各占い先の実現確率
村→ 3/6 \times 1/8 = 3/48
狩→ 1/6 \times 1/8 = 1/48
よって確定白のグレー4人になる確率は
{6/48 + 6/48 + 6/48 + 2/48 = 5/12}

狩人回避にした場合の狼吊りの確率

各占い先に対する狼指定確率
村→ 2/4
狩→ 2/5

以上より、確定白のグレー5人の時の狩人回避による狼吊りの確率は
{(3/48 \times 2/4 + 1/48 \times 2/5) \div 5/12= \bf{47.5\%}}

狩人貫通にした場合の狼吊りの確率

各占い先に対する狼指定確率
村→ 2/5
狩→ 2/5 = 40 \%

より
{(3/48 \times 2/5 + 1/48 \times 2/5) \div 5/12= \bf{40\%}}


おどろくべきことに、確定白のグレー5の時の初日狼吊りの確率は、グレー4の時と狩人回避進行、貫通進行ともに全く同じなのだ。
このことから、グレー5という呼び方はやめて、「確定白のグレー5」と「片白のグレー5」と呼び分けるべきだと思い始めただろう。そして、グレー4では回避進行派のみなさんは確定白のグレー5でも回避をしなければならないこともお分かりいただけただろう。

グレー5人(狂、霊占い)の場合

初日の盤面
占いCO
①ｰ>③白 または、 ①ｰ>②白
②ｰ>④白
霊能CO
③
グレー
⑤⑥⑦⑧⑨

各占い先の実現確率
狂村、霊村→ 2/6 \times 3/8 + 3/6 \times 2/8= 12/48
狂狩、霊狩→ {2/6 \times 1/8 + 1/6 \times 2/8= 4/48}
狂狼、霊狼→ {2/6 \times 2/8 = 4/48}
※かんたんのため、狂人が対抗占い師に白出しをした場合も「狂」を占ったとここでは表記している。

よって片白のグレー5人になる確率は
{12/48 + 4/48 + 4/48 = 5/12}

狩人回避にした場合の狼吊りの確率

各占い先に対する狼指定確率

狂村、霊村→ 2/4
狂狩、霊狩→ {2/5}
狂狼、霊狼→ {1/4}

以上より、グレー5人の時の狩人回避による狼吊りの確率は
{(12/48 \times 2/4 + 4/48 \times 2/5 + 4/48 \times 1/4) \div 5/12= \bf{43\%}}

狩人貫通にした場合の狼吊りの確率

各占い先に対する狼指定確率
狂村、霊村→ 2/5
狂狩、霊狩→ {2/5}
狂狼、霊狼→ {1/5}

より
{(12/48 \times 2/5 + 4/48 \times 2/5 + 4/48 \times 1/5) \div 5/12= \bf{36\%}}


グレー6人の場合

初日の盤面
占いCO
①ｰ>③白
②ｰ>③白
霊能CO
③
グレー
④⑤⑥⑦⑧⑨

各占い先の実現確率
狂霊→ 2/6 \times 3/8 + 3/6 \times 2/8= 12/48

狩人回避にした場合の狼吊りの確率

{2/5 = \bf{40\%}}

狩人回避にした場合の狼吊りの確率

{2/6 = \bf{33.3\%}}

まとめ

狼の初日吊り確率

グレー数\進行 回避 貫通
グレー4 47.5% 40%
グレー5(確白) 47.5% 40%
グレー5(片白) 43% 36%
グレー6 40% 33.3%

議論

どのグレー数においてもだいたい7ポイントほど回避進行を行えば狼吊りの確率が増加するという結果になった。実際に確率を求めることでわかった大きなことは、初日狼吊りという観点からはグレー4の場合と確定白のグレー5の場合は同じ狼吊りの確率となることだった。
注意してほしいのは、本記事では初日の狼吊り確率を求めただけであって、結局「回避と貫通どちらの進行にするべきか？」という問題の答えにはなっていない。つまり、LWまで吊り切る確率にまで踏み込めていない。

そこで次の記事(あれば)では、回避進行、あるいは貫通進行をとることで2日目以降の狼吊りにどのように影響するのかについて、考察していこうと思う。

エイト・クイーン問題を解く

競技プログラミング プログラミング

現在セール中で安くなっていたこともあり懐かしのレイトン教授のスマホゲームを暇つぶしにやっていた。

レイトン教授と不思議な町 EXHD for スマートフォン

レイトン教授と不思議な町 EXHD for スマートフォン

  • Level-5 Inc.
  • ゲーム
  • ¥960
play.google.com
すると、攻略後の裏ステージでエイト・クイーン問題が出題された。普通に試行錯誤していてもなかなか解けなかったことと、自分で実装したことがなかったこともあり、プログラムを組んで解を探すことにした。
エイト・クイーン - Wikipedia

解法

愚直に実装したら64マスにクイーンを8個おくので、{ \displaystyle {}_{64} \mathrm{ C }_8 = 4426165368 }
通り試せば良い。 計算量だと{\displaystyle \mathrm{O}(10^9)}になるのでまあできそう。

ただ、割と自明な必要条件として、各クイーンは同じ筋、または段に2個以上あってはならないことが言える。クイーンは将棋の飛車の動きもすることを使った条件だ。この条件を課すと、組み合わせとしては {\displaystyle 8! = 40320}通りになる。10万分の1の計算量になるのでこれだけの条件でも計算量がめちゃくちゃ小さくなることが分かる。

回転対称性等を利用すればもっと高速でできそうですが、計算量4分の1にしかならないのであまりやる気がしないです。

よって、方針としては、各筋におけるクイーンの配置方法全通りを挙げ、その配置方法が可能であるかどうかをチェックすることにした。

C++による実装
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool control_table[8][8];
int queen_rank[8] = {0, 1, 2, 3, 4, 5, 6, 7}; 

//解の描画
void draw_board(){
    cout << "a b c d e f g h" << endl;
    for(int file = 0; file < 8; file++){
        for(int rank = 0; rank < 8; rank++){
            if(queen_rank[file] == rank) cout << "q ";
            else cout << ". ";
        }
        cout << file + 1;
        cout << endl;
    }
}

void init_control_table(){
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            control_table[i][j] = true;
        }
    }
}

//queenをfile, rankにおいた時に生まれる利きの追加
void addQueen(int file, int rank){
    //縦の利き
    for(int tmp_file = 0; tmp_file < 8; tmp_file++){
        control_table[tmp_file][rank] = false;
    }
    //横の利き
    for(int tmp_rank = 0; tmp_rank < 8; tmp_rank++){
        control_table[file][tmp_rank] = false;
    }
    //斜めの利き
    for(int i = 0; i < 8; i++){
        if((file + rank - i >= 0) && (file + rank - i < 8)){
            control_table[file + (rank - i)][i] = false;
        }
        if((file - rank + i >= 0) && (file - rank + i < 8)){
            control_table[file - (rank - i)][i] = false;
        }
    }
}

int main(){
    int count = 0;
    do{
        bool flag = true;
        init_control_table();
        for(int i = 0; i < 8; i++){
            if(control_table[i][queen_rank[i]]){
                addQueen(i, queen_rank[i]);
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            count += 1;
            cout << "solution No." << count << endl;
            draw_board();
            cout << endl;
        }
    }while(next_permutation(queen_rank, queen_rank + 8));


}

出力結果例

solution No.91
a b c d e f g h
. . . . . . . q 1
. . q . . . . . 2
q . . . . . . . 3
. . . . . q . . 4
. q . . . . . . 5
. . . . q . . . 6
. . . . . . q . 7
. . . q . . . . 8

solution No.92
a b c d e f g h
. . . . . . . q 1
. . . q . . . . 2
q . . . . . . . 3
. . q . . . . . 4
. . . . . q . . 5
. q . . . . . . 6
. . . . . . q . 7
. . . . q . . . 8

解は全部で92個あることがわかりました。
ということで92番目の解をレイトン教授に提出したところ
f:id:moratoriumer:20190111141519p:plain
良かったです。