POSTGRESQL 9.4/9.5 - Select...for update one single random row on a large dataset with high Reads and Writes

I have a type of lottery system with random picks I am trying to optimize.

I have the following constraints:

• I need to apply the SELECT...FOR UPDATE only to rows where the deal_id is the current deal of my app (i.e i don't apply it it on the WHOLE table/on ALL the rows of the table, only on those where for example deal_id= 3 for example)
• I need to select only rows where available=true
• I need to output only 1 row (when a player buys a ticket I must go check these 1 million rows and RANDOMLY choose one for him (only one so many Stackoverflow solutions like here or TABLESAMPLE do not easily work)
• I have usually about 1 million rows that match deal_id = 3 (3 as an example) and available =true (out of a total of about 30M rows at any given time)
• I have very high READS and WRITES => about 50 to 100+ concurrent reads on the table and as a consequence same number approx of writes (as once chosen, available= true is changed to 'false' inside the SELECT..for UPDATE)
• I have a lock while the select/update on a row is being implemented. Now I'm using SELECT..FOR UPDATE with pg_try_advisory_xact_lock (and when postgresql 9.5 goes out of beta, I will use SKIP LOCKED)
• I need blazing fast speed. i target a query < 5ms

Here is my current query. It is a ARBITRARY PICK but now I want to change it/recreate it to have a want a RANDOM PICK (but avoid the usual random() limit 1 that need to go through all the 1M rows and is very slow, even maybe avoid offset(?) as it is notoriously slow on large datasets).

UPDATE tickets_rows s
        SET available = false
        FROM (
              SELECT id
              FROM   tickets
              WHERE  deal_id = #{@deal.id}
              AND    available
              AND    pg_try_advisory_xact_lock(id)
              LIMIT  1
              FOR    UPDATE
              ) sub
        WHERE         s.id = sub.id
        RETURNING     s.name, s.id

how to change this query to move from arbitrary pick to a RANDOM pick and with the fastest query possible?

I'd like if possible tangible query suggestions, that I will try in my app.