Mutated Randomness

Hi, all!

This post is about an experiment I performed during Fall 2015 semester under the supervision of Prof. Stephanie Forrest as part of her course on complex adaptive systems here at UNM. The aim was to evolve a population of seemingly random binary sequences into sequences that are provably random with respect to a given set of tests of randomness and independence. My motivation for this experiment was to explore the possibility of using a genetic algorithm as a wrapper on the RNG (random number generator) code. This may be useful in situations when we require the user to not be able to regenerate the sequence(s) given initial RNG parameters.

For the experiment, the initial population of sequences was generated using the Mersenne twister inside Python 2.7.10’s random.randint(0,1) function and then evolved using a genetic algorithm (GA). The idea was to weigh these sequences with respect to the p-values of five statistical tests of randomness and independence performed on each of them and apply some selection, crossover, and mutation to evolve this population into one that has a majority of high fitness individuals.

The sequences in the initial population were generated using different seeds. This defined the original aim of the experiment: to evolve to a set of sequences that are *random enough* and show negligible dependence on the seed used for the random number generator (RNG) that created them. Thus, the GA was halted as soon as the population evolved to contain at least some given $\epsilon > 0$ fraction of high fitness individuals.

An interesting observation was made when the results were obtained. The algorithm showed a strong aversion to mutation (when one would expect that mutation would actually help). Even when setting the mutation probability to something as low as $0.01$, the population did not seem to converge to contain high fitness individuals up to the fraction we desired. This suggested that the space of all random sequences (as generated by this RNG) contained very small (maybe even singleton sets of) neutral regions with respect to the fitness function used and that there was perhaps a high correlation between the bits in the sequence and their position in it. The plot below shows the results obtained, where the X-axis represents number of generations and the Y-axis represents fitness.

The plot below shows the results obtained, where the X-axis represents number of generations and the Y-axis represents fitness. Mutation probability was set to $0.01$ per bit and the crossover probability was kept very close to $1$. As can be seen, the maximum fitness in the population decreases with successive generations.

Even more interesting is the fact that a high probability single point crossover operation supported evolution in our favor, and produced a population of distinct sequences having high fitness values. So, if it was indeed the case that the neutral regions are small, one would expect the crossover to not do so well either. So, to verify this, I ran some simulations with low crossover and mutation rates and observed that the population hardly evolved. This behavior has made me sleepless since.

Some questions and extensions I am considering for this project are as follows:

1. Can $p$-values be replaced by some other measure of goodness on the tests of randomness/independence?
2. Does the order of applying the tests matter? In other words, given a sequence of tests $T_1,T_2,\dots,T_n$, when does there exist (or not) a sequence $s$ such that $s$ is not random with respect to the set $\{T_1,\dots,T_i \}$ for all $i < n$, but is random with respect to the whole set $\{T_1,T_2,\dots,T_n\}$?
3. How about another design of the fitness function, other than just the product of the $p$ values?
4. Does the nature of crossover matter in this setting?
5. Is there an analytical explanation to the small sized neutral regions?
6. Define a measure for goodness of evolution and prepare plots for this goodness against crossover rates and mutation rates.

I plan to update this post with the actual algorithm I used and plots for the results, along with a more analytical explanation of the situation and possibly the questions above, so that some of you can suggest edits and help me solve the mystery. Stay tuned 🙂

References :

Image source

A *bug* in democracy

Remember those times when the leaders were honest and you could believe in the fact that whatever they propose will be for the good of people in general? Well, some leaders are still like that and for some others, even carbon dating wouldn’t be able to determine the last time this happened.

On a more serious note, this post is an interesting problem from Peter Winkler’s book on mathematical puzzles [PW], brought to my attention by my advisor Jared during our weekly group meeting two weeks back. It tends to highlight the power of majority voting schemes in driving all the economy in the hands of only one person. Although the practical scenario may be largely different, the puzzle below does demonstrate potential scheme, which Jared referred to as a bug (and I agree), that exploits democracy in the favor of the ruler. Hope you find it an interesting read!

Consider a democracy with $n \geq 3$ people, one of whom is the leader (elected or otherwise). At the time of his election, each of the $n$ people have some initial amount of money they possess. The aim of the puzzle is for the leader to propose a series of money redistributions among the people so that at the end of the process, he is able to collect as much as money from the people as possible. The only caveat here is that for whatever change he proposes, he needs a majority of the people to vote in favor of the proposal for it to pass. We assume that every person (except the leader) votes YES to any scheme that increases the money he currently possesses, votes NO to any scheme that proposes a smaller amount that what he currently owns and ABSTAINS otherwise. However, remember that since the leader is one of the $n$ people to vote, he has a say in the voting as well.

