Aceto, 24 bytes

^




OYpO
r^`!
?d0=   >

Takes an infinite stream of lines and yields them in a random order. Every element has a chance of occurring at any random point.

We start with a ? in the bottom left corner, which moves us in a random direction. If that is down or left, we get pushed right back.

If we're moved upwards, we read a value, shuffle the stack (Y), and jump back to the Origin.

If we're moved to the right, we duplicate the top stack value, push a 0 and test for equality (since we're reading strings, we can't ever have the integer 0). If the values are equal, that means we've reached the bottom of the stack (from which we don't want to print). We negate the comparison (!), and print only if (`) the things were not equal. Then we also jump back to the Origin.

JavaScript, 59 bytes

for(l=[0];;)l.splice(1/Math.random(),1,prompt()).map(alert)

Try it online!

A number may be moved infinite far. Randomness would choose first element for high prob so each element would get popped

x86 machine code, 32-bit linux, 37 36 bytes

Disassembly:

0:  6a 21                   push   0x21
2:  5f                      pop    edi
3:  50                      push   eax
4:  b0 03                   mov    al,0x3
6:  31 db                   xor    ebx,ebx
8:  89 e1                   mov    ecx,esp
a:  99                      cdq
b:  42                      inc    edx
c:  cd 80                   int    0x80
e:  4f                      dec    edi
f:  75 f2                   jne    0x3
11: 58                      pop    eax
12: 0f c7 f5                rdrand ebp
15: 83 e5 7c                and    ebp,0x7c
18: 87 04 2c                xchg   DWORD PTR [esp+ebp*1],eax
1b: 50                      push   eax
1c: 47                      inc    edi
1d: b0 04                   mov    al,0x4
1f: 43                      inc    ebx
20: cd 80                   int    0x80
22: eb e0                   jmp    0x4

Starts by reading 32 bytes into a buffer. Then, after reading each additional byte, displays a random byte from the buffer and replaces it with the just-read byte.

Assembly code:

.global _start

.section .text
_start:

.intel_syntax noprefix
        push 33
        pop edi
read_loop:
        push eax
read_loop1:
        mov al, 3
        xor ebx, ebx
        mov ecx, esp
        cdq
        inc edx
        int 0x80
        dec edi
        jnz read_loop

        pop eax
        rdrand ebp
        and ebp, 124
        xchg eax, [esp + ebp]
        push eax
        inc edi

        mov al, 4
        inc ebx
        int 0x80

        jmp read_loop1

Assemble using the following command:

gcc -g -c -m32 file.s && ld -m elf_i386 file.o -o prog

SmileBASIC, 61 58 bytes

@L
B$=B$+R()IF I>8THEN R=RND(9)?B$[R];:B$[R]="
I=I+1GOTO@L

Each character of the infinite list is added to the end of the buffer. When the buffer length is 11, a random character is printed and removed.

Function R generates the next character.

Javascript, 78 bytes

for(l=[];;){l.push(prompt());l.length==10&&alert(l.splice(Math.random()*9,1))};x.sort(()=>Math.random()<0.5);alert(x)}

Uses the same method as xnor's answer.

R, 70 bytes

x=NULL;repeat{x=sample(c(x,scan()));if(sum(x|1)>9){cat(x[1]);x=x[-1]}}

Starts with an empty vector x. In an infinite loop, it takes a new value from STDIN, then shuffles the vector. Then it checks if the length of the built up list is 10 or higher. If it is, it can start printing. This way the vector has a buffer of 10 inputs, each getting shuffled in every iteration. So it is possible for input to be printed 10 places earlier, and infinitely many places later (following a geometric distribution with p=1/10). When the buffer is long enough, the first element is printed and removed from the vector.

Ruby, 43 bytes

l=[];loop{l<<gets;l[9]&&$><<l.shuffle!.pop}

My original answer used a lazy-evaluated infinite list, but this is shorter. Oh well.

Bash, 17 bytes

xargs -n9 shuf -e

Try it online!

