This work studies the constrained optimal execution problem with a random market depth in the limit order market. Motivated from the real trading activities, our execution model considers the execution bounds and allows the random market depth to be statistically correlated in different periods. Usually, it is difficult to achieve the analytical solution for this class of constrained dynamic decision problem. Thanks to the special structure of this model, by applying the proposed state separation theorem and dynamic programming, we successfully obtain the analytical execution policy. The revealed policy is of feedback nature. Examples are provided to illustrate our solution methods. Simulation results demonstrate the advantages of our model comparing with the classical execution policy.