※ 引述《CorruptAngel (微笑面具)》之銘言：
: 現在有一個input 長度k 由很L個x 和 k-L 個yj組成 j = 1 , 2 , ... k-L
: （第一個輸入是x）
: 有另外一個大小是k的集合W 由L個z和 k-L 個yj組成 j = 1 , 2 , ... k-L
: input開始讀起 讀到x則隨機刪除W中的一個元素 cost加1
: 如果讀到yi 且yi還在集合W中 則刪除yi ;
: 如果讀到yi 且yi已經被刪除 則隨機刪除一個元素 且cost加1
: （隨機：如果集合大小s裡面每個元素被刪除的機率是1/s）
: 證明 對於"任何的input"
: k
: E[cost] = L * sigma 1/p
: cost的期望值 p = 1
在花了很長的時間找我在數歸中的計算錯誤後,
我試著用 (k, L) = (2, 1) 來證這是錯的 @@
一個 x 一個 y1
所以有一半的機會第一個 input 是 x
如果 W 中選出 x: 下次出現 y1, total cost = 1
如果選出 y1: 下次出現 y1, 又要再加一個 cost, total cost = 2
一半的機會第一個 input 是 y1
這次會把 y1 刪掉, 下次出現 x, total cost = 1
1 1 1
所以 E[cost] = --- * 1 + --- * 2 + --- * 1 = 1.25
4 4 2
k 1 1
但是 L * sigma --- = 1 * (1 + ---) = 1.5 @@
p = 1 p 2
---
不知道是不是對 input 的假設有誤? 還是哪裡犯了機率計算上的錯?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.20
※ 編輯: scwg 來自: 140.112.30.20 (10/21 20:32)