"God does not play dice", says Einstein. But we do! What if there were 7 players and you have to randomly choose one with a 6 face dice?
Let me deface the question: What if there was a function (Called rand6) that randomly generates a Natural number between 1 to 6 and you have to write another function (Called rand7) that generates a random Natural number between 1 to 7 using first function (rand6)? And rand6 is balanced.
Note that the probability of all events must be equal!
Wait a moment! Think! or just skip this step to my stupid solution.
This is the answer if you wish:
But how?
The idea is to launch an election campaign! there will be a local_max_count
that will keep top candidates count which have equal votes. Candidates are one of {1,2,3,4,5,6,7} that will go for a second, third, or n*th* election. And there is also a global_max
variable that keeps the maximum count of votes of top candidate.
int local_max_count = -1;
In each election, we play dice for each candidate (not really what Facebook is made because of), and the number will be it's vote count.
for (int i = 0; i < 7 ; i ++)
if (votes[i] == global_max)
{
local_max_count ++;
// call the rand6()
votes[i] = rand6();
}
then global max
is defined as:
// Find the array maximum
for (int i = 0; i < 7 ; i ++)
global_max = max (global_max, votes[i]);
And if there was a unique top candidate, function will return that as answer:
if (local_max_count == 0)
for (int i = 0; i < 7 ; i ++)
if (votes[i] == global_max)
return i + 1; // i + 1 because normal people start counting from 1.
But what if there were two or many other candidates?
There is the point that way we have to recursively call our function and change a line in // Election
code to add value to previous value:
votes[i] += rand6();
Test
You can run this function for 1000 times and visualize output with pyplot
or any thing you wish. But it has to be something like image below because all numbers must have same chance to keep fair.
Question!
What if rand6
function was unbalanced?
Top comments (0)