Generating realistic names with last names There is raw list of most frequent names and last names according to US census.
How to make a list of combined names and last names so it will look realistic, i.e., with a respect to frequency of names/last names?
 A: The problem is lack of external validation. You need to have a list of joint first-last name dyads to assess this problem. Simply generating names according frequency is too naive. You make errors, such as how female last names in Russia are conjugated with an "a", Anna Karenina's husband was Mr. Karenin. First or last names indicating race, nationality, or religion have a different frequency of the other, Jean-Pierre or Bernadette, for instance, may be more likely to be hooked up with Reaubideaux than O'Malley, Shah, or Xu.
A: Without the joint distribution all you can do is to draw independently from first and last names.
However, here's an idea on how to get the joint distribution. Draw a sample of first and last name, use their marginal frequencies, of course. Next, search LinkedIn or other social network by the combo: first + last name, retrieve the number of hits. This will give you the joint distribution. You don't have to run every combination, of course, only the most frequent ones.
A more difficult way is to search the social network by just the last or first name, and get the conditional distribution of the first/last name. This will also let you build the joint distribution. 
Both approaches have their advantages.
The problem with both is the bias. LinkedIn tends to be biased towards having educated professionals. So, if you're building spamming/scamming app for general population then it won't be a good choice to bootstrap your joint distribution.
A: I think names look realistic if the first name "goes well" with the last name. This is, after all, a big part of how parents select the name for their child; they say the full name out loud and see if it sounds "nice".
Violating this "sounds nice" property is what gives away fake names. The good news is that humans can recognize fake names, so you have at least a chance.
I'd cast it as a classification problem. If you can train classifier that can distinguish between randomly paired names and names from your list (with reasonable accuracy), you can probably also use it to generate positive examples (dpeneding on the type of classifier.
The important thing is to extract good features. You should extract information at the level of phonemes or letters (character bigrams might be good), and the position of the tokens is very important.
Then, just feed the classifier elements from your list as positive examples, and randomly paired names as negative examples. 
EDIT: Just read the question better. I thought you had a list of names that go together. You need that. Get that.
