When allocating indivisible objects, agents might have equal priority rights for some objects. A common practice is to break the ties using a lottery and randomize over deterministic allocation mechanisms. Such randomizations usually lead to unfairness and inefficiency ex-ante. We propose a concept of ex-ante fairness and show the existence of an agent-optimal ex-ante fair solution. Ex- ante fair random allocations are generated using "allocation by division", a new method of generating random allocations from deterministic allocation mechanisms. Insights from the two-sided matching theory and the recent random assignment literature are unified and extended. The set of ex-ante fair random allocations forms a complete lattice under first-order stochastic dominance relations. The agent-optimal ex-ante fair mechanism includes both the deferred acceptance algorithm and the probabilistic serial mechanism as special cases.