[erlang-questions] RNG algorithm choice for uniform natural numbers

[Raimo Niskanen]

On Thu, Aug 09, 2018 at 03:27:51PM +0200, Krzysztof Jurewicz wrote:
> > What I actually want to implement is a randomized apportionment scheme, as described on https://rangevoting.org/Apportion.html (“Truly unbiased methods”), but more efficient, like in the code below (not tested).
> 
> Tests revealed that the simple algorithm does not satisfy the quota property. Therefore I’ve used a more sophisticated one (code below), which however doesn’t require using a specific interval for drawing integers. Instead of the rand module, I use SHA-256 to generate random integers (taking first n bits). This is very interoperable between languages, though I don’t know whether SHA-256 satisfies all RNG properties desirable in that context. (Also I don’t have a proof that the distribution of apportioned seats is unbiased).
> 
> -type score() :: ({Votes :: non_neg_integer(), Id :: any()}).
> -type result() :: {Id :: any(), Seats :: non_neg_integer()}.
> 
> -spec apportion(list(score()), pos_integer(), pos_integer(), binary()) -> list(result()).
> apportion(Scores, TotalSeats, VotesSum, State) ->
>     {WholeSeatsMap, RemainderScores, RemainingSeats, _} =
>         lists:foldl(
>           fun (
>             {Votes, Id},
>             {WholeSeatsAcc,
>              RemainderScoresAcc,
>              RemSeatsAcc,
>              StateAcc}) ->
>                   Seats = Votes * TotalSeats div VotesSum,
>                   <<RandInt:32, _/binary>> = NewState = crypto:hash(sha256, StateAcc),

Have you tried to change line above to
                    RandInt = rand:uniform(1 bsl 32),
and not add 1 to RandInt below?

To see if the problem you had was about the random number generator or in
the surrounding code...

>                   RemainderScore = (Votes * TotalSeats rem VotesSum) * (RandInt + 1),
>                   {maps:put(Id, Seats, WholeSeatsAcc),
>                    [{RemainderScore, Id}|RemainderScoresAcc],
>                    RemSeatsAcc - Seats,
>                    NewState}
>           end,
>           {#{},
>            [],
>            TotalSeats,
>            State},
>           Scores),
>     DrawnIds =
>         %% We actually need to sort the list only at first RemainderSeats places, so here is a room for optimization.
>         [Id || {_, Id} <- lists:sublist(lists:reverse(lists:sort(RemainderScores)), RemainingSeats)],
>     ResultMap =
>         lists:foldl(
>           fun (Id, ResultMapAcc) ->
>                   maps:update_with(
>                     Id,
>                     fun (OldSeats) -> OldSeats + 1 end,
>                     1,
>                     ResultMapAcc)
>           end,
>           WholeSeatsMap,
>           DrawnIds),
>     lists:sort([{Id, Seats} || {Id, Seats} <- maps:to_list(ResultMap), Seats > 0]).

-- 

/ Raimo Niskanen, Erlang/OTP, Ericsson AB