I think based on your prestige, you have a certain "base" percentage chance of a band of mercenaries to establish contact with you. This is modified by 100% for each "mercenary building" like Brothel, Beer Hall, and Every-man's Unquestioning Outfitter (supply shop for mercs, thieves, and bandits). so with all three buildings your base percentage (20%?) plus an additional 300% of base ... which is 20 x 4, which is 80%.
World starts out with no mercenaries ... and then the bigger nations get and the larger armies get, Rogue companies of mercenaries begin to form. There would probably never be enough mercenaries to be larger than 10 or 20% of the worlds professional State-owned armies, although I think merchant civs could increase this somehow (where its more a value of percentage) and honestly this limitation seems un-needed to me. Anyways, more and more mercenary companies (and mercenary adventurers) come along, and for the Merc Company you hire them for a determined number of turns, hopefully turns and gold are determined via dialouge and influenced by Diplomatic skill. (such NPCs are best dealt with by Diplomatic skill, fellow Sovereigns however, I would prefer a thinking AI, wit vs wit). Perhaps Merc Adventurers are signed on for life, or until they route from combat (and miraculously don't die). Assasins can also be Hired the same way .. only assasins are Persistent (there are say, 10 assasins in the world, and over time they will level up, ect) .. and you only hire an assasin for a Mission. After the mission, they take their gold, their extra level, and go back to the market. Perhaps there is a way to permanently hire an assasin, or several assasins, but It would probably have to be something special, like owning the GrandMaster Assasin Guild House, or something similar. Such a person might be able to use their assasins as spies (although I would prefer Assasins merely exist in the ether when not on the job, as opposed to actively travelling the land, same with mercenaries, but I suppose either way works)