Finding numbers that satisfy these equations - related to marginal distribution

Question

Let $a_1, \ldots , a_n \in [0,1]$ be some numbers such that $\sum\limits_{i=1}^n a_i=m$ for some natural number $m$. I want to prove that there exist nonnegative numbers $b_X$ where the indices $X$ are sets of size m, containing some of the natural numbers $1, \ldots , n$ such that: \begin{equation*} \sum\limits_{X} b_X = 1 \end{equation*} and \begin{equation*} \sum\limits_{X, j \in X} b_X = a_j \end{equation*} This can be translated to a probablity theoretic statement, but I am certain there is some simple algebraic or combinatoric proof, which I would prefer. I am unable to find it. A similar question has been asked here , the author even gives an answer themselves, but in my opinion it is incorrect. The $b_X$ sum to $1$ but the second property doesn't hold in their answer. They set $b_X = \frac{\sum_{i \in X} a_{i}}{m\cdot{n-1\choose m-1}}$. Unless I am miscalculating this can't be correct.

Answer 1

Let a $m$-sum $n$-tuple be a tuple $(a_1,\dots,a_n)$ of nonnegative real numbers in $[0,1]$ such that $\sum_{i=1}^n a_i=m$. For all positive integers $m$ and $n$, we want to construct a function $b_{m,n}((a_1,\dots,a_n),X)$ which takes in a $m$-sum $n$-tuple $(a_1,\dots,a_n)$ and a set $X$ where $|X|=m$ and $X\subseteq \{1,\dots,n\}$ such that: $$ \sum_X b_{m,n}((a_1,\dots,a_n),X)=1 $$ and for every $1\leq j\leq n$, $$ \sum_{X,j\in X} b_{m,n}((a_1,\dots,a_n),X)=a_j $$ We will prove such a function $b_{m,n}$ exists for all positive integers $m,n$ by induction on $n$.

The $n=1$ case is trivial: First, if $n=1$, then we need $m=1$ because $a_1\in [0,1]$. Thus, we define $b_{1,1}$ as $b_{1,1}((a_1),\{1\})=a_1$, and it is trivial to show the above two conditions hold. (Notice that we must have $a_1=1$ in this case for $(a_1)$ to be a $1$-sum $1$-tuple.)

Now, for the inductive case: For positive integers $m,n$ where $n > 1$, assume that $b_{m',n'}$ exists for all positive integers $m',n'$ where $n' < n$. Then, we must prove a $b_{m,n}$ which satisfies our two conditions exists. We will split this inductive case into two cases: $m=1$ and $m > 1$.

The $m=1$ case is trivial: We just define $b_{1,n}$ as $b_{1,n}((a_1,\dots,a_n),\{j\})=a_j$ for all $1\leq j\leq n$, and it is trivial to show the above two conditions hold.

Now, for the $m > 1$ case: We construct $b_{m,n}$ as follows: $$ b_{m,n}((a_1,\dots,a_n),X)= \begin{cases} a_1b_{m-1,n-1}\left(\left(p_2,\dots,p_n\right),X\setminus \{1\}\right) & 1 \in X \\ (1-a_1)b_{m,n-1}\left(\left(p_2',\dots,p_n'\right),X\right) & 1 \notin X \end{cases} $$ If you understand how this is a probability theoretic statement, here is the intuition behind the above definition: We need to choose exactly $m$ elements from $1,\dots,n$, where the probability of choosing the element $i$ is $a_i$. In particular, the probability of choosing element $1$ is $a_1$, so we choose $1$ with probability $a_1$ (the first case) and we do not choose $1$ with probability $1-a_1$ (the second case). Finally, in the first case, the $p_i$s represent the conditional probability $P(i\text{ is chosen} \mid 1\text{ is chosen})$ while in the second case, the $p_i'$s represent the conditional probability $P(i\text{ is chosen} \mid 1\text{ is not chosen})$.

