On a complicated urn problem and the small code to solve it

Here is the simple problem i submitted the Telegram community a it of time ago:

We have an urn with n×m balls, we pick k balls from that urn, k greatly supperior to m. the balls in the urn assorted as groups with each group bearing a same number, there are n groups of m balls.

What is the probability of picking at least half a full group of balls?

This problem appeared too long to solve on my tight schedule, so I decided to go for some Monte-Carlo-ish approach and to make a few thousand trials.

Here is the code that was used:

#include <stdint.h>
#include <vector>
#include <array>
#include <algorithm>
#include <iostream>
#include <atomic>

struct ball{
	uint64_t N;
	uint64_t M;
};

int main()
{
	constexpr uint32_t attempt_count = 4800000;
	constexpr uint64_t k_max = 4500;
	constexpr uint64_t m_num = 16;
	constexpr uint64_t n_num = 8192/m_num;
	std::array<std::atomic_int, k_max> global_counts;
	for(uint64_t i=0; i<k_max;i++)
		global_counts[i].store(0);

	#pragma omp parallel for
	for(uint64_t att=0;att<attempt_count;att++)
	{
		std::vector<ball> deck;
		for(uint64_t i = 0; i<n_num; i++)
			for(uint64_t j = 0; j<m_num; j++)
				deck.push_back(ball{.N=i, .M=j});
		std::random_shuffle(deck.begin(), deck.end());

		std::vector<uint64_t> counts(n_num,0);
		for(uint64_t tir = 0; tir<k_max; tir++)
		{
			ball my_ball = deck.back();deck.pop_back();
			
			counts[my_ball.N]++;
			if(std::any_of(counts.begin(), counts.end(),[=](uint64_t v){return v>=(m_num/2);}))
			{
				global_counts[tir]++;
			}
		}
		
	}

	for(uint64_t k=0;k<k_max;k++)
		std::cout<<k<<";"<<[](double de, double di){return de/di;}(global_counts[k],attempt_count)<<"\n";
}

And here is the diagram made from it:

Here the red curve stands for m=16 and the green one stands for m=32.

Conclusion

I invite you to check the information at https://nekoit.xyz/, join us on Discord or Telegram, or follow me on Mastodon [email protected] to receive notifications of my followup posts.