Les séquences à faible écart fonctionnent-elles dans des espaces discrets?

Les séquences à faible écart dans un espace réel ( ) semblent être un excellent outil pour échantillonner uniformément un espace échantillon. Pour autant que je sache, ils se généralisent bien à n'importe quel espace réel, si vous utilisez une carte appropriée (par exemple. carte linéaire).$[0,1]^n$$[0,1]\to[a,b]$

Ces séquences se généralisent-elles en espaces discrets? par exemple. si j'ai un espace qui n'a que deux éléments dans chaque dimension (par exemple, les commutateurs booléens), puis-je simplement mapper ? Qu'en est-il des dimensions avec plus d'éléments (par exemple, un commutateur à 4 états?) Et pour les espaces avec différents nombres d'états dans chaque dimension?$[0,0.5]\to 0;\ (0.5,1]\to 1$

Mon intuition dit que cela pourrait fonctionner correctement, surtout si la sous-séquence est longue, mais qu'elle pourrait mieux fonctionner pour certaines séquences que pour d'autres, selon le nombre d'états (par exemple, une séquence de Halton pourrait avoir des interactions étranges avec une dimension avec un nombre premier d'états ou une séquence de Sobol ne peut fonctionner que pour les dimensions avec éléments). Mais je n'ai fait aucun test.$2^n$

Si cela ne fonctionne pas, pourquoi pas?

La reponse courte est oui! Il peut fonctionner et est aussi simple que de multiplier le vecteur par un entier et de prendre la partie entière de chacune de ses composantes.$t_n \in (0,1)^d$$m$

La réponse la plus longue est que votre intuition est correcte, qu'en pratique elle a des résultats mitigés selon le choix de:

• quelle séquence vous choisissez (Halton, Sobol, etc.)
• les paramètres de base (par exemple, 2,3,5, ...)
• et dans une moindre mesure, la valeur de .$m$

Cependant, j'ai récemment écrit un article de blog détaillé "L'efficacité déraisonnable des séquences quasi aléatoires , sur la façon de créer facilement une séquence ouverte à faible écart dans des dimensions arbitraires, qui est beaucoup plus susceptible de discrétisation que les séquences existantes à faible écart existantes, telles que les séquences Halton et Kronecker.

La section de l'article intitulée "Couverture" traite spécifiquement de votre question de discrétiser les séquences à faible écart.

Dans les carrés d'image suivants (qui indiquent un point de réseau entier unique) avec moins de rouge, cela implique une distribution plus uniforme, car chaque carré rouge indique que la cellule ne contient pas de point bleu. On peut clairement voir comment même la séquence distribue des points par rapport à d'autres méthodes contemporaines.$R$

La solution est une méthode de récurrence additive (modulo 1) qui généralise le problème 1-Dimensionnel dont la solution dépend du Golden Ratio. La solution au problème de dimension , dépend d'une constante spéciale , où est la valeur de la plus petite valeur réelle positive de telle que $d$$\phi_d$$\phi_d$$x$

Pour ,  , qui est le nombre d'or canonique.$d=1$$\phi_1 = 1.618033989...$

Pour , , qui est souvent appelé la constante plastique, et possède de belles propriétés. Cette valeur a été supposée être probablement la valeur optimale pour un problème bidimensionnel connexe [Hensley, 2002].$d=2$$\phi_2 = 1.3247179572...$

Jacob Rus a publié une belle visualisation de cette séquence bidimensionnelle à faible écart, qui peut être trouvée ici .

Avec cette constante particulière à la main, le calcul du terme -ème est maintenant extrêmement simple et rapide à calculer:$n$

Bien sûr, la raison pour laquelle on appelle cela une séquence de récurrence est que la définition ci-dessus est équivalente à

Dans presque tous les cas, le choix de ne change pas les caractéristiques clés, et donc pour des raisons de simplicité évidente, est le choix habituel. Cependant, certains arguments, relatifs à la symétrie, suggèrent que est un meilleur choix.$\pmb{\alpha}_0$$\pmb{\alpha}_0 =\pmb{0}$$\pmb{\alpha}_0=\pmb{1/2}$

Le code Python est

# Use Newton-Rhapson-Method
def gamma(d):
    x=1.0000
    for i in range(20):
        x = x-(pow(x,d+1)-x-1)/((d+1)*pow(x,d)-1)
    return x

d=5
n=1000

# m can be any number.
# In the diagram above it is chosen to be exactly sqrt of n, 
# simply to to make the visualization more intuitive 
# so that ideally each cell should have exactly one dot.
m=10

g = gamma(d)
alpha = np.zeros(d)                 
for j in range(d):
    alpha[j] = pow(1/g,j+1) %1
z = np.zeros((n, d))    
c = (np.zeros((n,d)).astype(int)  

for i in range(n):
    z = (0.5 + alpha*(i+1)) %1
    c = (np.floor(m *z)).astype(int)
print(c)

J'espère que cela pourra aider!

Si vous avez un nombre fini d'espaces, vous serez mieux avec une énumération explicite des espaces possibles avec une conception de bloc incomplète équilibrée construite sur eux. En fin de compte, les propriétés des séquences à faible écart sont asymptotiques, avec des propriétés souhaitables obtenues avec les longueurs de l'ordre où est la dimension de votre espace. Si le nombre de combinaisons possibles est inférieur à cela, vous pouvez simplement prendre toutes les combinaisons possibles et obtenir un design équilibré avec cela.$N\sim 6^s$$s$

Mise à jour: il y avait un livre qui a discuté en utilisant QMC pour les processus de Poisson et Bernoulli. Peut-être y trouverez-vous quelque chose d'utile, même si à mon avis c'est très loin d'un bon rapport qualité / prix. Pour 15 $, peut-être. J'ai trouvé que c'était quelque peu bâclé par endroits, poussant les idées de l'auteur (parfois bizarres) plutôt que d'utiliser ce qui était compris comme les meilleures méthodes de la littérature.