The timing and dynamics of many diverse behaviors of mammals, e.g., patterns of animal foraging or human communication in social networks exhibit complex self-similar properties reproducible over multiple time scales. In this paper, we analyze spontaneous locomotor activity of healthy individuals recorded in two different conditions: during a week of regular sleep and a week of chronic partial sleep deprivation. After separating activity from rest with a pre-defined activity threshold, we have detected distinct statistical features of duration times of these two states. The cumulative distributions of activity periods follow a stretched exponential shape, and remain similar for both control and sleep deprived individuals. In contrast, rest periods, which follow power-law statistics over two orders of magnitude, have significantly distinct distributions for these two groups and the difference emerges already after the first night of shortened sleep. We have found steeper distributions for sleep deprived individuals, which indicates fewer long rest periods and more turbulent behavior. This separation of power-law exponents is the main result of our investigations, and might constitute an objective measure demonstrating the severity of sleep deprivation and the effects of sleep disorders.