1
$\begingroup$

The Sobol sequence in one dimension looks like this:

$$S = 0, \frac{1}{2}, \frac{3}{4}, \frac{1}{4}, \frac{3}{8}, \frac{7}{8}, \frac{5}{8}, \frac{1}{8}, \cdots$$

So I decided to write this out in binary.

0
0.1
0.11
0.01
0.011
0.111
0.101
0.001
...

I suspected some kind of pattern, so I defined a new function $R$ which reverses the binary form of the number. It's a bit more difficult to write in math notation, but I tried anyway:

$$R\left(\sum_{k=-\infty}^{\infty}{c_k 2^k}\right)=\sum_{k=-\infty}^{\infty}{c_k 2^{-k-1}}, c\in\{0,1\}$$

So we apply this function to the sequence, and now we have some integers to work with:

  0
  1.0
 11.0
 10.0
110.0
111.0
101.0
100.0
...

$$R(S)=0,1,3,2,6,7,5,4,\cdots$$

So at this point I take some blind guesses and eventually find this algorithmic looking way of producing S.

Define notation for length of a sequence: $|X|$

Define notation for concatenation of sequences: $X || Y$

Define function which returns the input sequence backward: $b$

Define functions for left and right half of a sequence with even length: $l, r$

Define the permutation function: $p(X) = X \text{ if } |X|\le 1 \text{ otherwise } p(l(X))||b(p(r(X)))$

Define a partial sequence: $S_k = p([0,1,2,\cdots,2^k-1])$

$S = \lim_{k\to\infty}{R(S_k)}$

As far as I can tell, this definition is correct.

The only problem is, it's based on a permutation, so it's really inconvenient if I just want to get one value at some index. Surely there's an explicit formula? It might be very messy, but I still want to see it anyway.


Found another construction based on bitwise XOR.

Define $L$ to return the lowest $1$ in the binary representation of the input.

$$L(x)=(((x-1)\oplus x)+1)\gg 1$$

$$L([1,2,3,\cdots]) = 1,2,1,4,1,2,1,8,\cdots$$

Define a sequence recursively:

$P_0 = 0, P_k = P_{k-1}\oplus L(k)$

$S = R(P)$

I suppose we could define an XOR sum and then get an explicit formula from that, but I'm not really satisfied with that - surely there's a better way?


Side note, I'm not sure if Sobol is simply a type of sequence, or if there is one canonical Sobol sequence (for each number of dimensions). If it's just a type, then I suppose there's something about this specific one that makes it the best.

There's the much simpler sequence $R([0,1,2,3,\cdots])$ which is similar and almost as good for Sobol's purposes. If Sobol is just a type of sequence, perhaps this can be adapted into one with all the same properties - it's much more straightforward to calculate so it would make a good substitute.

$\endgroup$
  • 1
    $\begingroup$ I am not quite sure I find the rule of the numerators clear. Perhaps you can provide a few more terms, or else a definition of the sequence? $\endgroup$ – Fimpellizieri Jun 28 '18 at 18:44
2
$\begingroup$

The Gray code is that intermediate sequence you saw:

$$G = 0,1,3,2,6,7,5,4,\cdots$$

The Wikipedia page for Sobol sequence mentions Gray code as a way of generating it but doesn't give details.

Anyway, the Gray code has a simple explicit formula using bitwise operators:

$$G_k = (k\gg 1)\oplus k$$

From there we just string that together with your $R$ function:

$$S=R(G)$$

It's probably easier to leave it like this, since both are most easily defined based on bits.


But just for completeness:

We can get the bits of the Gray code like so:

$$G_{k,n}=\left\lfloor 2^{-n}k+\frac{1}{2}\right\rfloor \mod 2$$

$$G_k=\sum_{n=1}^{\infty}{2^{n-1}G_{k,n}}$$

$$G_k=\sum_{n=1}^{\infty}{2^{n-1}\left(\left\lfloor 2^{-n}k+\frac{1}{2}\right\rfloor \mod 2\right)}$$

We can observe that the highest $1$ bit of $G_k$ is the same as $k$. For $n>\lfloor\log_2(k)\rfloor$, all $G_{k,n}$ will be $0$. So we can stop summing once we get there:

$$G_k=\sum_{n=1}^{\lfloor\log_2(k)\rfloor}{2^{n-1}\left(\left\lfloor 2^{-n}k+\frac{1}{2}\right\rfloor \mod 2\right)}$$

Then substitute with your definition of $R$ to get $S$:

$$S_k=\sum_{n=1}^{\lfloor\log_2(k)\rfloor}{2^{-n}\left(\left\lfloor 2^{-n}k+\frac{1}{2}\right\rfloor \mod 2\right)}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.