Generating square-free words efficiently

We study a simple algorithm generating square-free words from a random source. The source produces uniformly distributed random letters from a k  -ary alphabet, and the algorithm outputs a (k+1)(k+1)-ary square-free word. We are interested in the “conversion ratio” between the lengths of the input random word and the output square-free word. For any k≥3k≥3 we prove the expected value of this ratio to be a constant and calculate it up to an O(1/k5)O(1/k5) term. For the extremal case of ternary square-free words, we suggest this ratio to have a constant expectation as well and conjecture its actual value from computer experiments.