Step by Step solution about How to resolve the algorithm Percolation/Mean run density step by step in the C programming language

The C program is designed to estimate the binomial probability p(1 - p) and compare it to the observed probability K obtained from a series of coin flips (represented by a random number generator). It runs multiple tests with varying probabilities and sample sizes to analyze the deviations from the expected binomial distribution.

• Function run_test:

  • Inputs: probability p, sequence length len, number of runs runs.
  • Generates a sequence of len random 0s and 1s without storing them. Each element is generated by comparing a random number to a threshold thresh, calculated as p * RAND_MAX.
  • Counts the number of transitions from 0 to 1 (cnt) during the runs.
  • Returns the observed probability K as the ratio of transitions to the total number of elements and runs.

• Main Function:

  • Sets up parameters for testing:
    • Varying probabilities (p) from 0.1 to 0.9.
    • Varying sequence lengths (n) from 100 to 100000.
  • Loops through these parameters and performs the following for each combination:
    • Calls run_test to obtain the observed probability K.
    • Calculates the expected binomial probability p(1 - p) (p1p).
    • Prints out p, n, K, p1p, and the difference between K and p1p, along with the percentage difference.

• Output:

  • A table displaying the results for each combination of p and n.
  • The table shows the probability, sequence length, observed probability, expected binomial probability, the difference between the two, and the percentage difference.

#include <stdio.h>
#include <stdlib.h>

// just generate 0s and 1s without storing them
double run_test(double p, int len, int runs)
{
	int r, x, y, i, cnt = 0, thresh = p * RAND_MAX;

	for (r = 0; r < runs; r++)
		for (x = 0, i = len; i--; x = y)
			cnt += x < (y = rand() < thresh);

	return (double)cnt / runs / len;
}

int main(void)
{
	double p, p1p, K;
	int ip, n;

	puts(	"running 1000 tests each:\n"
		" p\t   n\tK\tp(1-p)\t     diff\n"
		"-----------------------------------------------");
	for (ip = 1; ip < 10; ip += 2) {
		p = ip / 10., p1p = p * (1 - p);

		for (n = 100; n <= 100000; n *= 10) {
			K = run_test(p, n, 1000);
			printf("%.1f\t%6d\t%.4f\t%.4f\t%+.4f (%+.2f%%)\n",
				p, n, K, p1p, K - p1p, (K - p1p) / p1p * 100);
		}
		putchar('\n');
	}

	return 0;
}