Is this an application of the Birthday problem?

Question

Let's say there is some positive integer n that is somewhere between 0 and N (also a positive integer). I tell the program to start generating random (or pseudo-random) number pairs (modulo N) and check each time if their difference is n. When n is found, program exits.

pseudo code:

declare n and give it some value;
declare a;
declare b;

--start
a = random() mod N;
b = random() mod N;

if |a-b| = n
   {
     exit program;
   }
else
   {
     go back to the start line;
   }

What is the complexity of such program?

Next, I want to find what is the probability of that n being found after m number of tries (pair difference checks). To make it easier, I reverse the question and ask what is the probability of that n NOT being found after m tries:

(for example, n = 9 and N = 10)

2 = number of pairs that give 9 (I'm checking for absolute values of pair differences)

10^2 = number of all possible pairs

10^2 - 2 = number of pairs that will NOT give 9

So the probability of NOT getting 9 after m tries is: $(\frac{98}{100})^m$

It seems that after around 34 checks I should have about 50% probability of getting 9.

Is my calculation correct? Is this an application of the Birthday problem?

Answer 1

The only way to get $a - b \equiv N \mod N$ when $a$ and $b$ are $0 \le a, b < N$ is that $a = b$. Thus the program stops when the same number is generated twice, which happens once in $N^2$ tries.

The birthday paradox is that the size of the set of values taken independently out of $N$ to get probability $1/2$ of some element repeating is around $\sqrt{N}$, but one would naïvely think it needs to be much larger.

Answer 2

First i wrote a bit of code in c#

using System;
using System.Collections.Generic;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            var calc = new Calculator(100);
            Console.WriteLine(string.Format("All Differences are {0}", calc.CountAllDifferences()));
            Console.WriteLine(string.Format("All Differences %N = 0 are: {0}", calc.CoundAllDivisibleDifferences()));
            Console.Read();
        }
    }

    internal class Calculator
    {
        private int n;

        public Calculator(int n)
        {
            this.n = n;
        }

        public int CountAllDifferences()
        {
             HashSet<int> allPossibleDifferences = new HashSet<int>();
            for (int a = 0; a < n; a++)
            {
                for (int b = 0; b < n; b++)
                {
                    allPossibleDifferences.Add(Math.Abs(a - b));
                }
            }
            return allPossibleDifferences.Count;
        }


        public int CoundAllDivisibleDifferences()
        {
            var divisibleDifferences = 0;
            for (int a = 0; a < n; a++)
            {
                for (int b = 0; b < n; b++)
                {
                    if (Math.Abs(a-b)%n == 0)
                    {
                        divisibleDifferences += 1;
                    }
                }
            }
            return divisibleDifferences;
        }
    }
}

the result is, that there are for N, you will get n possible absolute differences. And you get also n possible diffences, for Math.abs(a-b)%n==0.

In case of n=10, than each time a equals b.

So the complexity could be O(N/2) = O(N) in Big O Notation.