Abstract Simultaneous localization and mapping (SLAM) is one of the most frequently studied problems in mobile robotics. Different map representations have been proposed in the past and a popular one are occupancy grid maps, which are particularly well suited for navigation tasks. The uncertainty in these maps is usually modeled as a single Bernoulli distribution per grid cell. This has the disadvantage that one cannot distinguish between uncertainty caused by different phenomena like missing or conflicting information. In this paper, we overcome this limitation by modeling the occupancy probabilities as random variables. Those are assumed to be beta-distributed and account for the different causes of uncertainty. Based on this map representation, we derive a SLAM algorithm, including all necessary sensor models, for building maps composed of beta-distributed random variables and using these maps for localization. Furthermore, we propose measures for quantifying uncertainty in the resulting maps and for solving navigation tasks. We evaluate our approach using real-world as well as simulation-based datasets and we compare it to a state-of-the-art SLAM algorithm for building classical grid maps.