This will eventually stop…

Given an input string S, print S followed by a non-empty separator in the following way:

• Step 1: S has a 1/2 chance of being printed, and a 1/2 chance for the program to terminate.

• Step 2: S has a 2/3 chance of being printed, and a 1/3 chance for the program to terminate.

• Step 3: S has a 3/4 chance of being printed, and a 1/4 chance for the program to terminate.

• Step n: S has a n/(n+1) chance of being printed, and a 1/(n+1) chance for the program to terminate.

Notes

• The input string will only consist of characters that are acceptable in your language's string type.

• Any non-empty separator can be used, as long as it is always the same. It is expected that the separator is printed after the last print of S before the program terminates.

• The program has a 1/2 chance of terminating before printing anything.

• A trailing new line is acceptable.

• Your answer must make a genuine attempt at respecting the probabilities described. Obviously, when n is big this will be less and less true. A proper explanation of how probabilities are computed in your answer (and why they respect the specs, disregarding pseudo-randomness and big numbers problems) is sufficient.

Scoring

This is , so the shortest answer in bytes wins.

• Can the separator be an empty string? Commented Jun 12, 2017 at 7:13
• @rturnbull Well no, because in that case there is no separator. Commented Jun 12, 2017 at 7:18
• Do we have to print these one after the other, or can we just print all of them when the program terminates? Commented Jun 12, 2017 at 18:21
• @Dennis One after the other. Commented Jun 13, 2017 at 6:42

Dart - 73 chars

import"dart:math";p(s,{i=2}){while(new Random().nextInt(i++)>0)print(s);}

This function implements the algorithm by taking a string as input and printing it as necessary. The separator is obviously newline. To run it, you need a main method like main(){p("foo");}.

It's hard to be small when you need to import the math library and instantiate the Random class.

Try it online

APL (Dyalog), 17 bytes

Requires ⎕IO←0 which is default on many systems.

{⎕←⍺⋄×?⍵:⍺∇1+⍵}∘2


This is a monadic function derived from a dyadic function by currying the right argument.

{ anonymous function

⎕←⍺ print ⍺ (the string)

 ⋄  then

×?⍵: if the signum of a random int in the range [0,-1] is 1, then:

⍺ ∇ 1+⍵ recurse with 1+ as new right argument

(implicit, else: stop)

}∘2 with 2 as bound right argument

Try it online! Sets ⎕RL←0 (Random Link) to avoid TIO's regeneration of the same random number.)

C# 79 bytes

does a divide by 0 error count as terminating?

using System;s=>{for(int i=1;2>1/new Random().Next(++i);Console.Write(s+' '));}


Lua, 50 46 bytes

i=2while 1<math.random(i)do i=i+1print(...)end


Assumes that it is already seeded

Try it online!

JS (ES6), 47 bytes

x=>{for(i=1;Math.random()<i/(i+1);i++)alert(x)}


Unlike the other ES6 answer, this uses a for loop and alert bombs instead of recursion. The seperator that is printed when the program stops is undefined.

k, 20 bytes

0:((*1?2+)(1+)/0)#,


Explanation:

0:((*1?2+)(1+)/0)#,
0    /set x to 0
(*1?2+)    /     /...while randint [0,2+x) is > 0
(             )#, /make array with that many copies of the string
0:                  /output array line by line


Probabilities:

 5#{(((#:'=x{(*1?2+)(1+)/0}\0)@!x))%x}2000000      /experimental
0.5001625 0.1667005 0.083024   0.050034 0.0333645
{(1%x)*-1_1.,*\{(x-1)%x}x}2+!5                    /calculated
0.5       0.1666667 0.08333333 0.05     0.03333333

• @ValueInk Oh, I believe I misread! Fixing this now... Commented Jun 15, 2017 at 22:44
• @ValueInk Fixed. Commented Jun 15, 2017 at 23:12

Forth (gforth), 71 bytes

include random.fs
: f 1 1 do i 1+ random i = ?leave 2dup type cr loop ;


Try it online!

Technically will end after the [maximum single-cell number]th iteration, but the chance of that happening is at least 2-64 on most systems (and likely 2-32 on others)

Code Explanation

include random.fs  \ load the random library to generate random numbers

: f                \ start a new word definition
1 1 do           \ loop from 1 to 0 (start at 1 stop when we reach 0 via integer overflow)
i 1+ random    \ get a random integer from 0 to n
i =            \ check if the value equals n
?leave         \ end the loop if true
2dup type cr   \ otherwise, print the input string followed by newline
loop             \ go back to beginning of loop
;                  \ end the word definition



Scala 7672 71 Bytes

