12/27/2016

[隨機系統] 淺論賭博系統理論 (1)

考慮某賭博系統其報酬率定義為 i.i.d. 隨機變數,記作 $X(k)$  且具有分佈 $F_X$ 。現在定義 $V(k)$ 為在時刻 $k$ 之資產價值,且令 $K \in [0,1]$ 為投資比率,則時刻 $k$ 之投資策略可記作
\[
I(k) := K V(k)
\]且投資人資產動態模型可表為
\begin{align*}
  V(k + 1) &= V(k) + I(k)X(k) \hfill \\
   &= V(k) + KX(k)V(k) \hfill \\
   &= \left( {1 + KX(k)} \right)V(k) \hfill \\
\end{align*}

Definition: Growth Rate and Optimal Growth Rate
以投資比率 $K$ 為投資策略之資產成長率 (Growth Rate) 定義為
\[
g(K) := E[\log(1+K X(k))]
\]
另外我們接著定義 最佳成長率 (Optimal Growth Rate) 如下
\[
g^* := \max_K g(K)
\]且我們稱 $K^*$ 達到 $g^*$ 為 log-optimal feedback gain。


Comments:
上述問題的最簡形式(投擲單一銅板問題) 即為經典 凱利問題 (Kelly Optimization Problem) 且上述的最大化成長率又稱為凱利判准 (Kelly Criterion),有興趣讀者請參閱本部落格關於凱利問題的相關文章。


上述最佳成長率存在性由下列定理確保。

=================
Theorem:
令 $X(0),X(1),...X(N-1)$ 為 i.i.d. 報酬 且具有分佈 $F_X$,現在令
\[\frac{{{V^*}(N)}}{{V(0)}} = \prod\limits_{k = 0}^{N-1} {\left( {1 + {K^*}X(k)} \right)} \]則當 $N \to \infty$,我們有
\[\frac{1}{N}\log \frac{{{V^*}(N)}}{{V(0)}} \to {g^*}\]almost surely.
=================

Proof: 首先觀察
\begin{align*}
  \frac{1}{N}\log \frac{{{V^*}(N)}}{{V(0)}} &= \frac{1}{N}\log \prod\limits_{k = 0}^{N - 1} {\left( {1 + {K^*}X(k)} \right)}  \hfill \\
   &= \frac{1}{N}\sum\limits_{k = 0}^{N - 1} {\log \left( {1 + {K^*}X(k)} \right)}  \hfill \\
\end{align*}接著注意到因為  $\{X(0),X(1),...X(N-1)\}$ 為 i.i.d. 故
\[
\{1 + {K^*}X(1),  \;1 + {K^*}X(1),...,\; 1 + {K^*}X(N-1)\}
\]亦為 i.i.d. ,且注意到 $ E\left[ {\log \left( {1 + {K^*}X(0)} \right)} \right] = {g^*}$ 故 利用 強大數法則 (請參閱下方 FACT) 可得當 $n \to \infty$ 我們有
\[\frac{1}{N}\sum\limits_{k = 0}^{N - 1} {\log \left( {1 + {K^*}X(k)} \right)}  \to E\left[ {\log \left( {1 + {K^*}X(0)} \right)} \right] = {g^*}\]almost surely。即為所求。 $\square$


=================
FACT: 強大數法則 (Strong Law of Large Numbers): 若 $X(1),X(2)...$ 為 i.i.d. 隨機變數且 $E[X(0)] $ 存在 。現令 $S(N):=X(1)+X(2)+...+X(N)$ ,則當 $N \to \infty$ 我們有
\[
\frac{S(N)}{N} \to E[X(0)]
\]almost surely
=================
Proof: Omitted. see R. Durrett, Probability Theory and Examples,





12/24/2016

[凸分析] 一些常用的凸集性質(1) - 任意凸集之交集仍為凸集

=================
FACT 1: 兩凸集之交集仍為凸集
令 $C_1, C_2$ 為兩凸集,則 $C_1 \cap C_2$ 為凸集。
=================

Proof:
若 $C_1,C_2$ 任一者為空集合,亦即 $C_i = \emptyset, \;\;\; i=1 \text{ or } 2$ 則 $C_1 \cap C_2 = \emptyset$ 故為凸集。若 $C_1, C_2 \neq \emptyset$ ,我們可令 $x,y \in C_1 \cap C_2 $ 與 $\theta \in [0,1]$ 我們要證明
\[
\theta x + (1-\theta) y  \in C_1 \cap C_2
\]
注意到$x,y \in C_1 \cap C_2 $ 表示 $x,y \in C_1$ 且同時 $x,y \in C_2$,由於 $C_1, C_2$ 為凸集,故 $\theta x + (1-\theta) y   \in C_1$ 且 $\theta x + (1-\theta) y   \in C_2$ 亦即,
\[
\theta x + (1-\theta) y  \in C_1 \cap C_2
\]故此得證。$\square$

