jeudi 29 janvier 2015

Transformation of distorted random sequences produces random sequences?

My program generates what might be called switch(x) sequences.


Here's a description the algorithm that produces them:



# define a switch(x) sequence of length n^2
def switch(x):
s = [] # define a bit string s:
s.append(random.choice([True, False])) # set its first bit randomly,
for i in range(1, n * n): # but for every subsequent bit i,
prior = s[i-1] # find its prior bit i-1,
shouldSwitch = x > random.random() # and with probability 1-x,
if shouldSwitch: s.append(not prior) # set i to opposite of its prior;
else: s.append(prior) # otherwise, have i = its prior.
return s


At x = .5, the sequence is thought to be a perfectly random sequence of bits. Deviating x distorts this randomness by producing sequences that either alternate or repeat bits too often.


I produced a program that computed the average alternation rate of a produced switch(x) sequence.



r = 0.0
for i in range(len(s)-1):
if s[i] != s[i+1]:
r = r + 1
rate = r/(len(s)-1)


Of course, I always obtain a rate relatively close to x when I put a switch(x) sequence through it, whatever x is. Like, within 1/100ths.


But suppose I transform my produced switch(x) sequence like so (where len(s) = n*n):



s1 = switch(x)
s2 = []
for i in range(n):
for j in range(n):
s2.append(s1[i + j*n])


Whenever I calculate the alternation rate for sequences transformed in this way, I always obtain a value really close to .5! The consistency is scary.


That doesn't make much sense to me, especially for values of x that are very close to 0 or 1. So I was hoping you could help me figure out what's going wrong.


Sorry if something's terrible about my style/efficiency.





Aucun commentaire:

Enregistrer un commentaire