※ 引述《scwg (void * I = NULL;)》之銘言：
: ※ 引述《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 z (probability = L/k): E(k, L) = 1 + E(k - 1, L - 1)
: selected yi (probability = (k-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)
這幾行我改了一些東西
大概我又沒說清楚..
"對於任意的input" 是說不管怎樣的input來不等式都會對
也就是不行算對所有input的期望值(不能把input算進期望值,也就是要worst case)
不過學長你這個證明的助益很大＠＿＠ 我在想看看..
: 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: 61.228.191.26
※ 編輯: CorruptAngel 來自: 61.228.191.26 (10/21 21:44)