xargs continuously takes 9 letters from STDIN and sends them to shuffle

an infinite list can be generated by:

yes {a..z}

which prints a b c d e .. z infinite times.

Test could be done by:

yes {a..z} | xargs -n9 shuf -e 

05AB1E, 13 bytes

[I)˜¼¾T›i.rć,

Try it online! (modified to take 20 elements)

[             # Infinite loop
 I)˜          # Add the next element from input to the array
    ¼         # Increment the counter variable
     ¾T›i     # If the counter variable is greater than 10...
         .r   #   Get a random permutation of the array
           ć, #   Print and remove the first element 

C, 214 bytes

c;i;char B[19]={0};char*I;
S(p,q){if(B[p]-B[q])B[p]^=(B[q]^=(B[p]^=B[q]));}
R(n){while(n--)putchar(B[c]),B[c]=*I,c=++i%19,I++;}
main(c,v)char**v;{srand(time(0));I=v[1];R(19);i=9;for(;;){S(i,rand()%19);R(1);i=++i%19;}}

How it works

Try Online (UNIX)

#include <stdio.h>
#include <unistd.h>

// animation speed
#define ANIMATION_SLOW 600000
#define ANIMATION_NORMAL 400000
#define ANIMATION_FAST 200000

c;i;char Buffer[19]={0};char*input;
Swap(p,q){if(Buffer[p]!=Buffer[q])Buffer[p]^=(Buffer[q]^=(Buffer[p]^=Buffer[q]));}
Read(n){while(n-->0)putchar(Buffer[c]),Buffer[c]=*input,c=++i%19,input++;}

main(int argc, char**argv)
{
    // initialization
    srand(time(0));
    input=argv[1];
    Read(19);i=9;

    // shuffle machine
    while(1)
    {
        usleep(ANIMATION_NORMAL);
        Swap(i,rand()%19);
        Read(1);
        i=++i%19;
    }
}

Prolog, 70 bytes

s(L):-get0(C),(length(L,9)->random_select(H,L,R),put(H);L=R),s([C|R]).

Alice, 7 bytes

a&IdU,O

Try it online!

This should work on an infinite input with infinite time and memory, but it's not so easy to test in practice :)

Explanation

a&I         Push 10 characters from the input to the stack.
     d        Push the depth of the stack.
      U       Pop a number (d), push a random number in [0,d)
        ,       Pop a number (n), move the element which is n elements below the top to the top of the stack.
         O    Output the character on top of the stack.

                Execution loops back to the beginning of the line.

At each iteration 10 characters are read from input and only one goes to the output, so memory usage increases linearly during execution. With a finite input this quickly reaches EOF, from which ten -1 will be pushed to the stack at each iteration. Trying to output -1 as a character has no effect, but it's unlikely that all the characters of the input will be printed in a reasonable amount of time.

Position i of the output can be taken by any character in the input up to position 10i, this complies with the challenge requiring at least a range from i-9 to i+9.

MATL, 11 bytes

`rEkN*?D}iT

Try it online!

Port of histocrat's Befunge answer.

Explanation: (Thanks to Luis Mendo for -1 byte)

`         T % Start do-while (`) .... true (T)
 rEk        % 50-50 chance of outputting or inputting:
            %   Random number between 0...1, multiplied by 2 and converted to logical. 
    N       % Check if there is anything on the stack to output
     *?     % If there is anything on the stack and (*) we want to output:
       D    % Output. Sadly, D errors when the stack is empty, requiring the N*
        }i  % Else, input.

This outputs almost surely in finite time, and almost surely requires only finite memory.

For completeness, here is a 15-byte version which keeps a 10-element buffer and outputs a random element from that:

`htnt9>?Yr&)wDT

I like this version for the very idiomatic (as far as golfing languages can be idiomatic) tn...Yr&), which pops a random element from the list and returns the list without that element. However, the particular logistics of this challenge add a lot of bytes (the required w for the display, the t9>? to check if the list is full enough...).

S.I.L.O.S, 149 bytes

