OOC: Actually I think they always spawn with one short stack, and it's usually the Khan's stack. Not sure why that is, but it's how I generally start the war, by taking out the mini-stack.

I think they'll fight the Byzantines at Edessa, after they gather the rest of the Horde, which hasn't entered yet, but there are no guarantees.