Блог пользователя BinhPhamT

A permutation with probability problem with fast calculation
Автор BinhPhamT, история, 5 недель назад, По-английски

Recently, I have participated in school contest and I got this problem:

The problem is to generalize a formula for the probability P in terms of weights $$$w$$$ and sums $$$S$$$ for a given $$$n$$$, where $$$S=\sum_{j=1}^{n} w_j$$$

The probability formula involves choosing a permutation of the set $$$[2, n]$$$, which means the number of terms grows rapidly with $$$n$$$. Let's try to understand the general pattern by analyzing the cases for $$$n=3$$$ and $$$n=4$$$

$$$\textbf Case \ n = 3$$$

Given: $$$S = w_1 + w_2 + w_3$$$

For $$$n=3$$$, the formula for $$$P$$$ is:

$$$\Large P = \frac{w_2 \cdot w_3}{S \cdot (S - w_2)} + \frac{w_2 \cdot w_3}{S \cdot (S - w_3)}$$$

We can factor the expression:

$$$\Large P = \frac{w_2 \cdot w_3}{S} \left( \frac{1}{S - w_2} + \frac{1}{S - w_3} \right)$$$

This represents the weighted sum of two terms where the denominators correspond to the differences between $$$S$$$ and individual terms $$$w_2$$$ and $$$w_3$$$

$$$\textbf Case \ n = 4$$$

Now, let's analyze the case for $$$n=4$$$, where the formula involves more permutations:

$$$\Large P = \sum_{\text{all permutations of } {2, 3, 4}} \frac{w_2 \cdot w_3 \cdot w_4}{S \cdot (S - w_2) \cdot (S - w_2 - w_3)}$$$

The expanded form looks like:

$$$\Large P = \frac{w_2 \cdot w_3 \cdot w_4}{S \cdot (S - w_2) \cdot (S - w_2 - w_3)} + \cdots \quad \text{(5 more similar terms)}$$$

Group similar terms by factoring:

$$$\Large P = \frac{w_2 \cdot w_3 \cdot w_4}{S} \left( \frac{1}{(S - w_2)(S - w_2 - w_3)} + \frac{1}{(S - w_2)(S - w_2 - w_4)} + \cdots \right)$$$

$$$\textbf Generalizing\ to\ n$$$

For any $$$n$$$, the general form of the probability formula is:

$$$P = \sum_{\text{all permutations of } {2, 3, \dots, n}} \frac{\prod_{i=2}^{n} w_i}{S \cdot (S - w_{i_2}) \cdot (S - w_{i_2} - w_{i_3}) \cdot \cdots \cdot (S - w_{i_2} - w_{i_3} - \cdots - w_{i_{n-1}})}$$$

The pattern is that for each permutation of $$${2, 3, ..., n}$$$ , the numerator is the product of all $$$w_i$$$'s and the denominator involves nested sums subtracting successive terms of the permutation from $$$S$$$

$$$\textbf Recursive\ Structure$$$

The denominator has a recursive structure:

$$$ P = \frac{\prod_{i=2}^{n} w_i}{S} \sum_{\text{permutations}} \prod_{j=2}^{n-1} \frac{1}{S - w_{i_2} - w_{i_3} - \cdots - w_{i_j}} $$$

However, I don't really know how to compute $$$P$$$ with the given constraints like this

$$$1 \leq n \leq 5000$$$

$$$w_i > 0$$$ and $$$1 \leq \sum^{n}_{i=1} w_i <= 10^5$$$

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится