/ English

# 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. #### Ludovic Lagouardette

Founder of NekoIT, Developer and Cloud architect

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