Proportional vs. Uniform
policy for CQs

Assumption : Update distribution is uniform.
We compare weighted Uniform and weighted Proportional policies.

Number of  crawls allocated to 
ith pagein the proportional policy is



${\frac{C.W_i.\lambda_i}{\sum_i{(W_i.\lambda_i)}}}$


where Wi and $\lambda_{i}^{}$ are weight and change frequency of 
ith page


respectively.


So Information gained for this page is equal to 



${\frac{C.{W_i}^2.\lambda_i.\rho_i}{\sum_i{(W_i.\lambda_i)}}}$


where $\rho_{i}^{}$ is the update probability for 

ith page at any update instant.


Information gained in case of the uniform allocation for the same page


is equal to



${\frac{C.{W_i}^2.\rho_i}{\sum_i{W_i}}}$


So ratio of performance of the proportion to the uniform policy over all


pages becomes 



${\frac{\sum_i{\lambda_i}.\sum_i{W_i}}{\sum_i{(W_i.\lambda_i)}}}$

As we know $\sum_{i}^{}$a_i.$\sum_{i}^{}$b_i $\geq$ $\sum_{i}^{}$(a_i.b_i) for non-negative a_i's and b_i's, above ratio is always greater than 1.
This proves that Proportional always performs better than Uniform no matter how page weights and change frequencies are distributed.