This paper proposes a novel probabilistic approach for appearance-based person reidentification in non-overlapping camera networks. It accounts for varying illumination, varying camera gain and has low computational complexity. More specifically, we present a graphical model where we model the person’s appearance in addition to camera illumination and gain. We analytically derive the solutions for the person’s appearance and camera properties, and use a novel constant time Gibbs sampling scheme to estimate the identification labels. We validate our algorithm on two indoor datasets and perform a comparative analysis with existing algorithms. We demonstrate significantly increased re-identification accuracy in addition to significantly reducing the computational complexity on our datasets.