0
$\begingroup$

Ok, It was hard to explain my problem in the title. I hope it made enough sense to peak the curiosity of some of you.

What I've been trying to do is find the relationship between the amount of random numbers generated (n) and the probability that an equal amount of odd and even numbers are generated. (n/2 odd and n/2 even). It should be clear that n must be an even number.

Obviously the numbers needn't be odd and even, as long as there is a 50% chance of generating one or the other. If this is posted in wrong location can someone navigate me in the right direction.

Anyway, basically I calculated mathematically that for every n amount of numbers generated, it should take on average approximately (4/5)sqrt(n) trials before the outcome is a perfect 50/50 (odd and even).

I got this result in terms of sqrt(n) using Stirling's approximation of factorials because I thought the final result would be much more comprehensible and easier to compare to my computed results.

However, my computed averages give me the result of approximately (6/5)sqrt(n) and I can't figure out why. I used two different pseudo-random generators (Math.random() & java.util.Random()) and both yielded the same results.

Below is the Maths involved in calculating the probability and I will also provide the code.

Please zoom in on the image if you can't read it.

MAths calculations

Computer program for calculating computationally:

public static void main(String[] args) {

    int run = 0;
    int total = 0;
    int amount = 0;
    int count = 0;
    int randint;
    int odd;
    int even;

    int n =100;                               // Amount of numbers generated randomly 
    int precision = 10000;                    // Amount of averages taken into account 
                                              // (Reduce with increase in "n" as time increases)

    Random generate = new Random(100);        // Seed 100 at beginning of program

    run = 1;

    while(run==1){

        odd = 0;
        even = 0;

        for(int i=0; i<n; i++){

            randint = generate.nextInt(2);

            if(randint%2==0){

                even++;  

            }else{

                odd++;

            }

        }

        count++;                            // increment count after every check

        if((odd==(n/2)) && (even==(n/2))){

            total+=count;                   // add count to total ( addition before addition - average calculation)
            amount++;                       // increment amount, this will be the division later
            count=0;

        }

        if(amount==precision){

            System.out.println(total/amount);  //print average
            run=0;



        }


    }

}
$\endgroup$
0
$\begingroup$

If $p = \binom{n}{n/2} \left( \frac{1}{2} \right)^n$ then your java code is approximating $\frac{1}{p}$ not $n p$.

Here's a wolfram alpha code for the two exact functions and your two sqrt approximations, plus a better approximation (5/4)*sqrt(n) for the function that your code is actually approximating (this follows from the sterling approximation of 1/p).

plot [ 1 /  ( choose[n, (n/2)] * (1/2)^n), n *  ( Choose[n, (n/2)] * (1/2)^n), (4/5)*sqrt(n), (6/5)*sqrt(n), (5/4)*sqrt(n) ] for n=50 to 150

The explanation is that your java code is approximating the mean of the geometric distribution whose success probability parameter is the probability that (odd==(n/2)) && (even==(n/2)).

Anyway, basically I calculated mathematically that for every n amount of numbers generated, it should take on average approximately (4/5)sqrt(n) trials before the outcome is a perfect 50/50 (odd and even).

The (4/5)sqrt(n) value is the expected number of perfect (n/2):(n/2) results you get when you try n times, not the expected number of trials it takes to get a perfect (n/2):(n/2).

$\endgroup$
0
$\begingroup$

I see that my other answer may be confusing so I'll try again.

Here are two things that are not the same:

  1. The expected number of perfect (n/2):(n/2) results when you try n times.
  2. The expected number of tries it takes to get a perfect (n/2):(n/2) result.

In your question and in your code you seem to confuse these two things. At the beginning of your question when you say

Anyway, basically I calculated mathematically that for every n amount of numbers generated, it should take on average approximately (4/5)sqrt(n) trials before the outcome is a perfect 50/50 (odd and even).

your text seems to mean (2) but your formula is for (1). Later in your copy pasted tex image, you say

the average number of 50/50 outcomes is given by multiplying the result by n

That text and its following formula agree, and they are both for (1). Your java code implements an approximation for the quantity you described in your text introduction; this implementation and the description are both for (2).

The expectations (1) and (2) are different, and they have sterling approximations (4/5)sqrt(n) and (5/4)sqrt(n) respectively. If you are using (1) and (2) interchangeably then this explains why you are getting inconsistent numbers.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.