上述結果可推廣到任意交集,亦即

=================
Theorem: 對任意  $i \in \mathcal{I}$ , 令 $C_i$ 為凸集,則
\[
\bigcap_{i \in \mathcal{I}} C_i
\]亦為凸集。
=================
Proof: omitted (與前述 FACT 的證明雷同)



凸集合的用途非常廣泛,比如說在線性代數中最常被使用的空間為向量空間的子空間,此子空間即為凸集和。



=================
FACT 2: Subspace 為凸集
令 $V$ 為任意 vector space,令 $W \subset V$ 且 $W \neq \emptyset$ 為 subspace,則 $W$ 為 凸集。
=================

Proof:
令 $x,y \in W$ 與 $\theta \in [0,1]$,我們要證明
\[
\theta x + (1-\theta) y  \in W \;\;\;\;\; (*)
\]注意到 $x,y \in W$ 且 $W$ 為 subspace 故我們知道對任意 $a,b \in \mathbb{R}$
\[
a x + b y \in W
\]現在取 $ a := \theta \in [0,1]$ 且 $b := 1- \theta$ 則 $(*)$ 自動成立。故 subspace 為 凸集。 $\square$



不只如此,子空間自身的交集仍為子空間

=================
FACT 3: Subspaces 交集仍為 Subspace
令 $V$ 為向量空間,令 $W,U$ 為 $V$ 之子空間,則 $W \cap U$ 仍為子空間。
=================

Proof:
由於子空間必定包含零點,故 $W \cap U \neq \emptyset$,現在取 $x, y \in W \cap U$ 與 $a,b \in \mathbb{R}$,我們要證明
\[
a x + b y \in W \cap U
\]由於 $x, y \in W \cap U$ ,故 $x,y \in W$ 且 $y \in U$ 又因為 $W,U$ 為子空間,故 $ a x + b y \in W $ 且 $ a x + b y \in U $ 亦即,
\[a x + b y \in W \cap U \] 至此得證。$\square$


由 FACT 2 與 FACT 3 可立即推得以下引理:

=================
Corollary:
Subspaces 之交集仍為凸集。
=================



另外關於凸集之交集的另一個主要應用來自 由 歐式空間線性不等式 與 線性等式所成之集合,一般稱之為 Polyhedra ,記作 $P$, 我們亦可使用上述 FACT 來推論 $ P $為凸集。

=================
Example: 
回憶 Polyhedran 定義為 $\mathbb{R}^n$ 空間中的 線性不等式 與 線性等式 所成之集合,亦即
\[
P := \{x \in \mathbb{R}^n: \exists A,b,C,d \text{s.t.} Ax \leq b, \;\;\; Cx = d\}
\]此集合等價為
\[
P= \bigcap \{\text{half-spaces and hyperplane}\}
\]由於 half-space 與 hyperplane為凸集 (why?) 故 $P$ 亦為凸集。
=================








12/08/2016

[投資理論] Markowitz's Mean-Variance 投資組合理論的潛在缺點

Markowitz 在 1952年 提出利用 Mean (或稱 一階動差) 與 Variance  (或稱 二階動差)這兩種統計量來判別一組 投資組合(portfolio) 的績效表現,該理論要求某投資組合具有較高 期望報酬 或者 較低 報酬變異,此理論被廣泛應用在現代金融 與 投資學,又稱 現代投資組合理論 。此文主要討論此理論具備的一些潛在的缺失:以下我們先給出基本定義:



考慮兩投資組合 $\{P_1, P_2\}$ 且令 $\{E_1, \sigma_1^2\}; \;\;\; \{E_2, \sigma_2^2 \}$ 分別為投資組合 $P_1$ 與 $P_2$ 之期望報酬 與 報酬變異
============================
Definition: Domination of Portfolios :
假設投資組合 $P_1$ 比另一 投資組合 $P_2$ 具有較高的期望報酬 與 較低的變異 (亦即 $E_1 > E_2$ 且 $\sigma_1^2 < \sigma_2^2$),則我們稱 $P_1$ dominates $P_2$ 。

我們稱 $P_1$ 為 dominate $P_2$ in minimum variance sense 若 $\sigma_1 < \sigma_2$
同理,我們稱 $P_1$ 為 dominate $P_2$ in maximum expected return sense 若 $E_1 > E_2$
============================


令 $P$ 為一組投資組合,我們利用上述討論,可以進一步給出 efficient portfolio 定義。
============================
Definition: Efficient Portfolio
1. 若沒有其他 投資組合可以 dominates $P$,則我們稱 $P$為 (absolutely) efficient

2. 若沒有其他 投資組合 可以 dominate $P$ in minimum variance sense 則我們稱 $P$ 為 efficient in variance sense

