Jelly,  10  5 bytes

ṗJẎQX

A monadic Link accepting a list of characters which yields a list of characters.

Try it online!

How?

ṗJẎQX - Link list of characters    e.g.  aabc

 J    - range of length                  [1,2,3,4]

ṗ     - Cartesian power (vectorises)     [[a,a,b,c],[aa,aa,ab,ac,aa,aa,ab,ac,ba,ba,bb,bc,ca,ca,cb,cc],[aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,baa,baa,bab,bac,baa,baa,bab,bac,bba,bba,bbb,bbc,bca,bca,bcb,bcc,caa,caa,cab,cac,caa,caa,cab,cac,cba,cba,cbb,cbc,cca,cca,ccb,ccc],[aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,bbaa,bbaa,bbab,bbac,bbaa,bbaa,bbab,bbac,bbba,bbba,bbbb,bbbc,bbca,bbca,bbcb,bbcc,bcaa,bcaa,bcab,bcac,bcaa,bcaa,bcab,bcac,bcba,bcba,bcbb,bcbc,bcca,bcca,bccb,bccc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,cbaa,cbaa,cbab,cbac,cbaa,cbaa,cbab,cbac,cbba,cbba,cbbb,cbbc,cbca,cbca,cbcb,cbcc,ccaa,ccaa,ccab,ccac,ccaa,ccaa,ccab,ccac,ccba,ccba,ccbb,ccbc,ccca,ccca,cccb,cccc]

  Ẏ   - tighten                          [a,a,b,c,aa,aa,ab,ac,aa,aa,ab,ac,ba,ba,bb,bc,ca,ca,cb,cc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,aaa,aaa,aab,aac,aaa,aaa,aab,aac,aba,aba,abb,abc,aca,aca,acb,acc,baa,baa,bab,bac,baa,baa,bab,bac,bba,bba,bbb,bbc,bca,bca,bcb,bcc,caa,caa,cab,cac,caa,caa,cab,cac,cba,cba,cbb,cbc,cca,cca,ccb,ccc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,aaaa,aaaa,aaab,aaac,aaaa,aaaa,aaab,aaac,aaba,aaba,aabb,aabc,aaca,aaca,aacb,aacc,abaa,abaa,abab,abac,abaa,abaa,abab,abac,abba,abba,abbb,abbc,abca,abca,abcb,abcc,acaa,acaa,acab,acac,acaa,acaa,acab,acac,acba,acba,acbb,acbc,acca,acca,accb,accc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,baaa,baaa,baab,baac,baaa,baaa,baab,baac,baba,baba,babb,babc,baca,baca,bacb,bacc,bbaa,bbaa,bbab,bbac,bbaa,bbaa,bbab,bbac,bbba,bbba,bbbb,bbbc,bbca,bbca,bbcb,bbcc,bcaa,bcaa,bcab,bcac,bcaa,bcaa,bcab,bcac,bcba,bcba,bcbb,bcbc,bcca,bcca,bccb,bccc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,caaa,caaa,caab,caac,caaa,caaa,caab,caac,caba,caba,cabb,cabc,caca,caca,cacb,cacc,cbaa,cbaa,cbab,cbac,cbaa,cbaa,cbab,cbac,cbba,cbba,cbbb,cbbc,cbca,cbca,cbcb,cbcc,ccaa,ccaa,ccab,ccac,ccaa,ccaa,ccab,ccac,ccba,ccba,ccbb,ccbc,ccca,ccca,cccb,cccc]

   Q  - de-duplicate                     [a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,bca,bcb,bcc,caa,cab,cac,cba,cbb,cbc,cca,ccb,ccc,aaaa,aaab,aaac,aaba,aabb,aabc,aaca,aacb,aacc,abaa,abab,abac,abba,abbb,abbc,abca,abcb,abcc,acaa,acab,acac,acba,acbb,acbc,acca,accb,accc,baaa,baab,baac,baba,babb,babc,baca,bacb,bacc,bbaa,bbab,bbac,bbba,bbbb,bbbc,bbca,bbcb,bbcc,bcaa,bcab,bcac,bcba,bcbb,bcbc,bcca,bccb,bccc,caaa,caab,caac,caba,cabb,cabc,caca,cacb,cacc,cbaa,cbab,cbac,cbba,cbbb,cbbc,cbca,cbcb,cbcc,ccaa,ccab,ccac,ccba,ccbb,ccbc,ccca,cccb,cccc]

    X - uniform random choice

05AB1E, 6 bytes

ā€ã˜ÙΩ

Try it online!

Explanation

ā       # push [1 ... len(input)]

 ۋ     # apply repeated cartesian product on each and input

   ˜    # flatten

    Ù   # remove duplicates

     Ω  # pick random string

Perl 6, 35 33 bytes

-2 bytes thanks to nwellnhof

{pick $_∪[X~] $_ xx$_:}o*.comb

Try it online!

Explanation:

{                      }o*.comb  # Anonymous code block

         [ X~] $_ xx$_   # Find all combinations with repetition of the input

                        # And the prefixes of each, excluding the single chars

      $_∪                # Set union the input characters with the list

 pick                 :  # And pick a random string from the set of strings

Brachylog, 8 bytes

⊇ᶠbṛ;?ṛw

Try it online!

Prints output directly instead of constraining the output variable, because for some reason this actually fails without the w at the end. Originally this used ≠ and the ∈& backtracking hack I used to implement bogosort, but I realized that it would be far saner to just use b instead.

       w    Print

      ṛ     a random one of

     ?      the input

    ;       or

   ṛ        a random element of

 ᶠ          every

⊇           sublist of

            the input

  b         except the first one (which would be the input).

Python 2, 111 121 bytes

lambda s:choice(g(list(set(s)),len(s)))

from random import *

g=lambda s,n:s+(n>1and[c+k for k in g(s,n-1)for c in s]or[])

Try it online!

Takes any iterable (list, set, string, etc.) of either distinct characters or non-distinct characters as input. Outputs a non-empty string with the required distribution.

g is a recursive function to generate a list of compliant strings.

Wolfram Language (Mathematica), 41 bytes

""<>#&@*RandomChoice@*Subsets@*Characters

Try it online!

C (gcc), 68 65 bytes

f(s,i)char*s;{for(;i<strlen(s);i++)rand()&1?putc(s[i],stdout):0;}

Try it online!

R, 72 bytes

sample(t<-unique(s<-scan(,"")),sample(n<-length(s),p=length(t)^(1:n)),T)

Try it online!

Input and output are vectors of characters. All possible outputs have equal probability.

Explanation (ungolfed version):

s<-scan(,"")                         # takes input as vector of characters

n<-length(s)

t<-unique(s)

sample(t,                           # sample uniformly at random from the list of unique characters

       sample(n,p=length(t)^(1:n)), # with length k in 1..n chosen randomly such that P[k] is proportional to length(t)^k

       T)                           # the sampling is with replacement

Charcoal, 34 bytes

≔Φθ⁼κ⌕θιη≔⊕‽ΣＥθＸＬη⊕κζＷ櫧ηζ≔÷⊖ζＬηζ

Try it online! Link is to verbose version of code. Explanation:

≔Φθ⁼κ⌕θιη

Extract the unique characters of the input. Let's call the number of unique characters n.

≔⊕‽ΣＥθＸＬη⊕κζ

Calculate the number of combinations for each possible length and take the sum. Then, pick a random number between 1 and this number (inclusive). This ensures that all combinations are equally likely (within the accuracy of the random number generator).

Ｗ櫧ηζ≔÷⊖ζＬηζ

Convert the number into bijective base n, using the unique characters as the digits.

MATLAB / Octave, 110 bytes

Choose a random permutation of a subset of the input letters (with repetitions), whose random length is based on the probability of generating a word with that length.

@(a)a(randi(numel(a),[find(cumsum(numel(a).^[1:numel(a)])>=randi(sum(numel(a).^[1:numel(a)])),1,'first'),1]));

Try it online!

T-SQL, 222 bytes

This creates all combinations of each unique character with recursive sql, then picks a random row from the distinct combinations.

DECLARE @ varchar(max)='T-SQL';



WITH C as(SELECT DISTINCT substring(@,number+1,1)x

FROM spt_values

WHERE'P'=type and len(@)>number),D

as(SELECT x y

FROM c UNION ALL

SELECT y+x

FROM C JOIN D

ON len(y)<len(@))SELECT top 1*FROM D

GROUP BY y

ORDER BY newid()

Note the online version will always give the same result unlike MS-SQL Studio Management. This is because newid() always returns the same value in the online testing. This should work in Studio Management.

Try it online ungolfed version

Python 2, 124 bytes

lambda s:g(list(set(s)),len(s))

from random import*

g=lambda s,n:choice(s)+(random()*~-len(s)**(n)>~-len(s)and g(s,n-1)or'')

Try it online!

A different approach: instead of first constructing a list of all compliant strings and choosing one at random, this approach randomly decides to continue extending the string or stopping.

This again has to deal with the exacting input requirements, at a cost of 31 bytes; but the function of interest g takes a list s of characters to be used, and an integer n which is the maximum length of the returned string.

As an example, consider the set of characters ['a','b'] and suppose we want to generate random strings of length 1, 2, or 3.

Then if we randomly choose 'a' as the starting character, the possible strings which could be returned are:

a

 aa

  aaa

  aab

 ab

  aba

  abb

shown above in 'tree' form, which is a total of 1 + 2 + 2*2 = 2^0 + 2^1 + 2^2 = 7 strings. So if we generate a string a; then 1/7 of the time we should stop and return 'a', and 6/7 of the time we should add further to the string - then the distribution will be uniform in the way desired.

More generally, if n is maximum length of the string and x is the number of characters in the set, then the number of strings starting with some given character is going to be:

$$h(n)=sum_{i=0}^{n-1} x^i$$
$$h(n)=1+x+x^2+x^3...+x^{n-1}$$

For x>1 (guaranteed by OP's rule 'at least two distinct...'), we have:

$$h(n)(x-1)=(1+x+x^2+x^3...+x^{n-1})(x-1)=x^n-1$$
$$h(n)=frac{x^n-1}{x-1}$$

So to decide whether we should continue extending our string, let p be a random number in [0,1); then we should recurse only if any of these equivalent statements are true:

$$p>frac{1}{h(n)}$$
$$p>frac{x-1}{x^n-1}$$
$$p(x^n-1)>x-1$$

of which g is the golfed implementation.

J, 27 bytes

[:(?@#{])@;[:,@{&.>#<@#"{<

Try it online!

standard formatting

[: (?@# { ])@; [: ,@{&.> # <@#"1 _ <

explanation

Eg, for the string 'abc' we first use #<@#"{< to create:

┌─────┬─────────┬─────────────┐

│┌───┐│┌───┬───┐│┌───┬───┬───┐│

││abc│││abc│abc│││abc│abc│abc││

│└───┘│└───┴───┘│└───┴───┴───┘│

└─────┴─────────┴─────────────┘

We then take the cartesian product of each of these {, flatten the results, and finally remove the outer boxing ;.

(?@#{])@ takes a random result from that list.

Note: TIO will return the same result every time, but in a normal J REPL it will be random.

C# (Visual C# Interactive Compiler), 126 bytes

a=>{var s=new Random();int d=a.Length;return Enumerable.Range(1,s.Next(1,d)).Select(x=>a.Distinct().ToList()[s.Next(0,d-1)]);}

Try it online!

Forth (gforth), 68 bytes

include random.fs

: f dup random 1+ 0 do 2dup random + 1 type loop ;

Try it online!

Explanation

• Get a random number between 1 and string-length


• Loop that many times


• For each iteration
  
  
  
  
  • Get a random number between 0 and string length - 1
  
  
  • Add that to string starting address and output the character at that address
  
  
  
  

Code Explanation

include random.fs           include the library file needed to generate random numbers

: f                         start a new word definition

  dup                       duplicate the string-length

  random 1+                 get the length of the new string, make sure it starts from 1

  0 do                      start a loop of that length

    2dup                    duplicate the starting address and string length

    random +                get a number from 0 to string-length and add it to the address

    1 type                  output the character at that address

  loop                      end the loop

;                           end the word definition

Java 131 bytes

void k(String a){a.chars().forEach(v->{int z=(int)(Math.random()*(a.length()+1));if(z<a.length())System.out.print(a.charAt(z));});}