c# random.next() doesnt work correct [duplicate]

This question already has an answer here:

• Random number generator only generating one random number 8 answers

i am trying to get a random array with a recurse function. at the end it gets written into a 2dArray

static void GenerateRandomPath(int[] path, int indexPath, int entryInArray,ref int[,] paths) {
    int[] notContainedNumber = GetAllNumbersNotInArray(path, path.GetUpperBound(0));
    if (indexPath < path.GetUpperBound(0)) {
        Random random = new Random();
        int i = notContainedNumber[random.Next(notContainedNumber.Length)];
        path[indexPath] = i;
        GenerateRandomPath(path, indexPath + 1, entryInArray, ref paths);
    }
    else {
        path[indexPath] = path.GetUpperBound(0);
        SetRowOf2DArray(paths, path, entryInArray);
    }            
}

my call of this function looks like this:

 for (int i = 0; i < constantGeneratedPaths; i++) {
                GenerateRandomPath((int[])path.Clone(),1,i,ref paths);
            }

The problem is, that the results are weird. As an example if my constantGeneratedPaths was 20 i am getting 10-15 identical paths.

When i change my call to this:

for (int i = 0; i < constantGeneratedPaths; i++) {
                System.Threading.Thread.Sleep(10);
                GenerateRandomPath((int[])path.Clone(),1,i,ref paths);
            }

i am getting 2-3 identical paths out of 20 (they occure right after each other) (What is also hardly possible regarding that our possibility to get a simmilar result is something like 2 quintillion)

When changing my call to:

 for (int i = 0; i < constantGeneratedPaths; i++) {
                System.Threading.Thread.Sleep(100);
                GenerateRandomPath((int[])path.Clone(),1,i,ref paths);
            }

i dont get any simmilar results.

In my opinion this is really weird. Does anyone know what could be the problem here? I dont want to use a thread.sleep because it really slows down my application.