Yeah, that's why I said in the extreme case you have to participate in all the volume. Of course randomly trading doesn't prove that you achieve VWAP, but I'm just saying that it's probably not terribly far off.
I can say with a great deal of confidence that a "random" VWAP algorithm would, on average, suck.
Many brokers will guarantee an execution at VWAP. It's a competitive business. The last time I put in such an order, I traded a double-digit percentage of the day's volume and paid 10bp commission (0.10%).
Plus, if you are dealing with a large broker they may just cross your order with an offsetting order (or their own position, execute nothing in the market and keep the entire premium.