We propose a new instruction, branch-on-random, that is like a standard conditional branch, except rather than specifying the condition on which the branch should be taken, it specifies a frequency at which the branch should be taken. We show that branchon-random is useful for reducing the overhead of program instrumentation, via sampling. Specifically, branch-on-random provides an order-of-magnitude reduction in execution time overhead compared to previously proposed software-only frameworks for instrumentation sampling. Furthermore, we demonstrate that branch-on-random can be cleanly architected and implemented simply and efficiently. For simple processors, we estimate that branch-on-random can be implemented with 20 bits of state and less than 100 gates; for aggressive superscalars, this grows to less than 100 bits of state and at most a few hundred gates.