Throughout Coelho's The Alchemist, the concept of "maktub"—the idea that our destiny is already written—is endorsed by many characters. What is the difference between being controlled by fate or one's destiny, and discovering one’s "Personal Legend?"
Paulo Coelho's The Alchemist was actually written (after The Pilgrimage) in response to a spiritual awakening that the author experienced while on a five hundred mile religious pilgrimage.
It may not, therefore, come as a surprise that the question of predestination arises in this story that deals a great deal with one's faith, though not necessarily a specific religion. Coelho seems less interested in furthering the precepts of a particular branch of faith, as in declaring a unity that binds the entire world together despite people's differences.
The Calvinists (followers of John Calvin, a Protestant Reformer) believe that God predestines who will be saved and who will not be saved—before an individual is born. In other words, they believe that salvation is not free to everyone. There is nothing in the scriptures that supports this—quite the contrary. In fact, the entire Bible is filled with examples of God asking the Israelites to choose, and Jesus doing the same in his short years of ministry...followed thereafter by his apostles and followers who emphasized that every person in the world has a choice—and no one who chooses God's path will be turned away. This is very different than the notion of predestination.
Destiny is defined as...
...the predetermined, usually inevitable or irresistible, course of events.
And fate basically means the same thing...
...that which is inevitably predetermined; destiny...
The doctrine that God has foreordained all things, especially that God has elected certain souls to eternal salvation.
The sense of fate and destiny is that no matter what one does, he or she will end up as God has already decided he or she will. There is no sense of free will in either of these things. This is pivotal in understanding the distinction between fate and destiny, and a Personal Legend.
The difference between fate and destiny and one's Personal Legend is that with the first two, God's plan is fulfilled regardless of what one does. However, Coelho notes in speaking with his teacher, that while God may have something in mind for a person, it is that person's choice as to whether he will listen to God and seek the good things God wishes for him (or her)—or not.
[The Personal Legend] is your blessing, the path God has chosen for you here on Earth. Whenever a man does that which gives him enthusiasm, he is following his Legend. However, not everyone has the courage to face up to his own dreams.
This focuses on the aspect of choice. According to what Coelho writes in The Alchemist and Coelho's input above from his teacher, with all three of the terms listed, God is involved. But with regard to one's Personal Legend, the individual can choose to follow the signs God leaves for him or ignore them. Achieving one's Personal Legend is realizing the wonderful things God has planned for every person alive. Ignoring or running away from one's Personal Legend (as Santiago was tempted to do when he lost all his money) will not bring someone the joy and fulfillment God wishes for every individual. This is the concept based upon Coelho's understanding of the world.