I think this question is going to be hard to answer because while we know a fair bit about Spartans and can reasonably assume a fair bit more (as covered by /u/Iphikrates, among other places, here, here and here) based on the historical record and our knowledge of other greek states, we know very little about the "immortals".

In so far as I'm aware all of our knowledge of them, and indeed the only mention of them by that name, comes from Herodotus Histories and it doesn't give us much to work with outside of Xeres' campaign. In so far as I'm aware there exists no sources on when the immortals were formed, where they were garrisoned (although it is generally assumed that they were the royal guard in Persepolis), how they were trained or how they were recruited.

Herodotus merely says that "when any one of them was forced to fall out of the number by death or sickness, another was chosen". The assumption is that they were chosen from among already trained warriors of the persian nobility but that is about the extent of it. Since they were, according to Herodotus, the royal guard, it stands to reasons that it is immortals we see depicted on the walls of Persepolis and Susa but again, this is an educated guess and it gives no information with direct relation to the questions you ask.