The popularity of mobile devices and location-based services (LBS) has created great concern regarding the location privacy of their users. Anonymization is a common technique that is often used to protect the location privacy of LBS users. Here, we present an information-theoretic approach to define the notion of perfect location privacy. We show how LBS's should use the anonymization method to ensure that their users can achieve perfect location privacy. First, we assume that a user's current location is independent from her past locations. Using this i.i.d model, we show that if the pseudonym of the user is changed before $O(n^{\frac{2}{r-1}})$ observations are made by the adversary for that user, then the user has perfect location privacy. Here, n is the number of the users in the network and r is the number of all possible locations that users can go to. Next, we model users' movements using Markov chains to better model real-world movement patterns. We show that perfect location privacy is achievable for a user if the user's pseudonym is changed before $O(n^{\frac{2}{|E|-r}})$ observations are collected by the adversary for the user, where |E| is the number of edges in the user's Markov chain model.