↵
Let $ \mathbf{p^0} = (p^0_1, p^0_2, \ldots, p^0_n) $ denote the initial vector of success probabilities that we are given, and let $ \mathbf{p} = (p_1, p_2, \ldots, p_n) $ be an arbitrary vector of success probabilities. Let $ S(i, \mathbf{p}) $ denote the probability of exactly $ i $ cores succeeding given that the success probabilities in $ \mathbf{p} $. Then we are trying to maximise
↵
Пусть $ \mathbf{p^0} = (p^0_1, p^0_2, \ldots, p^0_n) $ -- заданный вектор вероятностей успеха ядр и $ \mathbf{p} = (p_1, p_2, \ldots, p_n) $ -- другой вектор вероятностей. Пусть $ S(i, \mathbf{p}) $ -- вероятность, что точно $ i $ ядр будут успешными, допустя что ядро $ i $ будет успешным с вероятностей $ p_i $. Тогда мы хотим найти максимум функции↵
$$ f(\mathbf{p}) = \sum_{i \geq K} S(i, \mathbf{p}) $$↵
↵
$$ g(\mathbf{p}) = \sum_{i} p_i = u + \sum_{i} p^0_i $$↵
↵
$$ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot \nabla_{\mathbf{p}} \left(\sum_{i} p_i\right) = \lambda \cdot (1, 1, \ldots, 1) $$↵
↵
####
$$ \frac{\partial f}{\partial p_i} = S(K - 1, \mathbf{p}_{-i}) $$↵
↵
#### Proof of Lemma↵
This is a somewhat well-known derivation, but I have included it for completeness. By expanding the terms,
↵
#### Доказательство Леммы↵
Разложим члены уравнения:↵
$$ \frac{\partial f}{\partial p_i} = \frac{\partial}{\partial p_i} \left[ p_i \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) + (1 - p_i) \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) \right] $$↵
$$ \frac{\partial f}{\partial p_i} = \left( \sum_{i \geq K - 1} S(i, \mathbf{p}_{-i}) \right) - \left( \sum_{i \geq K} S(i, \mathbf{p}_{-i}) \right) = S(K - 1, \mathbf{p}_{-i}) $$↵
(
↵
In order to have
↵
Наивное решение $ \nabla_{\mathbf{p}} f(\mathbf{p}) = \lambda \cdot (1, 1, \ldots, 1) $
↵
1. We leave $ p_i $ at its initial value
↵
1. Оставим $ p_i $ как $ p^0_i $.↵
2.
3.
↵
This observation is sufficient to restrict the solution space to the point where we can search over it. (Well, we still need to make some efficiency arguments, like "only increase $ p_i $ up to 1 if it is already big", and "only try to equalize $ p_i $'s that are close to each other", etc..., but you get the idea
↵
Это наблюдение ограничает множесвто решений до такой степени, что мы можем его перебрать. (Ну, еще нужно несколько оптимизаий, например "увеличить $ p_i $ до $ 1 $ только если $ p_i $ уже велик", но это главная идея.)
