本文是記錄一些使用集合論語言，表達路徑(Path)/線段(Undirected Arc) 組成的關係: 令所有的路徑集為 $p \in P$，所有的線段集 $a \in A$ 路徑是由許多線段(無方向性)所組成的，自然存在對應關係 $E \subseteq P\times A$，可使用圖論二分圖描述 $G(P\cup A,E)$ 可以定義相依集：$$P_{a}:=\{p\in P : (p,a)\in E \},A_{p}:= \{a\in A :(p,a) \in E \}$$  並且滿足以下自然對偶邏輯(Natural Dual Correspondence) $$ \bigwedge_{(p,a)\in P\times A} \left( p \in P_a  \Longleftrightarrow a \in A_{p}  \right)   $$ 如果$X_a$為線段長，則很明顯路徑長可寫為 $$\bigwedge_{p \in P}\left( X_{p}:= X(A_p) = \sum_{a\in A_p} X_{a} \right)$$ 路徑長公式可以寫成線性系統　$$ X_{P} := M_{P\times A} X_{A} $$ (其中$X_P$,$X_{A}$ 為向量，$M_{P\times A}$ 為 $0-1$ adjacency sparse  matrix) 由線性系統可以求出反矩陣，而導出 $X_{A}= M^{-1}_{P\times A}X_{P} $) 定義 $p$ 損壞必定影響的路徑集 $$ \bigwedge_{p\in P}\left( P^{\cap}_{p}:= \bigcap_{a\in A_{p}} P_{a} \right) $$ 代表只要路徑 $p$ 斷了，則所有路徑 $p' \in P^{\cap}_{p}$ 也必定會斷，($p$是$p'$的一部分)  $$ \bigwedge_{p \in P}\bigwedge_{p' \in P^{\cap}_{p}} \left(A_{p} \subseteq A_{p'}\right)$$ 定義 $p$ 損壞可能影響的路徑集 ...