def w[T](s:T)={var x=2;while(Random.nextFloat>1f/x){x+=1;print(s+" ")}


This uses a template because it works fine for strings, and saves a character. Other than that, it's a pretty basic implementation. Scala picks up a couple bytes by not having a proper++ operator. Random.nextFloat returns a random value between 0 and 1, and 1f/x forces float division. This implementation uses a space as a separator, with no trailing newline.

• You can use x+=1 to save a byte
– user
Commented Jul 24, 2021 at 19:33

Thunno 2, 7 bytes

(ṅƙɼḅ;£


Attempt This Online!

Explanation

(ṅƙɼḅ;£  # Implicit input
(        # while
ṅ       # (condition)  0-based iteration index
ƙ      #              increment twice
ɼ     #              random item from [1..that]
ḅ    #              equals one?
;£  # (body)  print input string with newline
# Implicit output


Trilangle, 104 bytes

'0.<_.<.>i.S)#..\_/.L',z$)<.Se(*8'.3....LS:.)~<#+7....@..^.-/...,>j))2<.L,z,<......><#(,.#o.....\",o,../  Try it on the online interpreter! The random number instruction $ creates a random number along the whole range of integers. This program uses the sign of $$\\left|rand\left(\right)\right|+\frac{INT\_MIN}{i+1}\$$ to determine whether to terminate.

I don't currently have the ability to create the colorized drawing I normally do, but here's an annotated disassembly. I created this first, then wrote the program, and then tweaked this to match the output of the disassembler.

; Get the string and its length. Pretty standard.
PSI #0
input_loop: ; 0.2
GTC
BNG input_cleanup
SWP
INC
JMP input_loop
input_cleanup: ; 2.0
; Put the iteration number on top of the stack. Rather than popping the -1 to
; push 0, just increment it.
INC
; These swaps happened to be here, and they don't do anything
SWP
SWP
; Increment the iteration number and check whether to terminate
check_term: ; 2.10
INC
RND
; RND gives a number in [-0x800000, 0x7fffff].
; Terminate with probability 1/(i+1).
DP2
POP
; Get INT_MIN as 2^23. This overflows and becomes a negative number.
PSI #3
PSI #8
MUL
DEC
EXP
; then do the division and compare
SWP
INC
DIV
SWP
BNG rand_neg
; Stack: [...s, s.length, i, INT_MIN/(i+1), rand]
; Terminate when rand + INT_MIN/(i+1) < 0
compare: ; 3.2
; Flip the sign, then end when it's positive instead of negative. It turned out
; to save room to make the positive branch terminate.
NOT
BNG print_begin
JMP end ; disassembler quirk ¯\_(ツ)_/¯
rand_neg: ; 4.0
; Stack: [...s, s.length, i, INT_MIN/(i+1), rand]
; Terminate when INT_MIN/(i+1) - rand < 0
SUB
JMP compare
end: ; 5.0
EXT
print_begin: ; 6.0
POP
; Print the string.
; DP2 + POP is shorter than PSI #1 + IDX
DP2
POP
print_loop: ; 6.6
BNG print_done
DUP
; INC + INC is shorter than PSI #2 + ADD
INC
INC
IDX
PTC
POP
DEC
JMP print_loop
; Print a separator, then loop back.
print_done: ; 8.0
PSC ','
PTC
POP
POP
JMP check_term


I have a feeling that this can be shrunk, as there's a significant amount of unused space, but I haven't figured anything out yet.

JavaScript (Node.js), 40 bytes

x=>Array(0|.5/Math.random()).fill(x)+','


Try it online!

Act same

i=1;while((0<shuf -i0-$i -n1));do echo$1;i=$((i++));done  Try it online! While is a better tool for this job TI-BASIC, 24 22 bytes -2 thanks to @lirtosiast :Prompt Str1 //4 bytes :While randInt(0,Ans+1 //9 bytes :Disp Str1 //4 bytes :Ans+1 //4 bytes :End //1 byte  Since all non-zero values are truthy, taking a random integer in between 0 and n-1 will give a random boolean with the correct probability. • Why not Ans instead of A? Commented Jul 11, 2017 at 1:30 • @lirtosiast Either works, but they have the same byte count and there is no reason to use Ans over A. A takes up less screen space, so I chose it. Commented Jul 15, 2017 at 16:41 • I was thinking you could avoid the →A, since you don't use Ans for anything else, and both Ans and A default to 0. Commented Jul 15, 2017 at 22:40 • @lirtosiast Ah, OK, thanks. Commented Jul 16, 2017 at 0:36 Runic Enchantments, 20 bytes i0q11+:'RA0=?;S:$S4?


Try it online!

Note that input is implicitly split on whitespace characters, so they need to be escaped.

Explanation

>                        Implicit entry
i0q1                    Read input and set up stack
1+                  Increment counter (value needs to be 2 for first loop)
:'RA0=            Generate random value (non destructive to stack) and compare with 0
?;          If *not* 0, terminate
S:\$S      Otherwise duplicate and print string
4?    Skip next 4 instructions (implicit loop)
`

Newline variant, as printing a whitespace character as a separator costs an extra byte.