1、馬爾科夫決策課件 一、基本概念 1.隨機變量 、 隨機函數與隨機過程 一變量x，能隨機地取數據（但不能準確地預言它取何值），而對于每一個數值或某一個范圍內的值有一定的概率，那么稱x為隨機變量。 假定隨機變量的可能值xi發生概率為Pi 即P(x = xi) = Pi 對于xi的所有n個可能值，有離散型隨機變量分布 列： Pi = 1 對于連續型隨機變量，有 P(x)dx = 1 馬爾科夫決策課件 在試驗過程中，隨機變量可能隨某一參數（不一定是時間）的變化而變化. 如測量大氣中空氣溫度變化x = x(h),隨高度變化。這種隨參變量而變化的隨機變量稱為隨機函數。而以時間t作參變量的隨機函數稱為隨機過

2、程。 也就是說：隨機過程是這樣一個函數，在每次試驗結果中，它以一定的概率取某一個確定的，但預先未知的時間函數。 馬爾科夫決策課件 2、馬爾科夫過程 隨機過程中，有一類具有“無后效性性質”，即當隨機過程在某一時刻to所處的狀態已知的條件下，過程在時刻tto時所處的狀態只和to時刻有關，而與to以前的狀態無關，則這種隨機過程稱為馬爾科夫過程。 即是：ito為確知,it(tto)只與ito有關，這種性質為無后效性，又叫馬爾科夫假設。 馬爾科夫決策課件 3、馬爾科夫鏈 時間和狀態都是離散的馬爾科夫過程稱為馬爾科夫鏈。例：蛙跳問題 假定池中有N張荷葉，編號為1，2，3,N，即蛙跳可能有N個狀態（狀態確知

3、且離散）。青蛙所屬荷葉，為它目前所處的狀態；因此它未來的狀態，只與現在所處狀態有關，而與以前的狀態無關（無后效性成立） 馬爾科夫決策課件 寫成數學表達式為： P( xt+1 = j | xt = it , xt-1 = it1,x1 = i1) =P( xt+1 = j | xt = it ) 定義：Pij = P( xt+1 = j | xt = i) 即在xt = i的條件下，使 xt+1 = j的條件概率，是從 i狀態一步轉移到j狀態的概率，因此它又稱一步狀態轉移概率。 由狀態轉移圖，由于共有N個狀態，所以有 馬爾科夫決策課件1234P33P22P44P41P42P31P32馬爾科夫決策

4、課件 二狀態轉移矩陣 1.一步狀態轉移矩陣 系統有N個狀態，描述各種狀態下向其他狀態轉移的概率矩陣 P11 P12 P1N 定義為 P21 P22 P2N : : : PN1 PN2 PNN 這是一個N階方陣，滿足概率矩陣性質 1） Pij 0,i,j = 1,2, , N 非負性性質 2） Pij = 1 行元素和為1 ,i=1,2,NNN P =馬爾科夫決策課件 如： W1 = 1/4, 1/4, 1/2, 0 W2 = 1/3, 0, 2/3 W3 = 1/4, 1/4, 1/4, 1/2 W4 = 1/3, 1/3, -1/3,0, 2/3 3）若A和B分別為概率矩陣時，則AB為概率矩

5、陣。 概率向量非概率向量馬爾科夫決策課件 2.穩定性假設 若系統的一步狀態轉移概率不隨時間變化，即轉移矩陣在各個時刻都相同，稱該系統是穩定的。 這個假設稱為穩定性假設。蛙跳問題屬于此類，后面的討論均假定滿足穩定性條件。 馬爾科夫決策課件 3.k步狀態轉移矩陣 經過k步轉移由狀態i轉移到狀態j的概率記為 P(xt+k =j | xt = i) = Pij(k) i,j = 1,2, , N 定義：k步狀態轉移矩陣為： P11(k) P12(k) P1N(k) P = : : : PN1(k) PN2(k) PNN (k) 當系統滿足穩定性假設時 P = P = P P P 其中P為一步狀態轉移矩

6、陣。 即當系統滿足穩定性假設時，k步狀態轉移矩陣為一步狀態轉移矩陣的k次方.kk k馬爾科夫決策課件 例：設系統狀態為N = 3，求從狀態1轉移到狀態2的 二步狀態轉移概率. 解：作狀態轉移圖 解法一：由狀態轉移圖： 1 1 2: P11 P12 1 2 2: P12 P22 1 3 2: P13 P32 P12 = P11 P12 + P12 P22 +P13 P32 = P1i Pi2 132P13P32 P11P12P12P22馬爾科夫決策課件 解法二： k = 2, N = 3 P11(2) P12 (2) P13(2) P = P21(2) P22 (2) P23(2) P31(2)

