Before reaching their targets, sequence-specific DNA-binding proteins nonspecifically bind to DNA through electrostatic interactions and stochastically change their locations on DNA. Investigations into the dynamics of DNA-scanning by proteins are nontrivial due to the simultaneous presence of multiple translocation mechanisms and many sites for the protein to nonspecifically bind to DNA. Nuclear magnetic resonance (NMR) spectroscopy can provide information about the target DNA search processes at an atomic level. Paramagnetic relaxation enhancement (PRE) is particularly useful to study how the proteins scan DNA in the search process. Previously, relatively simple two-state or three-state exchange models were used to explain PRE data reflecting the target search process. In this work, using more realistic discrete-state stochastic kinetics models embedded into an NMR master equation, we analyzed the PRE data for the HoxD9 homeodomain interacting with DNA. The kinetic models that incorporate sliding, dissociation, association, and intersegment transfer can reproduce the PRE profiles observed at some different ionic strengths. The analysis confirms the previous interpretation of the PRE data and shows that the protein's probability distribution among nonspecific sites is nonuniform during the target DNA search process.