Return to Answer

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}

This can be solved in two cases:

• Case 1: Suppose there is an $x \in \mathcal{S}$ such that $1\leq x < M$. Then we can choose $c = x + \epsilon$ for some very small value $\epsilon>0$, so that $g_c=x$, and $(c-g_c)/(M-g_c)$ is arbitrarily small. In this case, $p^*=0$.

• Case 2: Suppose there is no $x \in \mathcal{S}$ such that $1\leq x < M$. So we choose $c=1$ and $$ p^* = \frac{1-g_1}{M-g_1}$$

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}

This can be solved by considering two cases:

• Case 1: Suppose there is an $x \in \mathcal{S}$ such that $1\leq x < M$. Then we can choose $c = x + \epsilon$ for some very small value $\epsilon>0$, so that $g_c=x$, and $(c-g_c)/(M-g_c)$ is arbitrarily small. In this case, $p^*=0$.

• Case 2: Suppose there is no $x \in \mathcal{S}$ such that $1\leq x < M$. So $g_c=g_1$ for all $c \in [1,M]$. So we choose $c=1$ and $$ p^* = \frac{1-g_1}{M-g_1}$$

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}

This can be solved in two cases:

• Case 1: Suppose there is an $x \in \mathcal{S}$ such that $1\leq x < M$. Then we can choose $c = x + \epsilon$ for some very small value $\epsilon>0$, so that $g_c=x$, and $(c-g_c)/(M-g_c)$ is arbitrarily small. In this case, $p^*=0$.

• Case 2: Suppose there is no $x \in \mathcal{S}$ such that $1\leq x < M$. So we choose $c=1$ and $$ p^* = \frac{1-g_1}{M-g_1}$$

The problem asked (without independence) can be solved.

  Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define  $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ We solve the problem by first solving a simpler problem ("Problem 1" below) that fixes a specific value for $E[X]$.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve problem 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $0 \leq g_c < c \leq M$. Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $\lambda_c = \frac{1}{M-g_c}$ and note that $\lambda_c>0$. Define $A$ as a set of all expectation vectors that arise from random vectors in $\mathcal{X}$: $$ A = \left\{\left(E[X_1], ..., E[X_n], P\left[\sum_{i=1}^n X_i \geq c\right]\right) \in \mathbb{R}^{n+1} : (X_1, ..., X_n) \in \mathcal{X}\right\} $$ Consider the following two problems:

• Constrained problem: \begin{align} \mbox{Minimize:} \quad & x_{n+1}\\ \mbox{Subject to:} \quad & \sum_{i=1}^n x_i = c \\ & (x_1, ..., x_{n+1}) \in A \end{align}

• Unconstrained problem: \begin{align} \mbox{Minimize:} \quad & x_{n+1} + \lambda_c\left(c-\sum_{i=1}^n x_i\right) \\ \mbox{Subject to:} \quad & (x_1, ..., x_{n+1}) \in A \end{align}

Observe that the constrained problem is equivalent to Problem 1. Also observe by standard Lagrange multiplier theory that if $\vec{x}^*$ is a solution to the unconstrained problem that satisfies $\sum_{i=1}^n x_i^*=c$, then it also solves the constrained problem. Indeed, such a vector $\vec{x}^*$ would trivially satisfy all constraints of the constrained problem, and for any other vector $\vec{w}=(w_1, ..., w_n, w_{n+1})$ that satisfies the constraints of the constrained problem, we have (since $\vec{w} \in A$): $$ x_{n+1}^* + \lambda_c\underbrace{\left(c-\sum_{i=1}^n x_i^*\right)}_{0} \leq w_{n+1} + \lambda_c\underbrace{\left(c-\sum_{i=1}^n w_i\right)}_{0} $$ and so $x_{n+1}^*\leq w_{n+1}$. Define the function $f:\mathcal{X}\rightarrow\mathbb{R}$ by: $$ f(x_1, ..., x_n) = 1\left\{\sum_{i=1}^n x_i\geq c\right\} + \lambda_c\left(c-\sum_{i=1}^n x_i\right) $$ where $1\{\cdot\}$ denotes an indicator function. It is not difficult to show that $$f(x_1, ..., x_n) \geq p_c \quad \forall (x_1, ..., x_n) \in \mathcal{X}$$ Hence, for all random vectors $(X_1, ..., X_n) \in \mathcal{X}$ we have: $$ f(X_1, ..., X_n) \geq p_c$$ and so for all random vectors $(X_1, ..., X_n) \in \mathcal{X}$ we have $E[f(X_1, ..., X_n)] \geq p_c$, that is: $$ P\left[\sum_{i=1}^n X_i \geq c\right] + \lambda_c (c - E[\sum_{i=1}^n X_i]) \geq p_c $$ However, the particular random vetor $(Z_1, .., Z_n) \in \mathcal{X}$ satisfies $\sum_{i=1}^n Z_i \in \{M, g_c\}$ always (where $0\leq g_c < c\leq M$), and so $$ f(Z_1, ..., Z_n) = p_c \quad , \mbox{ for all realizations of $(Z_1,...,Z_n)$} $$ Hence $$ E[f(Z_1, ..., Z_n)] = p_c $$ Thus, the random vector $(Z_1, ..., Z_n)$ minimizes the expression: $$ P\left[\sum_{i=1}^n X_i \geq c\right] + \lambda_c (c - E[\sum_{i=1}^n X_i]) $$ over all random vectors $(X_1, ... X_n) \in \mathcal{X}$. That is, the random vector $(Z_1, ..., Z_n)$ solves the unconstrained problem. But we already know this random vector satisfies $\sum_{i=1}^n E[Z_i]=c$, hence (by Lagrange multiplier theory) it solves the constrained problem, hence it solves Problem 1. $\Box$