7、 P32(2) P33(2) P11 P12 P13 P11 P12 P13 = PP = P21 P22 P23 P21 P22 P23 P31 P32 P33 P31 P32 P33 得： P12(2) = P11 P12 + P12 P22 +P13 P32 = P1i Pi2 馬爾科夫決策課件 例：味精銷售問題 已連續統計六年共24個季度，確定暢銷，滯銷界限，即只允許出現兩種狀態，且具備無后效性。 設狀態1為暢銷，狀態2為滯銷,作出狀態轉移圖: 圖中: P11為當前暢銷，連續暢銷概率； P12為當前暢銷，轉滯銷概率； P22為當前滯銷，連續滯銷概率； P21為當前滯銷，轉暢銷概率。 1

8、2P22P11P12P21馬爾科夫決策課件數據在確定盈虧量化界限后的統計表如下： t 1 2 3 4 5 6 7 8 9 10 11 12 13狀態 t 14 15 16 17 18 19 20 21 22 23 24狀態 進行概率計算時，第二十四個季度為暢銷，但后續是什么狀態不知，故計算時不能采用，只用于第二十三季度統計。有： P11 = 7/(7 + 7) = 0.5; P12 = 7/(7 + 7) = 0.5; P21 = 7/(7 + 2) = 0.78; P22 = 2/(7 + 2) = 0.22則 0.5 0.5 0.78 0.22此式說明了：若本季度暢銷，則下季度暢銷和滯銷的

9、可能性各占一半 若本季度滯銷，則下季度滯銷有78%的把握，滯銷風險22% P =馬爾科夫決策課件 二步狀態轉移矩陣為： 0.5 0.5 0.5 0.5 0.78 0.22 0.78 0.22 0.64 0.36 0.5616 0.4384 P11(2) P11(2) P11(2) P11(2) =P = P =22馬爾科夫決策課件 三.穩態概率： 用于解決長期趨勢預測問題。 即：當轉移步數的不斷增加時，轉移概率矩陣 P 的變化趨勢。 1.正規概率矩陣。 定義：若一個概率矩陣P，存在著某一個正整數m,使P 的所有元素均為正數（Pij o），則該矩陣稱為正規概率矩陣 k馬爾科夫決策課件例： 1/2

10、 1/4 1/4 P = 1/3 1/3 1/3 為正規概率矩陣 2/5 1/5 2/5 0 1 P11 = 0 1/2 1/2 但當 m = 2， 有 有Pij 0它也是正規概率矩陣。（P 每個元素均為正數） 但 1 0 0 1 就找不到一個正數m,使P 的每一個元素均大于0，所以它不是正規概率矩陣。 P =22 P =m P =2馬爾科夫決策課件 2.固定概率向量（特征概率向量） 設 P為NN概率矩陣,若U = U1, U2, UN為概率向量,且滿足UP = U,稱U為P的固定概率向量 例 0 1 1/2 1/2 為概率矩陣 P的固定概率向量 U = 1/3 , 2/3 檢驗 UP = 1

11、/3 2/3 0 1 1/2 1/2 =1/3 2/3P = 馬爾科夫決策課件 3.正規概率矩陣的性質 定理一 設P為NXN正規概率矩陣，則 A .P有且只有一個固定概率向量 U = U1,U2, UN 且U的所有元素均為正數 Ui 0 B.NXN方陣P的各次方組成序列 P, P, P, ,P 趨于方陣T，且T的每一個行向量都是固定概率向量U。 即 U1 U2 UN U lim Pk = T = : : : = : U1 U2 UN U 這個方陣T稱穩態概率矩陣。23k馬爾科夫決策課件 這個定理說明：無論系統現在處于何種狀態，在經過足夠多的狀態轉移之后，均達到一個穩態。 因此，欲求長期轉移概率

