[seqfan] Binary counter with random bits

[David Scambler]

A binary counter starts at zero and attempts to increment by 1 at each step. However each bit that should toggle may or may not do so. 

A matrix T with 1's for possible transitions from k to k+1 looks like this: 
to\from
11010001...
11010001...
01110001...
01110001...
00011101...
00011101...
00010111...
00010111...
...........

Starting with a vector containing a single 1 at k=0, repeated multiplications by T yields a triangle S(n,k) that counts the number of paths that arrive at value k after n steps.

n
0: 1
1: 1,1
2: 2,2,1,1
3: 5,5,4,4,1,1,1,1
4: 15,15,14,14,7,7,7,7,1,1,1,1,1,1,1,1

The distinct values in each row are the rows of A137650 and the row sums are A001861(n), that is, the count of all paths after n steps. The number of paths ending at k=0 after n steps is the first column, 1,1,2,5,15.. = Bell numbers A000110.

The number of paths ending with k=n after n steps seems to be 1,1,1,4,7,36,171,813,3046... which is a ragged slice through A137650 (not clear yet).

Now suppose that each bit that should toggle does so with probability 1/2. We can calculate the probabilities of value k after n steps. Integer numerators can be obtained by multiplying the probability after step n by D(n) = A006125(n+1) = 2^triangular(n).

D(n) * Probability of k=n after n steps = 1,1,1,11,35,1659,133019,19469339,891982491,586689014427,... (no formula yet)
D(n) * Probability of k=0 after n steps = 1,1,3,19,251,6843,381851,43357211,9976746651,...

The latter series can be obtained by convolving rows of A126347 with (reverse) powers of 2. E.g. 19 = 1*8 + 2*4 + 1*2 + 1*1.

There are several potential new series here. I hope this is of interest,
dave