Now, we need to construct $p_2,\dots,p_n$ and $p_2',\dots,p_n'$. In order for $b_{m,n}$ to satisfy our two conditions, we need the to hold: $$ 0\leq p_i\leq 1\text{ and }0\leq p_i'\leq 1\text{ for all }2\leq i\leq n $$ This comes from the restriction that all inputs to our function need to be in the interval $[0,1]$. $$ p_2+\dots+p_n=m-1 $$ This comes from the restriction that all inputs to $b_{m-1,n-1}$ must be a $m-1$-sum $n-1$-tuple. $$ p_2'+\dots+p_m'=m $$ This comes from the restriction that all inputs to $b_{m,n-1}$ must be a $m$-sum $n-1$-tuple. $$ a_i=a_1p_i+(1-a_1)p_i'\text{ for all }2\leq i\leq n $$ This last condition will be necessary to show $b_{m,n}$ satisfies our second condition. The intuition for this condition comes from the following probability statement: $$ \begin{align*} P(i\text{ is chosen})=\ &P(1\text{ is chosen})P(i\text{ is chosen}\mid 1\text{ is chosen}) \\ +&P(1\text{ is not chosen})P(i\text{ is chosen}\mid 1\text{ is not chosen}) \end{align*} $$ Now, we know that $a_2+\dots+a_n=m-a_1=m-1+(1-a_1)$. This means that, compared to $a_2,\dots,a_n$, the sum of $p_2,\dots,p_n$ needs to be $1-a_1$ lower than that of $a_2,\dots,a_n$ and the sum of $p_2',\dots,p_n'$ needs to be $a_1$ higher than that of $a_2,\dots,a_n$.

In order to carry this out, we will construct some $d_2,\dots,d_n$ such that (1) $0\leq d_i\leq a_i$ for all $2\leq i\leq n$, (2) $[a_1/(1-a_1)]d_i\leq 1-a_i$, and (3) $d_2+\cdots + d_n=1-a_1$. The use of these conditions will be explained below, but for conditions (1) and (3), the intuition is that $d_i$ represents the amount we will decrease $a_i$ by in order to get $p_i$, and the fact that the sum of the $d_i$s is $1-a_1$ means that the total sum of the $p_i$s will be the sum of the $a_i$s, $m-a_1$, minus $1-a_1$, which is $m-1$, as desired.

We define the $p_i$s and $p_i'$s as follows: $$ p_i=a_i-d_i $$ $$ p_i'=a_i+\frac{a_1}{1-a_1}d_i $$ The intuition behind the definition for $p_i$ has been explained. For $p_i'$, there are two pieces: first, the sum of $[a_1/(1-a_1)]d_i$s will be $[a_1/(1-a_1)]\cdot (1-a_1)=a_1$. This means that the sum of the $p_i'$s is the sum of the $a_i$s, $m-a_1$, plus $a_1$, which is $m$, as desired. The second piece is that, by increasing $p_i'$ by a ratio of $a_1/(1-a_1)$ compared to what $p_i$ was decreased by, we ensure that the overall change maintains the condition that $a_i=a_1p_i+(1-a_1)p_i'$. This last condition can easily be verified by plugging the definitions of $p_i$ and $p_i'$ into $a_1p_i+(1-a_1)p_i'$ and simplifying.

We also need to verify that $0\leq p_i\leq 1$ and $0\leq p_i'\leq 1$. For $0\leq p_i\leq 1$, we can easily see that $p_i\leq a_i\leq 1$ and $p_i=a_i-d_i \geq 0$ because we defined $d_i$ so that $0\leq d_i\leq a_i$. For $0\leq p_i'\leq 1$, it is easy to see that $p_i'\geq a_i\geq 0$ and we also have $p_i'=a_i+[a_1/(1-a_1)]d_i\leq 1$ because we defined $d_i$ such that $[a_1/(1-a_1)]d_i\leq 1-a_i$.

With all of our conditions on the $p_i$s having been verified, the last step is to construct the $d_i$s. First, let $S$ be the set of $2\leq i\leq n$ such that $a_i < 1-a_1$. Then, there are two cases:

Case 1: The sum of $S$ is greater than or equal to $1-a_1$. In this case, we can get away with just decreasing the $a_i$s from $S$, so for all $i\notin S$, we set $d_i=0$. Then, if $S=\{i_1,\dots,i_m\}$, we define the $d_{i_\ell}$s as follows: $$ d_{i_\ell}= \begin{cases} a_{i_\ell} & a_2+\cdots+a_{i_\ell} < 1-a_1 \\ a_{i_\ell}-((1-a_1)-(a_2+\cdots+a_{i_{\ell-1}})) & a_2+\cdots+a_{i_{\ell-1}} < 1-a_1\text{ and }a_2+\cdots+a_{i_\ell} \geq 1-a_1 \\ 0 & a_2+\cdots+a_{i_{\ell-1}} \geq 1-a_1 \end{cases} $$ I'll leave it as an exercise to show $0\leq d_i\leq a_i$ and $d_2+\cdots+d_n=1-a_1$. To show $[a_1/(1-a_1)]d_i\leq 1-a_i$, we need a few steps: First, $d_i\leq a_i\leq 1-a_1$, so $[a_1/(1-a_1)]d_i\leq [a_1/(1-a_1)](1-a_1)=a_1$. Second, whenever $d_i > 0$, we have $i\in S$ so $a_i < 1-a_1$ and thus $1-a_i > a_1$. Ergo, we have $$ \frac{a_1}{1-a_1}d_i\leq \frac{a_1}{1-a_1}(1-a_1)=a_1 < 1-a_i $$ as was to be shown.