12、矩陣，即進行長期狀態預測，只要求出穩態概率矩陣T； 而T的每個行向量都是固定概率向量，所以只須求出固定概率向量U就行了 !馬爾科夫決策課件 定理二：設X為任意概率向量，則XT = U 即任意概率向量與穩態概率矩陣之點積為固定概率向量。 事實上： U1 U2 UN XT = X : : : = U1Xi U1Xi U1Xi U1 U2 UN = U1 U2 UN = U馬爾科夫決策課件例：若 0.4 0.3 0.3 P = 0.6 0.3 0.1 求T 0.6 0.1 0.3 解：設 U = U1 U2 U3 = U1 U2 1U1U2 由 UP = U 有 0.4 0.3 0.3U1 U2 1

13、U1U2 0.6 0.3 0.1 = U1 U2 U3 0.6 0.1 0.3 馬爾科夫決策課件即 -0.2U1 + 0.6 = U1 U1 = 0.5 0.2U1 + 0.2U2 + 0.1 =U2 U2 = 0.25 -0.2U2 + 0.3 = U3 U3 = 0.25 U = 0.5 0.25 0.25 則 0.5 0.25 0.25 T = 0.5 0.25 0.25 0.5 0.25 0.25 說明： 不管系統的初始狀態如何，當系統運行時間較長時，轉移到各個狀態的概率都相等。（列向量各元素相等）即 各狀態轉移到1狀態都為0.5; 2狀態都為0.25 ; 3狀態都為0.25馬爾科夫決

14、策課件 商品在市場上參與競爭，都擁有顧客，并由此而產生銷售，事實上，同一商品在某一地區所有的N個商家（或不同品牌的N個同類產品）都擁有各自的顧客，產生各自銷售額，于是產生了市場占有率定義：設某一確定市場某商品有N個不同品牌（或N個商家）投入銷售，第i個商家在第j期的市場占有率 Si(j) = xi(j)/x i =1,2, N 其中 xi(j)為第i個商家在第j期的銷售額（或擁有顧客數） x為同類產品在市場上總銷售額（或顧客數）市場占有率所需數據可通過顧客抽樣調查得到。 馬爾科夫決策課件 一般地,首先考慮初始條件,設當前狀態（即j = 0 ） 為 S(0) = S1(0) S2(0) SN(0

15、)第i個商家 Si(0) = xi(0)/x xi(0) = Si(0) x即當前第i個商家市場占有率與初始市場占有率及市場總量有關.同時假定滿足無后效性及穩定性假設.由于銷售商品的流通性質,有第i個商家第j期銷售狀況為馬爾科夫決策課件 xi(k) = x1(0)P1i(k) + x2(0)P2i(k)+ + xN(0)PNi(k) = xS1(0)P1i(k) +xS2(0)P2i(k) + + xSN(0)PNi(k) P1i(k) = xS1(0) S2(0) SN(0) P2i(k) : PNi(k) 有：Si(k) = xi(k)/x P1i(k) = S1(0) S2(0) SN(

16、0) P2i(k) : PNi(k)馬爾科夫決策課件故可用矩陣式表達所有狀態: S1(k),S2(k), ,SN(k)= S1(0),S2(0), ,SN(0) P即 S(k) = S(0) P 當滿足穩定性假設時,有 S(k) = S(0) P 這個公式稱為已知初始狀態條件下的市場占有率k步預測模型. kkk馬爾科夫決策課件 例:東南亞各國味精市場占有率預測, 初期工作: a)行銷上海,日本,香港味精,確定狀態1,2,3. b)市場調查,求得目前狀況,即初始分布 c)調查流動狀況;上月轉本月情況,求出一步狀態轉移概率. 1)初始向量: 設 上海味精狀況為1; 日本味精狀況為2; 香港味精狀況

17、為3;有 S(0) = S1(0) S2(0) S3(0) = 0.4 0.3 0.3馬爾科夫決策課件2)確定一步狀態轉移矩陣 P11 P12 P13 0.4 0.3 0.3 P = P21 P22 P23 = 0.6 0.3 0.1 P31 P32 P33 0.6 0.1 0.33),3 步狀態轉移矩陣(假定要預測3個月后) P11(3) P12(3) P13(3) 0.496 0.252 0.252 P 3= P21(3) P22(3) P23(3) = P = 0.504 0.252 0.244 P31(3) P32(3) P33(3) 0.504 0.244 0.252 3馬爾科夫決策

