monotone_approx.jl

using Distributions
using Statistics

function monotone_approx(N::Int64,n_trials::Int64,n::Int64)

	"""
		inputs:
			N: the range of U([-N,N])
			n_trials: the number of times we generate random vectors
			n: the 'dimension' of the random vector

		outputs:
			Q: the quality of the approximation for ten values
			monotone relation: a logical verification that the monotone relation holds

	"""

	X = rand(-1*N:N,n_trials,n);

	Y = sum(X,dims=(2));

	## comparison with binomial:
	Q = zeros(10);

	D, D_hat = zeros(10), zeros(10);

	for k =1:10

		## delta is approximately N/2
		delta = N/2

		## an approximation of n_hat which is 'n' in the n choose k formula
		n_hat = Int(floor((2*N/(2*N+1))*n));

		## the fraction of S_n whose value is greater than 2*Delta*k:
		D[k] = mean(Y.>2*delta*k);

		## k in the n choose k formula:
		D_hat[k] = Int(floor((2*k + n_hat)/2));

		## a CDF that should have a monotone relationship with W
		## this may be considered an approximation
		Z = 1-cdf(Binomial(n_hat),D_hat[k]);

		## checking the quality of the approximation
		Q[k] = min(D[k],D_hat[k])/max(D[k],D_hat[k])

	end

	return Q, minimum((D[2:10].-D[1:9]).*(D_hat[2:10].-D_hat[1:9])) > 0

end