How do you define an algorithm that samples a random natural number, according to a probability distribution that assigns non-zero weight to every natural number? Meditate on it, before reading the solution.
def sample_nat(p_heads=0.5):
i = 0
while True:
if coin_flip(p_heads) == 'heads':
return i
i += 1
With p_heads=0.5 we implicitly define the probability distribution:
P(n:N):=12(n+1)
This program is pretty weird because the probability that it will not have halted after n steps is non-zero, for any n.
[Edit 2023-11-26]
Now I understand what is going on. This program is in fact a non-halting program, that halts with probability 1.
This is similar to how the probability that you get a rational number when you sample uniformly from [0,1]⊆R is zero.
(I am unsure about this paragraph.) In practice, this depends somewhat on what pseudo-random number generator we use. The pseudo-random number generator that we use might be such that there is no possible initial state, such that the generated sequence would be all tails, in which case the program would be guaranteed to terminate.
I notice that the mathematics-frame I used to try to generate a solution was utterly inadequate, whereas the programming-frame is much more productive wrt this problem. I think one big general weakness of my general math-frame, is that it imagines/visualises infinities as static, rather than as conceptually chunked dynamic processes.
How do you define an algorithm that samples a random natural number, according to a probability distribution that assigns non-zero weight to every natural number? Meditate on it, before reading the solution.
With
p_heads=0.5we implicitly define the probability distribution: P(n:N):=12(n+1)This program is pretty weird because the probability that it will not have halted after n steps is non-zero, for any n.
[Edit 2023-11-26]
Now I understand what is going on. This program is in fact a non-halting program, that halts with probability 1.
This is similar to how the probability that you get a rational number when you sample uniformly from [0,1]⊆R is zero.
(I am unsure about this paragraph.) In practice, this depends somewhat on what pseudo-random number generator we use. The pseudo-random number generator that we use might be such that there is no possible initial state, such that the generated sequence would be all tails, in which case the program would be guaranteed to terminate.
[END Edit]
I notice that the mathematics-frame I used to try to generate a solution was utterly inadequate, whereas the programming-frame is much more productive wrt this problem. I think one big general weakness of my general math-frame, is that it imagines/visualises infinities as static, rather than as conceptually chunked dynamic processes.