probability or statistics - Generate two random numbers with constraints

I want to generate two random numbers, $p$ and $q$, between $0.5$ and $1$.

They are connected by the constraint $1/(2q) > p$.

How do I generate $p$ and $q$?

Answer

Assuming you just ommitted the parentheses and meant $1/(2q) > p$, then this works

q = RandomReal[{0.5, 1}]

p = RandomReal[{0.5, 1/(2 q)}]

Edit: The above code will generate 2 random numbers that satisfy the given criteria, they won't be sampling the same distribution.

qlist = RandomReal[{0.5, 1.0}, 10000];
plist = RandomReal[{0.5, 1/(2 #)}] & /@ qlist; 
ListPlot[ Transpose[{qlist, plist}]]

You see that the first variable samples {0.5,1.0} uniformly while the other does not. But the inequality is symmetric, and can be written $1/(2p)>q$ so that isn't right. rhermans's answer fixes this, but it runs unreasonably slow on my machine. For example, generating a list of 1000 pairs takes about 100 seconds for me using ImplicitRegion and RandomPoint.

But I can do it in about a tenth of a second using this inelegant code

list2 = Reap[
     i = 0;
     While[
      i < 10001,
      test = RandomReal[{0.5, 1.0}, 2];
      If[test[[1]] < 1/(test[[2]] 2), i++; Sow[test]];
      ]
     ][[2, 1]]; // AbsoluteTiming
ListPlot@list2