With respect to the discussion we had in our group meeting and acknowledging all other members who contributed towards coming up with this solution, here is what we think the leader can do best.

Theorem: For a democracy with $n \geq 3$ people that starts with a total of $T$ units of money distributed among the people, a pseudo-greedy leader is always able to gather $T-1$ units of the money to himself in $\mathcal{O}(\log n)$ rounds of voting.

Let us first look at an example before we try to attempt proving the theorem above. Suppose there are $5$ people in the democracy, each starting with a dollar. For the sake of representation, let this fact be represented by {A:1, B:1, C:1, D:1, E:1}, where without loss of generality, we assume that A represents the leader.

To begin, the leader suggests the following redistribution of money: {A:1, B:2, C:2, D:0, E:0}. When the voting begins on this scheme, D and E vote NO but B and C vote YES. Then, it is up to the leader to break the tie and he does this by voting YES since he foresees this scheme to help him in the future. The scheme is then passed and the money has now being redistributed as proposed. The next scheme that the leader proposes is {A:1,B:4,C:0,D:0,E:0}, on which B votes YES, C votes NO and D and E ABSTAIN. Again, to break the tie, the leader votes YES and the scheme passes with this redistribution of the money.

In the last step, the leader proposes {A:4, B:0, C:1, D:0, E:0}. For this scheme, B votes NO, C votes YES and the others ABSTAIN. Hence, the leader votes YES and the scheme passes with the majority vote. Note that the leader has been able to grab $4 out of the total of$5 in the population in just 3 steps, by being non-greedy sometimes. Also, note that the remaining $1 cannot go to the leader since he will never have a majority to vote in favor of any proposition that does this. Thus, the leader ends with taking over$4 in just 3 steps, taking full advantage of the power of majority voting scheme. In fact, since the first two schemes he proposed did not increase his dollars, he must have come out as being generous to some people in the process, building confidence in his leadership which he would exploit later. Hence, the term pseudo-greedy in the theorem statement. Sounds like a serious bug to me!

Now that we have seen an example of how the leader can drive all but one dollar to himself, the theorem statement above can be easily proved. For the sake of brevity, I will not present a formal proof of the same, but rather give an informal idea on how one can devise a set of schemes which end in a distribution in favor of the leader.

The main idea is for the leader to always keep the decision of voting YES on the schemes he wants to pass with himself. The leader can do this by enforcing fewer than a half of the people to vote NO (since this is unavoidable) and by keeping at least these many people to vote YES (to obtain a tie which he will break in his favor). The latter requires him to be nongreedy sometimes, bu that’s OK since he knows in the long run, this will benefit him. Typical political hypocrisy!

Thus, as demonstrated above, the leader takes money from fewer than a half of the people (as may as he can) and transferring that money to the other half which will vote YES on the redistribution. This way, once all the money (except the dollars with the leader) reach one person (who is not the leader), then the trick is to give one dollar to a person who doesn’t have any money and put the remaining money with the leader. This scheme will always pass because the poor person who got this one dollar will vote YES to the scheme and the majority will be achieved when the leader votes. It’s always easy to lure the most suffering men into voting YES for anything that even remotely seems favorable to them.

Hence, in $O(\log n)$ steps, the leader has collected all but one dollar from the people in the democracy. An important point to note here is that the puzzle doesn’t require any person to know the full distribution of money he is voting for in any step. In other words, as long as a person sees that the leader has proposed something in which his balance will increase, he votes YES regardless of what others get or lose. This is again very representative of real life in which hardly anyone looks at the full budget proposed by the government and checks complete money flow before voting for the same. Ignorance may be a bliss for some, but is probably driving our money away from us in this scenario.

Well, I hope this puzzle was an interesting mathematical insight into what can go (or is going) wrong with the democracies all around. A simple majority voting scheme can be adversarially designed to capture all the money or resources and numerous such algorithms may exist in place already. I would also like to say that this post is not pointed to anyone in particular, and just presents a mathematical puzzle from a curious point of view.

Moral of the story : DO NOT ABSTAIN. Practice your voting rights even if the leaders propose something that may not favor or harm you. As can be seen, if the people in the democracy above had not abstained, the leader would never be able to gather all the money to himself.

Until next time, have fun and stay tuned!

References :

[PW] Winkler, Peter. “Mathematical Puzzles: A Connoisseur’s Collection. 2004.” AK Peters.

Image source