18、課件4)預測三個月后市場 0.496 0.252 0.252 S(3) = S(0)P3 =0.4 0.3 0.3 0.504 0.252 0.244 0.504 0.244 0.252 S1(3) = 0.40.496 +0.30.504 + 0.30.504 = 0.5008 S2(3) = 0.2496 S3(3) = 0.2496 馬爾科夫決策課件 二.長期市場占有率預測 這是求當 k 時 S(k) ? 我們知道: S(k) = S(0) P lim S(k) = S(0) lim P = S(0)T = U 因此,在已知初始條件下求長期市場占有率就是求穩態概率矩陣,也是求固定概率向量

19、. 求固定概率向量的方法,我們在前一節已有例子,只不過說明了長期市場占有率也是只與穩態矩陣有關,與初始條件無關. kk馬爾科夫決策課件 上面味精例子, 0.4 0.3 0.3 已知 P = 0.6 0.3 0.1 0.6 0.1 0.4 0.5 0.25 0.25 求出 T = 0.5 0.25 0.25 = lim Pk 0.5 0.25 0.25 lim S(k) = 0.5 0.25 0.25 即中國味精可擁有50%的長期市場. 馬爾科夫決策課件 是考慮:一個與經濟有關隨機系統在進行狀態轉移時,利潤要發生相應變化,例如商品連續暢銷到滯銷,顯然在這些過程變化時,利潤變化的差距是很大的. 所

20、以有如下的定義: 若馬爾科夫鏈在發生狀態轉移時,伴隨利潤變化,稱這個馬爾科夫鏈為帶利潤的馬爾科夫鏈. 馬爾科夫決策課件 設系統有N個狀態 狀態i經過一步轉移到狀態j時(即當事件發生時,Pij = 1)所獲得的利潤為rij i,j = 1,2, N 于是有利潤矩陣 r11 r12 r1N R = r21 r22 r2n : : : rN1 rN2 rNN 顯然 ,rij 0 盈利 ;rij 0 虧損 ; rij = 0 平衡 由于系統狀態轉移為隨機的,得到的利潤也應當是隨機的,這個利潤只能是期望利潤. 馬爾科夫決策課件 11、即時期望利潤(一步狀態轉移期望利潤) 考慮狀態 i 狀態轉移 i 1

21、i 2 i i i N 一步轉移概率 Pi1 Pi2 Pii PiN 利潤變化 ri1 ri2 rii riN 所以:從i轉到1的期望利潤值 P11r11 從i轉到2的期望利潤值 P12r12 : : 從i轉到i的期望利潤值 Piirii : : 從i轉到N的期望利潤值 P1Nr1N馬爾科夫決策課件 而從狀態i開始經過一步轉移后所得到的期望利潤值為 Pijrij = Pi1ri1 + Pi2ri2 PiNriN 這個值稱為即時期望利潤,又是一步狀態轉移期望利潤,是概率定義下的利潤均值. 記為 Vi = Vi = Pijrij 特別地Vi = 0 ,即當 k = 0, 未轉移,沒有利潤變化. 1

22、0馬爾科夫決策課件 2. k步轉移期望利潤遞推公式 k步轉移期望利潤可以分解為兩步,即一步和k1步, 一步轉移期望利潤為Vi = Pijrij 現考慮k1步 首先,從0時刻到1時刻發生了一步狀態轉移,假定 狀態已轉移1狀態(令Pij = 1)后,從1狀態開始 k1 步轉移后達到期望利潤為V1k-1 . 而i狀態轉移到1狀態的發生概率為Pi1 , 因此i狀態先轉移到1狀態后的k1步實際期望利潤為 Pi1 V1k-1 k1馬爾科夫決策課件 同理 i狀態先轉到2狀態后的k1步實際期望利潤為 Pi2 V2 即:各實際期望利潤之和,構成了初始狀態為i的 k1步轉移后的轉移期望利潤 : PijVj k步轉

23、移期望利潤 Vi = Vi +PijVj = Pijrij + PijVj = Pij (rij + Vj )以上公式為k步轉移期望利潤遞推公式此公式可改寫為矩陣遞推式:由 Vi = Vi + PijVjk1k1k1 k1k1k1kk1馬爾科夫決策課件 V1定義 V = V2 為j步轉移期望利潤列向量 : VN V1 V = V2 為即時期望利潤列向量 :. VN P11 P12 P1N : : : 為一步狀態轉移概率矩陣 PN1 PN2 PNN 有V = V +PVjjjjP =K k1馬爾科夫決策課件例:設某商品銷售狀態分別為暢銷(狀態1)及滯銷(狀態2),銷售狀態轉移概率矩陣為 P11 P12 0.5 0.5 P21 P2