※ 引述《CorruptAngel (微笑面具)》之銘言：
: 抱歉我忘了說明了_ _||
: 這是某個演算法分析的一小部份... 所以可以假設k L足夠大/__\
hmm... 那我證的看起來就算 L, k - L 有是 0 的都 ok..
: 阿阿阿阿阿阿阿~~~~~
: 還有 我錯了orz...是要證 <=
: 真的很抱歉>///<
L = 0 時明顯兩邊都是 0
L = k 時明顯右邊 L <= L * (1 + ...)
好, 然後設當 k, L 較小時不等式成立
如果第一個 input 是 x (probability = L/k)
selected x (probability = L/k): E(k, L) = 1 + E(k - 1, L - 1)
selected zi (probability = L/k): 把 yi 換成 x, 那就變成 (k - 1, L) 的問題
E(k, L) = 1 + E(k - 1, L)
如果第一個 input 是 yi (probability = (L-k)/k)
直接刪掉, E(k, L) = E(k - 1, L)
L 2 L 2 L(k - L)
所以 E(k, L) = (---) + (---) E(k - 1, L - 1) + ----------
k k k^2
L(k - L) k - L
+ ---------- E(k - 1, L) + ------- E(k - 1, L)
k^2 k
L L^2 k - 1 1 k^2 - L^2 k - 1 1
<= --- + ----- (L - 1) sigma --- + ----------- L sigma ---
k k^2 p = 1 p k^2 p = 1 p
L k - 1 1 L^2 k - 1 1
= --- + L sigma --- - ----- sigma ---
k p = 1 p k^2 p = 1 p
k 1
<= L sigma ---
p = 1 p
不知道有沒有問題?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.20