3. 同理,若沒有其他 投資組合 可以 dominate $P$ in maximum expected return sense 則我們稱 $P$ 為 efficient in expected return sense
============================

Comments:
1. 上述嚴格不等式 $>$ 可以替換為 較弱的不等式 $\geq$。
2. 上述 三種 efficient 投資組合 (absolute efficient, efficient in variance sense, efficient in expected return sense ) 一般泛稱為 efficient,不多做區分。順帶一提,這一類的 efficient portfolio 會落在 所謂的 效率前緣 (efficient frontier ),有興趣讀者可參閱一般投資學或者資產配置理論的相關書籍,在此不多做贅述。



Markowitz' Mean-Variance 理論的潛在缺失:
以下我們討論上述 Mean-Variance 理論的潛在缺失:我們同樣使用前述的設定:考慮兩投資組合 $\{P_1, P_2\}$ 且令 $
\{E_1, \sigma_1^2\}; \;\;\; \{E_2, \sigma_2^2 \}
$ 分別為投資組合 $P_1$ 與 $P_2$ 之 期望報酬 與 報酬變異

現假設 $E_1 < E_2$ 且 $\sigma_1^2 < \sigma_2^2$,則上述 Markowitz 理論並無法決定到底 $P_1$ 好 還是 $P_2$ 好。或者說 Markowitz 理論無法告知到底是 $P_1$ 或者 $P_2$ 較為 efficient。以下我們給出一個更具體的例子說明此一論點。

Example
考慮三組 彼此獨立隨機變數 $r_1 \sim U[1,3]$, $r_2 \sim U[10, 100]$ ,且 $r_3 = 0$ almost surely,分別表示三種資產的報酬,我們現在對其建構投資組合如下:令 $K_1,K_2,K_3$  分別為 $r_1,r_2, r_3$之權重 滿足 $K_i \geq 0$ 且 $\sum_{i}^3 K_i = 1$,則投資組合 (記作 $P$ ) 之報酬 (記作 $r_p$)可表為
\[
r_p := K_1 r_1 + K_2 r_2 + K_3 r_3
\]則我們可計算上述投資組合的期望資產
\begin{align*}
  \mathbb{E}\left[ {\sum\limits_{i = 1}^3 {{K_i}{r_i}} } \right] &= \sum\limits_{i = 1}^3 {{K_i}\mathbb{E}\left[ {{r_i}} \right]}  \hfill \\
   &= {K_1} \cdot 2 + {K_2} \cdot 55 + {K_3} \cdot 0 \hfill \\
   &= 2{K_1} + 55{K_2} \hfill \\
\end{align*} 且對應的報酬變異為
\begin{align*}
  Var\left[ {\sum\limits_{i = 1}^3 {{K_i}{r_i}} } \right] &= \sum\limits_{i = 1}^3 {{K_i}Var\left[ {{r_i}} \right]}  \hfill \\
  & = {K_1} \cdot \frac{1}{{12}}{\left( {3 - 1} \right)^2} + {K_2} \cdot \frac{1}{{12}}{\left( {100 - 10} \right)^2} + {K_3} \cdot 0 \hfill \\
   & = \frac{1}{3}{K_1} + 675{K_2} \hfill \\
\end{align*}
但是注意到若取 $K_3 :=1, (K_1 = K_2 = 0)$ 則我們可得 efficient portfolio (in variance sense) :因為此投資組合具有零變異。

另一方面,若取 $K_2 :=1, (K_1 = K_3 = 0)$,則我們亦得到另一組 efficient portfolio (in expected return sense):因為此投資組合具有最大正期望值。


Comments
事實上,由前述 Markowitz 理論的定義,那麼我們可以找出無窮多種  efficient portfolio,但 Markowitz 的理論並無法提供更進一步資訊來告訴我們何者才是真正最好的 投資組合。在經濟學中或一般金融工程領域,會建議投資人採用 效用函數 (utility function) 作為新的判準,來做最佳化投資組合的績效,比如說我們可定義效用函數 $U(x) := a x + \frac{1}{2}b x^2 $ 滿足 $a>0, b\geq 0$ ,則我們可以考慮 最佳化問題 如下
\[
\max_{K} \mathbb{E}[U(r_p)]
\] 有興趣讀者可參閱 相關文獻 或者 本 Blog 相關文章,在此不再贅述。



[最佳化] C^2 函數一階逼近的餘項積分表示

令 $f: \mathbb{R}^m \to \mathbb{R}$ 為 $C^2$-函數。對 $f$ 在 $y$ 附近使用一階泰勒展開: \[ T_y(x) := f(y) + \nabla f(y)^\top (x - y) \] 則其餘項 $R(x,y)$ 訂為 $$R(...