Main Intuition Average case Consider the following scheme Popularity Only perform coded caching among most"popular'files 1 to N The average transmission rate for the "popular'files will be upper bounded by the worst-case rate M N,M、N1 K·(1-) N File N、1+N1 K N, M Index whenever K>> N,/M If these files are indeed very popular, k will be large. Thus, the expected rate will likely be close to this upper bound N M Once a file is"popular its popularity does not matter!• Consider the following scheme: – Only perform coded caching among most “popular” files 1 to N1 • The average transmission rate for the “popular” files will be upper￾bounded by the worst-case rate: whenever K’ >> N1 /M • If these files are indeed very popular, K’ will be large. Thus, the expected rate will likely be close to this upper bound Once a file is “popular”, its popularity does not matter! 11 Main Intuition: Average Case File Index Popularity 𝑁1 1 1 1 1 1 1 ' (1 ) (1 ) 1 ' 1 M N M N K N M N M K M N • − •  − = − + ? 1 1 N M −