  The Population-Based Incremental Learning (PBIL) algorithm uses a convex
combination of the current model and the empirical model to construct the next
model, which is then sampled to generate offspring. The Univariate Marginal
Distribution Algorithm (UMDA) is a special case of the PBIL, where the current
model is ignored. Dang and Lehre (GECCO 2015) showed that UMDA can optimise
LeadingOnes efficiently. The question still remained open if the PBIL performs
equally well. Here, by applying the level-based theorem in addition to
Dvoretzky--Kiefer--Wolfowitz inequality, we show that the PBIL optimises
function LeadingOnes in expected time $\mathcal{O}(n\lambda \log \lambda +
n^2)$ for a population size $\lambda = \Omega(\log n)$, which matches the bound
of the UMDA. Finally, we show that the result carries over to BinVal, giving
the fist runtime result for the PBIL on the BinVal problem.
