The referendum (or compound majority) paradox occurs when the majority of voters in the majority of districts supports an issue/candidate but the majority of voters across all districts opposes the same issue/candidate (or vice versa). We calculate the likelihood of this social choice anomaly for any (possibly large) odd number of districts and any (possibly large) odd number of voters per district. The likelihood of the paradox is close to 50% when the issue/candidate is divisive (voters across all districts are split almost 50%-50%). The paradox virtually disappears when the issue/candidate is supported/opposed by at least two-thirds of all voters.