Sampling in PostgreSQL
Corrective

If instead of generating one random value we generate S random values
where S is the sample size, then order all of the random generated
values, it will be sampling with replacement. (I don't know if I am right.)

You are wrong in two points.

Your original query does not generate &quot;one random value&quot;. random() is a volatile function that is called for every row. Then all rows are sorted by the result, that's why this is hugely inefficient for big tables.
Accordingly, the approach &quot;if we generate S random values ...&quot; is going nowhere. You have to &quot;granulate&quot; random rows to matching &quot;row numbers&quot; - either existing IDs or surrogate numbers. That's what I am going to demonstrate.

I know you said:

At this point I don't mind about the performance of the query.

So @ypercube's answer is correct as usual. But my heart is bleeding. There are much faster ways.
Assuming the worst case that you don't know anything about the table.
Attach a sequential number to each row in arbitrary order, then you can select random rows reliably, multiple times if you want. The table is scanned once, which is still expensive for huge tables and small samples, but much better than scanning n times:
WITH t AS (SELECT *, row_number() OVER () AS rn FROM tbl)
SELECT * FROM (
    SELECT trunc(random() * (SELECT max(rn) FROM t))::int + 1 AS rn
    FROM   generate_series(1, 10) g
    ) r
JOIN   t USING (rn);

Each row has the same chance to be selected any number of times.
If you have an ID column with few or no gaps there are much faster options for big tables:

Best way to select random rows PostgreSQL