b=1
lbla
x=15+b*15
b=1
lblb
readIO
queue 0 i
x-1
if x b
a=0
lblx
x=rand*2
queuePop 0
if x X
printInt m
a+1
b=15-a
if b x
GOTO a
lblX
queue 0 m
GOTO x

Try it online!

Essentially it keeps taking input (on the online interpreter through arguments, but on the offline official interpreter it will allow you type into the console (infinitely)) in blocks of 15 at a time (30 the first block).

It loads the input into a temporary queue and picks a lucky 15 (randomly, but not equally distributed in terms of probablity or distribution).

The rest remain in as new inputs fill the queue, the first input could be shuffled all the way to the end, (basically I think the characters follow a normal distribution). It's interesting to note that this program is only twice as verbose as python and perhaps "golfier" than Java.

To better see the results I have a non-compliant version which takes input as a string (however it can only take in 8,000 or so characters).

Try it online!

Just for fun, here is this post fed through the string version.

 [.L.Ooy" 9beS.I.S],"14 ts  b1
 nly

  =ll
   x=1b 15   1
5b  a*b=  lb  rd#  + lb eaI O    e 
 x
 ifquu   
1 0x b
   =

    e
0
   i lblxa -d*2
    quu   x=rn 
   x Xea p0
   pnInt o r   a
   mf =   iePit
  ba 1
   GTO  1 f b x+ Oa


 qe -lblX u0 m    GOOue  
[rlT 

 tnn5 !I.STii][S.LO ie

htpsgthyx]:iub.om/jhujh.. tcraa.I.O.o /TytonieSu:wl/.L lnn!:tt/iS
[ in hsto.un/nuslprxRUCoDsio/]:e#NzZn6j4c/2xNQFnF7y0aLzkrosd9Dov2yxJNx774HBrgPUdi9CySI09sCLw5TJwB7jlB1XVeQFE7m1VMsIQvDOjBmdtME3umNzYXs9unFbqRamVDfUDw@RT3NHoL7/i04bz16DCoP4eulOU7jPD8OmYjATpynkuMDuBPYmtnIJzseyyhaNkMyQgXG2R782vqMDIiUm6Kq4Q3mJkxlUsR1rrldPw./l28Z SL.XS – IONuscOT "
senallyxMz.stiitkp ingN"
 eestaint on heeInliinrprt (oe e  toghr tetgpnmntuon eruEuut r h ofi off,bhenecil inretea.atr  ialoks tirilw upeitfleptly ty  honso (e oote cenfine iwllbc 15 atly) nitloo  aim( te)nikfte3 firs bck)
hs 0It te 
 lodshipo alauttt.mpra quuet i reanicks a lck eooy d  randomyn p 15( u o equl,unbtty drbutedaynistinems oftrly ordisrprob ill abition h  ibttmin.Tet ri)
 a nwit u ree nusfil th queusen 
pte ftip,ae uldsfuesis ob hl rlelth weual  t tc hdyoend,f tbaaly thi an elnkhecarcthe(sc h o  noreiItrolwaaldibtio  lmiru.t' iereaf ) tsng tetntiottssht prasnon  hogIms only twieatisi s vroscpythonadprs a hbapolfi" e r n e ehanava.
 tte s/"gt 
obterelIe  tsvea non-omhTrehs  a plntvesion hcahihk ine teuts sriprics at rwvritcaw aa g(hoee n onl kein n00 orscat ,0  cter).

[Tyauoas  it onine!hrhrys:.ru]p//o/lsslo#jVd(tinnexi3E@KDpit/LrhtwXwVEUuscxPmJjFFCaNimMzlHiQEcMmdVIT7vqs8mNgxU3mD/J1AwX q/ivbao1j@nb4I6/m93655bThmb4cy5TUX3xvI018cZzrXItuO5B@NX5JD/HzyE@G@D5eqrGem3l0HPGRutZfpi2PzVA@d3CVRTm4zJxnZdcFSTEO0JOT9KhDI6byjnLhS0cNmGz7hJrTdAgORT8Ndvv7DgZSbJdkp9v5al8qMyNCb9tXe0ChrShXRTOt@7fFgV3zTkbVbsD@JpKina2oKgNVakjsjLCpD29u7l0XVRWalVTyArF1FqypQAxXb/BedqUqpJGOPVyxOjLj0jXup8cE277L2I6@lSowK5pA7nGldRBiJwyKxF6z2c3kW/sJ4EYBbbpSuBxs55nyI9sdnu@nJJeGqtKprGEUbc6NDGMjjO2tN/KuKTWh2WWbbRRLVaq/P6KqkoMNWGRgTQZLlbXfQI050bY0rz0xmzCVZ4vowjpV0dCmkDFq0VNa5GSDzVn5Qw7idwPTxu5xTAtLQCDN/YIApfAn4dsDmYksCqUU27sRggpzRK4SmdjmPUPQO4j5FmgHMFRWS2eI1CfA2YIcf7JlylFjdZypVTH0IJu4ZJHiUviyBFKqhrkCjgXAAB8d710NhHgDwcJksuvPPprcfzHPTaJGFX8OIExW/cBZjaPiY7a4WD6rTYmOouBVucROlwvuBJiHWdJQjjbobNGTd7M1P6z8dw/A@GU02hgjCcrjjQHkAdS6r7UjQ6wAPqB@sIgxkKcbZDixeWS6mn160CKQpn7aUwGLK22u9I0oX6YIwPMhFVaX5uYon0AyoNTCZvnmtilVhV3/pgTGc7r39lIS5PmqM/NGnUSLnTw9eTJ7qqrNQKsJHz@Tt8mDZVWKCKTkBro1PuQAksDdN1yaVGiVXElRW9i5M11cINmxNGYAg9TD7sxtEDI2OkKMaBXgvO5dOplUQQIdpb2w66NePBScMmEnAX8ydGSiiHlss@hOLZzInnIoTevRtEm/TGHWOkly5ljMK4FkgDDSWCWBW3YwmEVYCIBV@GMIg3TZtGwMFWXVxQwBb5iD6PfS7h7Sric1ib5ZYIvW6n3tlaK7/6@3OAHy4LjOuW@tzaBP3@mFbJpHsVsQKPfeui/o1@aBcbZ4TK96T8tp3QjeA1vDXMKBIqdK@HZs2vsMlQE36YmrBEnVRUvAGNuCt44e0RB0sL0MkNu1Q5wOwliTT2JQzVrOnHAmSXIU//sqjdG6jdT2r1v@@lGjouzkGWoD4zhnzJBxo0OT6OTbBDgeDFRnY8TMXZbMPdxsCtbXeUxIBqST4VRwkpbgwChBcJxMx6hLIVZhfuylDvF1l26Nbl3xRLgQnatSCMigx@PCT6lcG1ebdk/86UBUFp9UkxjoCGSJnlxMtUdHf6IjkMnil5aua9L@xXsdHEKW@8JpVqlgKsr12bAKG2Typfv@Yy4CkUydETWphcdmdpWq7egtxqP8pYI2rSaSuYBwW0tNTdXn4qcjnZ9JKhuVwaWRycwCWt247LSflsCHsB3u0KoLTQJzL1uMl0duij/IF7LCc5FSpIPW7gcjOYj@jQdpQHv0WUz/IbMhS0XmFiWm1i0cTbxXjsjLxt6nGmQNQoKfREklc8pTFyHub7jUg8TR4QrZ2w3YjaLWNi@FFerCnNgY0LqgrA6qkWg8H/7Pv6YhtqeZzvoB0yD5Wm1eLL1Vf/SouI0Q/fox7eQlXieZB1F1v2/in/btqyVPtubWhDIKH8WaTlry43N6HgOEzX5HOjv1@lamBeZlJpqJnG3B2LZe8sXUafdAcVvVjBBlqxbEThCdjpelc7YVuYXOqM8MyVV3iPxbqYu@nmbHnoKpK1Eww11sA9aiwN8kMe0ioVO7qnucL1A8wHJ4wTsdltrm3CC4bpCd5hMhyDGXSdGgdKvnCKUpNB9nH@wXLgu5iUEcfJbDKZFjx6gI9i8fCcUFiQXxeSbKnwhT6@v/I6yS/Ew9k@tgI68/lO@4jjx0PZBpSo5vWLCDi4zb@TJejQQPtvlgde98MDGJ4vUW3T@iJTA89gGhUJIgy@MDBpaz3s7PT2ZIwStVANsxpCmhghh68huncD0VdumQt0lT/Su6HW3kMLFfo/FphQ0QhtoZ5iRN/@hZ/DmHq8UZEgiblprekkw1I366fMhePmDclSxirOlYH2Hwe3fom3aoe1@yaQYwi5ZPd2FcITXO7cu9@6tiHZJc7lKSB8e3/mXx34xYH/8F@TUxx/5vs5yHsYBL4ekscycqT1BnuV19/ "SFE/iRAIL.O NqUXAm. T3zDreu).S –IOxs."d

Perl 5, 39 bytes

38 bytes of code + -n flag.

print splice@F,rand 10,1if 9<push@F,$_

Try it online!

Add each element to @F array (with push@F,$_). When @F contains 10 elements (push returns the number of elements in the array, hence 9<push...), a random element is removed and printed (splice@F,rand 10,1 to remove the element, print to print it).
The output starts happening after then 10th element has been read. Hence, each element can start appearing at least 9 positions before its original one, and can be shifted to the right infinitely.

Befunge (quirkster flavor), 4 bytes

?,?~

, reads a character from the stream and pushes it onto the stack. ~ pops the top character from the stack (if present) and prints it. ? randomizes which command is executed next. So the algorithm here is "In an infinite loop, with equal probability either push a character or pop a character." I think this satisfies the requirements: a character can see arbitrarily many characters added above it in the stack, so it can move arbitrarily far to the right, and it can be printed when the stack is arbitrarily big, so it can move arbitrarily far to the left.

C (gcc), 94 bytes

L;i;f(s){srand(s);int B[9]={0};for(L=0;;)L>9&&putchar(B[i=rand()%10]),B[L>9?i:L++]=getchar();}

Try it online!

Ok, a TIO link doesn't make much sense. For ease of testing, I created the following C program that will output random ascii characters, or repeat an string infinitely.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main(int argc, char** argv){
    srand(time(NULL));
    if(argc < 1) {
        for(;;){
            printf("%c", rand() % 95 + 32);
        }
    } else {
        char* s = argv[1];
        int i = 0;
        for(;;){
            if(s[i] == 0)
                i = 0;
            printf("%c", s[i++]);
        }
    }
}

This program will be referred to as iro.

Program correctness

What I do here is read 9 values into a buffer. After this, random indices are chosen from this array and are outputted, then replaced by the next character in the stream.

Python 3, 78 bytes

from random import*
l=[]
while[shuffle(l)]:l[9:]and print(l.pop());l+=input(),

Try it online!

Takes input from STDIN (one per line), prints to STDOUT.

Keeps a buffer l of up to 10 elements. The buffer is shuffled with each step. When its length is 10, the last element is printed and removed.

If an element happens to be printed as soon as it was inserted, it has skipped ahead of 9 other elements waiting in the buffer, so it appears 9 spots left. An element can wait in the buffer arbitrarily long, so its position can move any amount right.

There doesn't seem to be a nice way to produce and remove a random element from a list. Shuffling seems like overkill. It's 2 bytes longer to use l.pop(randint(0,9)) (which uses that the list has 10 elements).

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(l.pop(randint(0,9)))

It's no better to do x=choice(l);l.remove(x).A language with poprandom like

poprandom = lambda l:l.pop(randrange(len(l)))

could very cleanly do

from random import*
l=[]
while 1:l+=input(),;l[9:]and print(poprandom(l))