本文為分析電玩裡常見的期望值小問題: ================================================== 如果有 $n$ 個庫存物/道具。每使用 $1$ 次庫存物/道具時，有 $p \in [0,1]$ 的機率不會消耗這次使用，那麼平均而言總共可以使用幾次 ??  有多少扣達(quota) ?? (假設每次使用的機率機制相同，獨立同分布，Bernoulli 試驗) ================================================== 首先先定義隨機變數 $T$ ，代表總共只可以使用了 $T$ 次，而以 $t$ 表示隨機變數的"取值"，根據生活經驗很明顯 $t \in [n,\infty)_{\mathbb{Z}} = \{n,n+1,n+2,.....\}$  定義當 $T = t$ (當隨機變數 $T$ 取值為 $t$) 的機率為 $$ P_t := Pr(T=t)  $$ 則本文目標為計算期望值: $$ E[T] =  (\text{可能次數} \times \text{對應的機率}) \text{的總和} $$ $$ = \sum_{t \in [n,\infty)_{\mathbb{Z}}} t \cdot Pr(T=t) = \sum^{\infty}_{t = n} t \cdot P_{t} = \underbrace{ \lim_{N \rightarrow \infty} \left(\sum^{N}_{t = n} t \cdot P_{t}\right) }_{\text{嚴謹寫法}}$$ 而機率計算如下: $$ P_{t}= \overbrace{\left[ \underset{\text{不盡相異物直線排列數}}{\left( \begin{array}{c} t-1 \\ n-1 \\ \end{array} \right)} p^{t-n} (1-p)^{n-1} \right]}^{\text{前 $t-1$ 次，共消耗了 $n-1$ 個道具，得到了$t-n$ 次再使用機會}} \cdot \overbrace{(1-p)}^{\text{最後 1 次 消耗了...

本文為紀錄簡易博弈模型，若滿足有交集則彩金"疊加性"，則傳統期望值可推廣到非互斥事件上。 給定 開獎結果(樣本空間) $\Omega$ ，投注項目集 $B$ ， 投注項目 $b$所對應的開獎結果集 $\Omega_{b}$ $$ \bigwedge_{b \in B}\left(\Omega_{b} \subset \Omega\right)$$ 以及定義 $\Omega_{b}$補集: $$\displaystyle{\bigwedge_{b \in B} \left( \bar{\Omega}_{b}:= \Omega \setminus \Omega_{b} \right) }$$ 機率公設與 $\Omega_{b}$ 定義計算如下: $$\displaystyle{ \sum_{\omega \in \Omega} P(\omega) = 1} $$ $$\displaystyle{\bigwedge_{b \in B} \left( P(\Omega_{b}) := \sum_{\omega \in \Omega_{b}} P(\omega) \right)} $$ 描述文氏圖互斥分割集概念如下: $$\displaystyle{\Omega = \bigcup^{\text{disjoint}}_{S \subseteq B} \left(\bigcap_{b \in S}\Omega_{b} \cap \bigcap_{b \in B\setminus S} \bar{\Omega}_{b}\right)  }$$ 開獎機制如下: 假定 開獎結果 $\omega$，投注$b$ 項目中獎可獲得彩金 $c^{bingo}_{b}$ 元，槓龜獲得彩金 $c^{turtle}_{b}$ 元 $$\displaystyle{\bigwedge_{(b,\omega) \in B\times \Omega}\left\{\begin{array}{l}\omega \in \Omega_{b} \Longleftrightarrow \text{得到 } c^{bingo}_{b}\\ \omega \not\in \Omega_{b} \Longleftrightarrow  \text{...

本篇介紹一些筆者認為重要的整數規劃-圖形，邏輯建模技巧與概念，關於整數規劃的用途，可先參考之前這篇: http://discoverforgottenmath.blogspot.tw/2017/09/why-integer-programming-is-important-in.html 而建模技巧是把日常生活中的邏輯給正確的連結到方程式上!! 以下我們都把 $X \in \{0,1\}$ 視為  boolean 決策變數 ======================================= 刻劃出點 Node $i , j$ 跟邊 Arc $(i,j)$ 關係 ======================================= 定義: $X_{i} = 1  \text{ iff }  $ 我選擇了點 $i$ $X_{ij} = 1  \text{ iff }  $ 我選擇了邊 $(i,j)$ $$(E1) \quad \text{if  $(i,j)$ is selected  then ($i$ and $j$) are selected} $$ $$ \left\{\begin{array}{c} X_{(i,j)}\leq X_i \\ X_{(i,j)}\leq X_j \\ \end{array}\right.$$ $$(E2) \quad \text{if ($i$ and $j$) are selected then $(i,j)$ is selected } $$ $$ X_{i}+X_{j} \leq 1+X_{(i,j)} $$ $(E1)$ 是現實生活中自然的邏輯: 意涵代表，我選擇了這條邊 $(i,j)$ 則我自然會 cover $i , j$ 這兩個點 $(E2)$ 則不一定會有的邏輯，需思考 $(i,j)$ 的定義 例如:  我定義 $(i,j)$ 為直接從 $i$ 走到 $j$ 則走路徑 $(i \rightarrow j \rightarrow k \rightarrow w)$ 則 $X_{i}=1 , X_{w} =1 $ 但是 $X_{(i,w)} = 0$ ，...

本篇以隨筆平易近人的方式，寫一些如何降低演算法"計算量"的一些核心抽象概念。 [利用分配律尋找完全多分圖] 相信大家都知道加法$(+)$ ，乘法$(\times)$ 分配律的概念，複習一下 $$   (A+B)\times (C+D)   =A \times C + B \times C + A \times D + B \times D$$ 左式推廣我們可以寫成 $$ \underbrace{(A_1+A_2+....+A_{L_1})}_{\text{第一組}}\times  \underbrace{(B_1+B_2+....+B_{L_2})}_{\text{第二組}} \times ...  \times \underbrace{( ... )}_{\text{第 $m$ 組}}  $$ 每一組 有$L_{i}$ 個元素，總共有 $L$ 個元素(字母) 而且每一組有 $L_{i} -1$ 個加法，總共就有 $$\displaystyle{\sum^{m}_{i=1}(L_i - 1) =  L - m } \text{ 個加法} $$ 由於每一組中間穿叉乘法，有 $m-1$ 個乘法。我們分別把加法，乘法個數記做 ~ $\otimes $ , $ \oplus$，所以左式總共的運算數為 $$  \text{左式運算量 = } (m-1) \cdot \otimes  + (L-m) \cdot \oplus    $$ 右式完全展開，非常多項，要完整寫出來並非容易的事，但是我們知道它應該是長這樣 $$ (\text{第一組連乘}) + (\text{第二組連乘} ) + (\text{第三組連乘} ) + ........ $$ 至於究竟有幾組連乘呢 ?? 答案是 $\displaystyle{ \prod^{m}_{i=1}L_i }$ 組，而每一組中間穿叉 $L_i -1$ 乘法 右式總運算量為 $$ \text{右式運算量 = } (L-m)\cdot \otimes  + \displaystyle{ \pr...

本篇文章使用淺顯易懂集合論的語言，連接統計學現實與抽象化的過程，來重新詮釋統計學的概念，並區分一些差異與澄清一些觀念，希望能對初學統計的讀者有些幫助。 [定義有限母體] 日常生活中，母體的概念大家都能理解，很多很多個體。我們可以定義一個很大但有限的集合$\Omega$ ，每個獨一無二的個體記做 $s$ ，所以可以寫成 $s \in \Omega$ 而全部個數記做 $N$ (現實生活中$N$很大通常未知，除非我們有能力有時間消耗大量成本做普查才能得知 $N$) $$ |\Omega| = N  $$ [ex:] 例如全台灣人，兩千三百萬人左右，則可以寫成 $N \approx 2300 \times 10^4$ 而我們感興趣的可能是個體的可以量化的屬性(如:身高，成績)，所以可以定義一個實數函數(real-valued function) $$ X : \Omega \longrightarrow  \mathbb{R}  $$ [ex:] 例如阿元的月收入$\$$  可以寫成     $X(阿元) =  22 \times 10^3$  或是記做下標 $X_{阿元} = 22 \times 10^3$ ，而每個人的月收入有高有低，如果把那些"值"聯集起來，我們能說一定若在實數域裡面 !! [屬性值有哪些] 數學上來說就是 range of $X$ , image of $X$ $$ X(\Omega) := \{ X_s  \in \mathbb{R}: s\in \Omega \} = \bigcup_{s\in \Omega} \{ X_s\} \subset \mathbb{R} $$ 這時我們可以把薪水的值記做 $x \in X(\Omega)$ [計數與比例] 這時大家會好奇說有沒有其他人跟我一樣的薪水，還有那群人在全台灣人佔了多少比例，所以會計算個數 (Count) ，以及比例 (Frequency) 。 正是數學定義如下: $$  \text{Count}(x,\Omega) :=   |\{ s\in \Omega :  X_s = x  ...

本篇為筆者使用集合論符號，方便抽象推廣化到多維陣列。 ====================================== [符號提醒] 由於有些符號有點抽象，為了方便讀者了解，小寫大多為"元素"，大寫大多為"集合" $\prod$ 代表集合的 Catesian Product , $ \sum $ 代表連加，$| \cdot |$ 代表集合元素個數(Cardinality)，符號幾乎不會混用，並注意字母粗體的差別!! [定義論域] 首先定義下標符號集合 $i \in I$ , 而且給定多維離散結構有限集合 $$\mathcal{R}_{I}  \subseteq U_{I} $$ 其中 $U_{I}$ 為給定 $|I|$維座標宇集 $$ u_{I} \in U_{I} = \prod_{i\in I}U_i$$ , 正式定義如下 ====================================== [定義整體離散結構] $$ \mathcal{R}_{I} := \left\{ u_I = \underbrace{(u_i)_{i\in I}}_{|I|\text{dim - tuple}} \in U_{I} \left| u_i \in U_i  , \forall i \in I ,  u_{I} \text{ satisfies something ...} \right. \right \}$$ [ex1] 關於 $\mathcal{R}_{I}$ 與 depend sets 的例子可以參考這篇 https://discoverforgottenmath.blogspot.tw/2017/08/framework-of-creating-depend-sets-given.html 可以簡記 $u_{I} \in \mathcal{R}_{I}$ 對於每個 $i \in I$，可以把 $u_{I}$ 寫成 $(u_{i},u_{I-\{i\}} )$ , 也可以簡記為 $u_{I} = (u_{i},u_{-i} )$  (賽局理論表示法) ====================================== [收集出一維結構] 對...