Probability breaking sequences

Question

If we have a finite list of elements we can determine the probability of any one element being drawn at random as the number of times it occurs divided by the total number of elements in the list.

For example if the list is [2,3,2,4] the probability of drawing 2 is \$\frac 1 2\$ since there are \$2\$ 2s and \$4\$ elements total.

For an infinite sequence we can't use this method. Instead what we can do is look at every prefix of the sequence determine the probability using the above method and then see if the limit of the probabilities converges. This looks like

$$ P(x, s_i) = \displaystyle\lim_{n\rightarrow\infty} \dfrac{\left|\left\{s_m\mid m<n,s_m=x\right\}\right|}{n} $$

For example if we have the sequence which alternates between 0 and 1, [0,1,0,1,0,1..., then the probability of drawing a 0 is \$\frac 1 2\$.

Now this is neat but sometimes the limit just doesn't converge, and so the probability of an element being drawn is undefined.

Your task will be to implement a sequence where for every positive integer its probability is undefined. This means that no matter what you pick this limit must not converge. It also means just as a side effect that every positive integer must appear an infinite number of times. Otherwise the probability would converge to \$0\$.

You may implement any sequence you wish as long as it fulfills the above. Your sequence should output non-negative integers. Zero is permitted to appear in the sequence but is not required to.

This challenge uses the defaults for sequence IO which can be found here.

This is code-golf so the goal is to minimize your source code with answers being scored in bytes.

Answer 1

x86 32-bit machine code, 7 bytes

0F BD C1 0F BC C0 C3

Try it online!

Following the fastcall calling convention, this takes the 1-indexed n in ECX and returns the nth value in EAX.

In assembly:

.global f
f:
    bsr eax, ecx
    bsf eax, eax
    ret

This produces blocks of size 1, 2, 4, 8, 16, ... of the same number, so that each block raises its number's proportion to more than half. bsr (find highest position of a 1 bit) is used to obtain the 0-indexed block number.

The values used for the blocks are (0), 0, 1, 0, 2, 0, 1, 0, 3, ...; these values are produced by bsf (find lowest position of a 1 bit) on the block number. (The result of bsf is officially undefined for a value of 0, but on at least some systems it consistently leaves the destination register unchanged, producing 0 for block 0.)

Answer 2

Python 2, 24 bytes

lambda n:`n`.find("1")+1

Attempt This Online!

This is heavily based on @xnor's idea in the comments. It returns the (1-based) index of the most significant decimal "1" and 0 if there is none.

Why does it work?

for any cutoff 10^k the fraction of numbers below it that have the first "1" at position n (n<k) is asymptotically the same, in particular, it is bounded below by a positive number. But between 10^k and 2x10^k there are no such numbers, meaning that frequency will eventually fall to half its value (and then rise again) which is incompatible with convergence.

The case k=1 must be dealt with separately (easy) and k=0 is exempt by OP.

Python, 36 bytes

lambda n:int(bin(len(bin(n)))[3:],2)

Attempt This Online!

Takes an index and returns the corresponding value. Numbers are first mapped to the length of their binary representation. That way whatever this finally maps to is elevated to a probability of roughly 0.5. As a simple way to make sure every number comes back eventually, we take again the binary representation and use the most significant bit for modulo. In other words we remove it and all leading zeros that may be exposed.

The test code first shows the first 1000 items and then the unique values of the first 1000 blocks.

Answer 3

Python 3, 41 bytes

j=1
while j:j+=1;print([str(j)[1:]]*2**j)

Try it online!

Here, we increment j and strip the leading digit, to get a sequence where every number appears infinitely often. Let's call the stripped number k. Then we output 2**j copies of k. This has the property that the probability of k jumps up to 50%, when we ouput k, then decreseas by half after every iteration. This means that the probability of k doesn't converge.

The probability jumps occur because \$2^j>\displaystyle\sum_{n=1}^{j-1}2^n\$

The IO format is a bit rough, to say the least. The output is a non-digit separated list of numbers, which may have leading zeros.

Python 3, 48 bytes

j=10
while j:j+=1;print(*[int(str(j)[1:])]*2**j)

Try it online!

Same idea, except the output looks a bit nicer. Numbers don't have leading zeros and the output is whitespace separated.

Python 3, 39 bytes

j=2
while j:j+=1;print([~-2**j%j]*2**j)

Try it online!

This is based on a conjecture that \$2^n\mod n\$ will take all values, except 1, infinitely often. To fix the missing \$1\$, we can compute \$2^n-1\mod n\$, and now \$0\$ will be the missing value.

Answer 4

JavaScript (Node.js), 29 bytes

n=>parseInt(10+Math.log(n),2)

Try it online!

Like m90's idea, output each number for a time, making it go up to parseInt(k,2), which every number happen for infinite times(10012xxxx for 9, etc.)