Efficient power line outage identification is an important step which ensures reliable and smooth operation of smart grids. The problem of multiple line outage detection (MLOD) is formulated as a combinatorial optimization problem and known to be NP-hard. Such a problem is optimally solvable with the help of an exhaustive evaluation of all possible combinations of lines in outage. However, the size of search space is exponential with the number of power lines in the grid, which makes exhaustive search infeasible for practical sized smart grids. A number of published works on MLOD are limited to identify a small, constant number of lines outages, usually known to the algorithm in advanced. This paper applies the Bayesian approach to solve the MLOD problem in linear time. In particular, this paper proposes a low complexity estimation of outage detection algorithm, based on the classical estimation of distribution algorithm. Thanks to an efficient thresholding routine, the proposed solution avoids the premature convergence and is able to identify any arbitrary number (combination) of line outages. The proposed solution is validated against the IEEE-14 and 57 bus systems with several random line outage combinations. Two performance metrics, namely, success generation ratio and percentage improvement have been introduced in this paper, which quantify the accuracy as well as convergence speed of proposed solution. The comparison results demonstrate that the proposed solution is computationally efficient and outperforms a number of classical meta-heuristics.