Problem 2: This is the original problem of the question, which does not specify the mean $E[\sum_{i=1}^n X_i] =c$. So we just optimize over $c \in [1, M]$.

$$ p^* = \min_{c \in [1, M]}\left[ \frac{c-g_c}{M-g_c} \right]$$

The problem asked (without independence) can be solved. Fix nonnegative real numbers $a_1, …, a_n$. Define $M = \sum_{i=1}^n a_i$ and assume $M \geq 1$. Define  $$\mathcal{X} = \{0, a_1\} \times \{0, a_2\} \times … \times \{0, a_n\} $$ To solve the problem, we first solve a simpler problem (called "Problem 1") below.

Problem 1: Fix $c \in [1,M]$. We want to find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq c\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] = c \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

To solve Probelm 1, define $$ g_c = \max_{(x_1, ..., x_n) \in \mathcal{X}} \left\{\sum_{i=1}^n x_i : \sum_{i=1}^n x_i < c\right\} $$ That is, $g_c$ is the largest value of $\sum_{i=1}^n x_i$ over all vectors $(x_1, ..., x_n) \in \mathcal{X}$ with components that sum to less than $c$. The max is achievable because $\mathcal{X}$ is a finite set that contains the all-zero vector. Note that $$0 \leq g_c < c \leq M$$ Define $\vec{x}_c$ as an element of $\mathcal{X}$ with a sum of components that is equal to $g_c$. Define $$p_c = \frac{c-g_c}{M-g_c}$$ Observe that $0< p_c \leq 1$. Define the random vector $$ (Z_1, ..., Z_n) = \left\{ \begin{array}{ll} (a_1, ..., a_n) &\mbox{ with prob $p_c$} \\ \vec{x}_c & \mbox{ with prob $1-p_c$} \end{array} \right.$$ It is not difficult to show that $E[\sum_{i=1}^nZ_i] = c$ and $$P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c $$

Claim

The random vector $(Z_1, ..., Z_n)$ solves problem 1. In particular, the minimum probability is: $$ P\left[\sum_{i=1}^n Z_i \geq c\right] = p_c = \frac{c-g_c}{M-g_c}$$

Proof

Define $$\mathcal{S} = \left\{\sum_{i=1}^n x_i \in \mathbb{R} : (x_1, …, x_n) \in \mathcal{X}\right\}$$ Let $(X_1, ..., X_n)$ be any random vector in $\mathcal{X}$ that satisfies $E[\sum_{i=1}^n X_i]=c$. Define $S=\sum_{i=1}^n X_i$. Note that: $$ S \in \mathcal{S} \subseteq [0, g_c] \cup [c, M]$$ Thus \begin{align} c &= E[S|S\geq c]P[S\geq c] + E[S|S\leq g_c](1-P[S\geq c]) \\ &\leq M P[S\geq c] + g_c(1-P[S\geq c]) \end{align} and so $$ P[S\geq c] \geq \frac{c-g_c}{M-g_c} = p_c $$ Thus, if $(X_1, ..., X_n)$ is any vector in $\mathcal{X}$ that satisfies the constraints of Problem 1 (namely, $E[\sum_{i=1}^n X_i]=c$), then $$ P\left[\sum_{i=1}^n X_i \geq c\right] \geq p_c $$ On the other hand, the lower bound is achieved by the random vector $(Z_1, ..., Z_n)$ defined above. $\Box$

Problem 2: Find a random vector $(X_1, ..., X_n)$ to solve \begin{align} \mbox{Minimize:} \quad & P\left[\sum_{i=1}^n X_i \geq E\left[\sum_{i=1}^nX_i\right]\right] \\ \mbox{Subject to:} \quad & E\left[\sum_{i=1}^n X_i\right] \geq 1 \\ & (X_1, ..., X_n) \in \mathcal{X} \end{align}

Problem 2 can be solved via Problem 1 by optimizing over the mean $c = E[\sum_{i=1}^n X_i]$ over all $c \in [1, M]$. Thus:

\begin{align} p^* &= \inf_{c \in [1, M]} \frac{c-g_c}{M-g_c} \end{align}