Case 2: The sum of $S$, which we will denote as $z$, is less than $1-a_1$. In this case, we set $d_i=a_i$ for all $i\in S$, and $0\leq d_i\leq a_i$ and $[a_1/(1-a_1)]d_i\leq 1-a_i$ can be shown in a similar manner to Case 1. However, this is not enough because we need $d_2+\cdots+d_n=1-a_1$. Therefore, if $T$ is the set of all $2\leq i\leq n$ such that $i\notin S$, we need to set some of the $d_i$ where $i\in T$. Before doing this, we make an observation: $$ \begin{align*} & \sum_{i=2}^n a_i=m-a_1 \\ \implies & \sum_{i=2}^n 1-a_i=n-m+a_1 \end{align*} $$ Let the $\text{frac}$ function be $t\to t-\lfloor t\rfloor$. It is well-known that $\text{frac}(a+b)\leq \text{frac}(a)+\text{frac}(b)$, so: $$ \begin{align*} & \sum_{i=2}^n \text{frac}(1-a_i)\geq \text{frac}(n-m+a_1) \\ \implies & \sum_{i=2}^n 1-a_i \geq a_1 \\ \implies & \sum_{i\in T} 1-a_i + \sum_{i\in S} 1-a_i \geq a_1 \\ \implies & \sum_{i\in T} 1-a_i \geq a_1-\sum_{i\in S} 1-a_i \end{align*} $$ Now, $d_i=a_i$ then, by the argument from Case 1, we have $[a_1/(1-a_1)]d_i=[a_1/(1-a_1)]a_i\leq 1-a_i$. Ergo, $$ \begin{align*} & \sum_{i\in T} 1-a_i \geq a_1-\sum_{i\in S} \frac{a_1}{1-a_1}a_i \\ \implies & \sum_{i\in T} 1-a_i \geq a_1-\frac{a_1}{1-a_1}\sum_{i\in S} a_i \\ \implies & \sum_{i\in T} 1-a_i \geq a_1-\frac{a_1}{1-a_1}z \end{align*} $$ From this fact, using a similar process to Case 1, we can choose $d_i'$ for all $i\in T$ such that $0\leq d_i'\leq 1-a_i$ and $\sum_{i\in T} d_i' = a_1-[a_1/(1-a_1)]z$. Then, we choose $d_i=[(1-a_1)/a_1]d_i'$. Right off the bat, we can see that $[a_1/(1-a_1)]d_i=d_i'\leq 1-a_i$, so that condition is easily satisfied. We also have that $$ \sum_{i\in T} d_i=\frac{1-a_1}{a_1}\sum_{i\in T} d_i'=\frac{1-a_1}{a_1}\left(a_1-\frac{a_1}{1-a_1}z\right)=1-a_1-z $$ Since, for $i\in S$, we have $d_i=a_i$ and the sum of $a_i$ over $i\in S$ is $z$, this means that the sum of all $d_i$ over both $i\in S$ and $i\in T$ is $(1-a_1-z)+z=1-a_1$, which satisfies that condition.

The last condition to verify is $0\leq d_i\leq a_i$. Since $d_i'\geq 0$, it is easy to see that $d_i=[(1-a_1)/a_1]d_i'\geq 0$. Then, since $d_i'\leq 1-a_i$, we have $d_i\leq [(1-a_1)/a_1](1-a_i)$. First, since $i\in T$, we know that $a_i \geq 1-a_1$. This means that $1-a_i\leq a_1$. Using these, we have that: $$ d_i\leq \frac{1-a_1}{a_1}(1-a_i)\leq \frac{1-a_1}{a_1}a_1=1-a_1 \leq a_i $$ which verifies the last condition we needed.

Now that we have constructed the $d_i$s and shown they satisfy our needed conditions, we are done with defining the recursive function.

I think coming up with this recursive function definition and showing the conditions about $p_i$s, $p_i'$s, and $d_i$s is the hardest part of the problem, so I will leave the proof for showing the $b_{m,n}$ function above satisfies the two conditions that we need, using the conditions we proved about the $p_i$s and $p_i's$, to you. But hopefully, with the intuition behind the conditions for the $p_i$s and $p_i'$s, it at least makes intuitive sense why this function would satisfy these two conditions.