Explicit formula for the 1D Sobol sequence

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.

• 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? – Fimpellizieri Jun 28 '18 at 18:44

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)}$$