Motivated by the growing interest in correlation-robust stochastic optimization, we investigate stochastic selection problems beyond independence. Specifically, we consider the instructive case of pairwise-independent priors and matroid constraints. We obtain essentially-optimal bounds for offline contention resolution and prophet inequalities against the almighty online adversary.  The impetus for our work comes from the recent work of [18], who derived a constant-approximation for the single-choice prophet inequality with pairwise-independent priors.

For general matroids, our results are tight and largely negative. For both contention resolution and prophet inequalities, our impossibility results hold for the full linear matroid over a finite field. We explicitly construct pairwise-independent distributions which rule out an $\omega\left(\frac{1}{\rank}\right)$-balanced offline CRS and an $\omega\left(\frac{1}{\log \rank}\right)$-competitive prophet inequality.  For both results, we employ a generic approach for constructing pairwise-independent random vectors — one which unifies and generalizes existing pairwise-independence constructions from the literature on universal hash functions and pseudorandomness. Specifically, our approach is based on our observation that random linear maps turn linear independence into stochastic independence.

We then examine the class of matroids which satisfy the so-called partition property — these include most common matroids encountered in optimization. We obtain positive results for both contention resolution and prophet inequalities with pairwise-independent priors on such matroids, approximately matching the corresponding guarantees for fully independent priors.

§ INTRODUCTION

Combinatorial optimization subject to uncertainty has gained substantial interest in recent years, largely motivated by its applications in computational economics ([31, 20]).

In many of these tasks, the underlying uncertainty or stochasticity arises from either the random availability of elements of a set system or a stochastic weight assignment over these elements. Two pivotal stochastic selection problems, contention resolution (e.g., [48, 3, 28, 43, 40]) and generalized prophet inequalities (e.g., [37, 30, 26]), fit into this paradigm. These problems appear either directly, or indirectly as subroutines, throughout the fields of algorithms and combinatorial optimization with a wide range of applications including mathematical programming [48], combinatorial sparsification [25], online rounding schemes [46], stochastic probing [28, 2, 13], oblivious posted pricing mechanisms [43, 28, 27], and algorithmic delegation [36, 14, 15].

A rich literature examines the design of algorithms for these problems when the input is a product distribution or negatively correlated. However, our understanding is relatively limited when the input distribution exhibits correlations, particularly positive correlations, which are often present in many intended applications. For instance, consider the scenario of sequential posted pricing where a seller with a single item encounters $n$ prospective buyers in sequence, each possessing a valuation for the product. The seller, with the goal of maximizing profit, offers a fixed, non-negotiable price to each buyer, who then decides to buy the item if the price is less than or equal to their valuation. Yet, in today's hyper-connected world, it is unrealistic to presume buyers remain unaffected by or ignorant of each other's valuations. In fact, notable studies [42, 7] demonstrate this phenomenon by showing that the aggregate online reviews from a large group of buyers play a critical role in shaping customer behavior.

A deeper understanding of the interplay between correlation and optimal selection, and an expansion of the algorithmic toolkit thereof, could enable progress in everything from approximation algorithms, online decision-making, decision-making under uncertainty, mechanism design, and beyond. Consequently, recent research efforts also aimed to expand this toolkit to enable correlation robust stochastic optimization [9, 16, 17, 29, 33]. It is either known (e.g. [32, 44]), or easy to show, that not much can be achieved when there is of arbitrary positive correlation. Even under assumptions like the linear correlation model [12], in the worst case there are no positive algorithmic results for prophet inequalities with non-sparse dependencies even for the rank one matroid [33] [In the linear correlation model, weights $X = (X_1,\dots, X_n)$ are sampled as $X = AY$, where $A$ is a fixed matrix and $Y = (Y_1,\dots, Y_n)$ is a vector of independent random variables.  [33] shows a constant factor prophet inequality when either all rows or columns of $A$ have a constant number of non-negative entries. However, in general, prophet inequalities with linear correlations have a lower bound of $\Omega(n)$ due to [33]. ].

Recent work by [18] attempts to rigorously understand stochastic selection problems with a broad family of distributions that permit positive correlations. They examine prophet inequalities for the rank one matroid when the stochastic inputs are pairwise independent, that is, the value of any two elements of the set system are independent of each other. Pairwise independence is a practical relaxation of independent distributions, which has been identified as a key technical component in constructing pseudo-random generators, derandomization, and reusing randomness due to its “almost independent" behavior (for more details, see surveys [38, 47]).
For further insight into the motivation for studying stochastic optimization problems under conditions of pairwise independent distributions, [18] provides a more extensive discussion.
A key contribution of [18], and the initial motivation for this work, is their constant approximate prophet inequality for the rank one matroid when the input distribution is pairwise independent. This naturally leads us to the following question:

Do constant approximate prophet inequalities or contention resolution schemes exist for a broader class of set-systems, such as matroids, when the input distribution is pairwise independent? More generally, is it possible to characterize a class of set-systems that admit constant approximate prophet inequalities or contention resolution schemes?

We resolve the above question for matroids. We demonstrate the limitations for both the matroid prophet inequalities and matroid contention resolution schemes when the stochastic inputs are pairwise independent. In contrast to the strong algorithmic results with mutually independent inputs [37, 21], we rule out constant-approximate matroid prophet inequalities and offline contention resolution schemes. Subsequently, we complement these results with optimal algorithms that match the performance upper bounds.
The following informal results summarize our main contribution.

* There is no $\omega\left(\frac{1}{\log \rank}\right)$-competitive matroid prophet inequality with pairwise independent distributions.

* There is no $\omega\left(\frac{1}{\rank}\right)$-balanced contention resolution schemes for pairwise independent distributions.

For both results, we carefully construct a pairwise independent distribution for the linear matroid $\FF_q^d$ for some large $d \in \ZZ_{+}$ and desired prime $q$. Our approach to constructing pairwise independent distributions is founded on the observation that uniformly random linear maps between vector spaces convert linear independence in the domain space to stochastic independence in the range space. To put it formally, when a group of $n$ vectors, which are $k$-wise linearly independent, is embedded in a vector space via a uniformly random linear map, the embedded $n$ vectors exhibit $k$-wise stochastic independence and each assumes a uniform marginal distribution over the space. Special instances of this observation have previously been employed to define $k$-wise independent hash functions [19, 49] and $k$-wise independent random bits [5, 35, 6, 39]. For a comprehensive overview of prior work on the construction of pairwise independent distributions, we refer interested readers to the survey by [38] and Chapter 3 of [47]. Our method can be viewed as a simple unification of existing constructions of scalar-valued random variables[Despite the simplicity of the construction, we have not been able to identify another construction with this level of generality. The concepts presented here permeate existing work on constructing $k$-wise independent random variables.].

Later, we examine the class of matroids that satisfy the partition property — these include the most common matroids encountered in optimization. Informally, this property holds if a matroid can be approximated by a (random) partition matroid. We demonstrate that, when a matroid fulfills the partition property, we can reduce the problem to one defined over rank one matroids. Leveraging the prophet inequality of [18] and our contention resolution scheme for the rank one matroid, we obtain constant factor prophet inequalities and contention resolution schemes for pairwise independent distributions for such matroids.

Finally, our results enhance the current understanding of the differentiation between two matroid families: those which admits the partition property and those that do not, as discussed in recent works [1, 10]. In the context of the matroid secretary problem, existing algorithms for a certain class of matroids—graphic [8], co-graphic [45], and laminar [34]—are contingent upon a constant partition property of these matroids. A survey by Dinitz [22] has posed an open question whether every matroid satisfies a constant partition property, yet a recent work [1] has disproven this by demonstrating that binary matroids do not satisfy an $\alpha$ partition property for $\alpha \leq O(d^{1/4})$ ($d$ is the rank of the matroid). Thus, [1] and another independent study [10] have both negated the possibility of any constant approximate partition-based algorithm for the matroid secretary problem.
In this work, we both strengthen and deepen this distinction in two ways. First, we establish that linear matroids does not admit an $\alpha$-partition property for any $\alpha \leq O(d)$, and their special subclass, binary matroids, does not for any $\alpha \leq O(d/\log d)$. Second, we introduce an algorithm-independent structural distinction between these two classes, precluding the existence of constant approximate prophet inequality and contention resolution algorithms for matroids lacking constant partition property under pairwise independent distributions.

§ PRELIMINARIES

§.§ Notations

Throughout, we use bold, lowercase letters to signify vectors, with the $\ell^{\text{th}}$ component denoted by $\vec v(\ell)$. Sets are denoted by capital letters, while collections of sets are denoted by bold capitals. We let the set of positive integers up to $n$ as $[n]$. For a function $\phi: A \rightarrow B$, for any $E \subseteq A $, we define a multiset $\phi[E]:= \{\phi(a): a\in E\}$. For any finite set of elements $E$, we denote the set of all subsets of $E$ as $2^E$.
We denote downward-closed set-system over set of elements $E$ as $\M = (E,\I)$, where $\I$ is a downward closed subset of $2^{E}$.

We let $\Delta(2^E)$ as the set of all possible distributions over $2^E$. For any $\vec x\in [0,1]^{|E|}$, we let $\Delta_{pw}(2^{E})(\vec x) \subseteq \Delta(2^E)$ as the family of pairwise independent distributions over a subset of elements $E$ with marginals $\vec x$, i.e. for every $\mathcal D(\vec x)\in \Delta_{\text{pw}}(\vec x)$, $\Pr_{Q\sim \D(\vec x)}[e\in Q] = x_e$ and the events $\{e\in Q\}_{e\in E}$ are pairwise independent.

Similarly, we denote the set of possible non-negative weight/value distributions over the set of elements $E$ that (randomly) assigns a positive weight to each element in $E$ as $\Delta(\mathbb R_{\geq 0}^{E})$. We let $\Delta_{\text{pw}}(\R_{\geq 0}^{E}) \subseteq \Delta(\R_{\geq 0}^{E})$ be the class of pairwise independent weight distribution over elements $E$ such that for any $\D \in \Delta_{\text{pw}}$, any pair of $e, f \in E$ of elements and values $x,y \in \R_{\geq 0}$, $\Pr_{w \sim \D}[w(e)=x \wedge w(f)=y] = \Pr_{w \sim \D}[w(e)=x] \cdot \Pr_{w \sim \D}[w(f)=y]$. Throughout the paper, we exchangeably use the term “weight" and “value".

$\FF_q$ denotes a finite field of size $q$ and $\FF_q^d$ represents a vector space of dimension $d$ over $\FF_q$, where $q$ is a prime. We define $\FF_q^d \times [m]$ as a vector space $\FF_q^d$ with $m$ copies of each vector where each copy is labeled with an integer from $[m]$, i.e. $\set{\vec v^i:i\in [m] \text{ for all }\vec v \in \FF_q^d }$ with standard operations on $\FF_q^d$ [We assume that all vectors are column vectors]. We use capital letters to symbolize matrices over these finite fields, and their rank is denoted by $\rank(\cdot)$. A matrix $R \in \FF_q^{r \times c}$ is a  full row-rank matrix if $\rank(R)=r$, i.e. its rows constitute a set of linearly independent vectors.

§.§ Matroid Theory

We use standard definitions from matroid theory; for details see [41, 50]. A matroid $\M=(E,\I)$ is a set-system with elements $E$ and a family of independent sets $\I \subseteq 2^E$ satisfying the three matroid axioms. A weighted matroid incorporates a matroid $\M=(E, \I)$ with weights $w \in \R^E$ for its elements. By duplicating or making parallel labeled copies of each element of a matroid $\M=(E, \I)$ “$m$” times, we construct a larger matroid $\M^m=(E^m, \I^m)$, where $E^m=E \times [m]$ and $T \subseteq E^m$ is independent, $T \in \I^m$, if $\{e : e^i \in T\} \in \I$ and $|T\cap \{e^i: i\in [m]\}|\leq 1$ for all $e\in E$.

The rank function of matroid $\M=(E, \I)$ is indicated by $\rank^\M$, where $\rank^\M(S) = \max\{|T| : T\subseteq S, T \in \I\}$. Weighted version of the rank $\rank_w^\M$ is defined for weighted matroids $(\M,w)$ as $\rank^\M_w(S) = \max\{w(T): T\subseteq S, T \in \I\}$. The span function of matroid $\M$ is denoted by $\spn^\M(S)$ where $\spn^\M(S)=\{e \in E: \rank^\M(S \cup \{e\})=\rank^\M(S)\}$. We slightly abuse notation and use $\rank(\M)=\rank^\M(E)$ for the rank of the matroid. We may omit the superscript $\M$ whenever it is clear from the context.

A linear matroid $\M=(E,\I)$ consists of a vector space $E$ and independent sets $\I$ that form a linearly independent set of vectors in $E$. A binary matroid is a linear matroid defined on the vector space $\FF_2^d$ for $d\in \mathbb N$. Linear matroid with $E=\FF_q^d$ is referred to as full linear matroid over $\FF_q^d$.  We refer to matroid with $E=\FF_2^d$ as full binary matroid.

§.§ Contention Resolution Schemes

A contention resolution scheme (CRS) is a rounding technique introduced by Chekuri et al. [48] in the context of (offline) submodular function maximization.
More formally, given downward-closed set-system $(E,\I)$ over ground set $E$, let $P_\I$ be a convex relaxation of the constraints $\I \subseteq 2^E$, let $\vec x\in P_\I$ and set of active elments $Q \sim \D$ such that $\D \in \Delta(2^E)$ and $\Pr_{Q\sim \D}[e\in Q] = x_e$ for all $e\in E$. The goal of a CRS is to round the set $Q\sim \D$ (which is not necessarily feasible in $\I$) to a feasible set $I \in \I$ such that $I \subseteq Q$.  CRSes are judged by their balanced ratio: we say that a contention resolution scheme is $c$-balanced if for all $e\in E$, $\Pr[e \in I \mid e\in Q] \geq c$. Many natural classes of combinatorial constraints including matroids, matching, and knapsack are known to admit $\Omega(1) $- balanced contention resolution schemes when the marginals $\{e \in Q\}_{e\in E}$ are independent across elements.

For given $\vec x \in \P_\I$, in this work, we focus on CRS for matroids when $\D \in \Delta_{\text{pw}}(2^E)(\vec x)$.
In the following definition, we define CRS for matroids with pairwise independent distribution which is a special case of a more general definition that appeared in Dughmi [23].

A  pairwise independent CRS $\pi$ for a matroid $\M = (E,\I)$ is an algorithm that takes as input a point $\vec x \in P_\I$, distribution $\D(\vec x) \in \Delta_{\text{pw}}(2^E)(\vec x)$ and a set of active elements
$Q \sim  \D(\vec x)$ sampled from $\D(\vec x)$ and outputs a feasible subset $\pi_{\vec{x}}(Q)\in \I$. In addition, we say CRS $\pi$ is $c$-balanced (a.k.a, $\pi$ has balance ratio $c$) if for every $\vec{x}\in P_\I$ and any distribution
$\D \in \Delta_{\text{pw}}(2^E)(\vec x)$,

$$\Pr_{R\sim \D(\vec x)}[e\in \pi_{\vec x}(Q)] \geq c \cdot \Pr_{Q\sim \D(\vec x)}[e\in Q].$$

Finally, we state the following theorem from [23] that characterizes the set of distributions which admits balanced contention resolution schemes.

Given a matroid $\M=(E, \I)$, and let $\D$ be a distribution supported on $2^E$. The following are equivalent for every $\alpha \geq 1$,

* $\D$ admits an $\alpha$-balanced contention resolution map.

* For every weight vector $\w \in \R_{\geq 0}^E$, the following holds:
$ \Ex_{Q \sim \D}[\rank_{\w}(Q)] \geq \alpha \cdot \Ex_{Q \sim \D}[\w(Q)]$

§.§ Prophet Inequality

Given a downward closed sets-system $\M=(E, \I)$, a prophet inequality problem consists of weights $\w \in \R_{\geq 0}^E$ sampled from a known distribution $\D$ and a permutation $\lambda$ of $E$ potentially chosen by an adversary.
We take the perspective of the gambler, who knows $\mathcal M$ and the distribution $\D$ of the random variables $\{w(e)\}_{e \in E}$. The gambler starts with an empty set $S$ of accepted elements and then observes each element in $E$ in an order $\lambda$ chosen by an adversary. For the purposes of this paper, the gambler plays against the almighty adversary who knows the realization of all the elements in advance however in contrast to [28], the adversary, does not know the coin flips of the gambler's strategy. When the element $e \in E$ arrives, the gambler learns the realization of $w(e)$ and has to decide online whether to accept element $e$ or not based on $(e,w(e))$ and the previously accepted elements $S$. However, they can only accept $e$ if $S \cup \{e\}$ is feasible in $\mathcal M$. The gambler seeks to maximize their utility $\E_{\D} \left[ \sum_{e \in S} w(e) \right]$, and in particular to compete with a prophet who plays the same game and knows the realizations of all random variables in advance. If the gambler has a strategy guaranteeing an $\alpha$ fraction of the prophet’s expected utility in expectation, we say that we have an $\alpha$-approximate (or competitive) prophet inequality for a matroid $\M$ and the value distribution $\D$.
In this work, we focus on the matroid prophet inequality problem with the class of pairwise independent value distributions, i.e. $\D \in \Delta_{\text{pw}}(\R_{\geq 0}^{|E|})$.

§ OVERVIEW OF TECHNICAL RESULTS

In this section, we briefly present an overview of our techniques and results. Our results are a mixed bag: first, we identify limitations of algorithmic results for prophet inequalities and offline contention resolution schemes for matroids when inputs exhibit limited independence, particularly, pairwise independence. Our results essentially demonstrate the “complexity" of stochastic selection problems beyond independent priors. Next, we obtain constant factor prophet inequalities and offline contention resolution schemes for matroids that adhere to the so-called partition property, which includes the most common matroids encountered in combinatorial optimization—examples include graphic, co-graphic, transversal matroids, etc.

§.§ A Recipe for $k$-wise Independent Vector Families

Our exposition starts with an exploration of a methodology to generate pairwise independent distributions (or in a broader sense, $k$-wise independent distributions) over a vector space over a finite field. Consider $\vec r_1, \vec r_2$, two (stochastically independent) random vectors in $\FF_q^d$, selected uniformly at random, with each entry of $\vec r_1$ and $\vec r_2$ independently drawn from $\operatorname{Unif}\set{0, \dots q-1}$. We then define vectors $\vec x_1=\vec r_1, \vec x_2=\vec r_2, \vec x_3=\vec r_1+ \vec r_2$. It is notable that these vectors are pairwise independent, in other words, $\Pr[\vec x_i=\vec u \wedge \vec x_j = \vec v] = \Pr[\vec x_i=\vec u] \cdot \Pr[\vec x_j = \vec v]$ for any arbitrary $\vec u, \vec v \in \FF_q^d$, despite their lack of mutual independence. This follows from the fact that as long as any two distinct random vectors $\vec x_i$ and $\vec x_j$ (i.e. $i\neq j$) are not defined by the same linear combination of random vectors $\vec r_1, \vec r_2$, their embedding into higher dimensional vector space through a uniformly random linear map preserves their stochastic independence. Here, in essence, we perform a random transformation on the vector space $\FF_q^2$, and subsequently embed them randomly into the higher-dimensional space $\FF_q^d$.

We utilize random linear maps to generate pairwise independent (and more generally $k$-wise independent) random vectors.
We consider a set of deterministic vectors ${\vec \sigma_1, \dots \vec \sigma_T} \subseteq \FF_q^m$, where any pair of vectors are linearly independent (not multiples of each other).
Let $R \in \FF_q^{d \times m}$ be a uniformly random matrix, and $\Phi_R:\FF_q^m \rightarrow \FF_q^d$ be a linear function such that $\Phi_R(\vec \sigma) = R \cdot \vec \sigma$. Our first observation (in Lemma <ref>) is that the events $\{\Phi_R(\vec \sigma_i) = \vec u\}$ and $\{\Phi_R(\vec \sigma_j) = \vec v\}$ for any arbitrary $i\neq j \in [T]$ and $\vec u, \vec v \in \FF_q^d$ are independent. Additionally, for any non-zero $\vec \sigma \in \FF_q^m$ and $\vec u \in \FF_q^d$, we find that $\Pr[\Phi_R(\sigma)=u] = \frac{1}{|\FF_q^d|} = \frac{1}{q^d}$, meaning that each $\Phi_R(\sigma)$ is uniformly distributed over $\FF_q^d$ for any non-zero vector $\sigma \in \FF_q^m$.

In a nutshell, given the set of pairwise linearly independent vectors $\Sigma = \{\sigma_1, \dots \sigma_T\}$ for $T>m$, the random vectors $\Phi_R[\Sigma] = \{\Phi_R(\sigma) : \sigma \in \Sigma\}$ are pairwise independent and uniformly distributed over the space.
Notice that range of the linear map $\Phi_R$ lies in the column space of $R$. Therefore, $\rank(\Phi_R[\Sigma]) \leq m$, and so $\Phi_R[\Sigma]$ generates $T$ many pairwise independent vectors in $\FF_q^d$ with $\rank(\Phi_R[\Sigma]) \leq m <T$.
Hence, $\Phi_R[\Sigma]$ is contained in a subspace with a small rank while maintaining pairwise stochastic independence.

§.§ Optimal Pairwise Independent CRS for Matroids

The first application of random linear maps hinges on its ability to control the rank of the set of output vectors. As a first step, we construct an approximately pairwise independent distribution for a linear matroid $\M$ with rank $d$ defined on $\FF_q^d$ that does not admit $\frac{c}{d}$-balanced CRS for some constant $c$.
We construct a distribution $D\in \Delta_{pw}(2^E)$ in two steps: first, we choose $\Theta(d)$ many vectors $\Sigma$ from $\FF_q^c$ that are pairwise linearly independent, where $c$ is a universal constant (indeed $c=2$). By suitably choosing $q$ to be sufficiently large, we can ensure the existence of a set of pairwise linearly independent vectors $\Sigma \subseteq \FF_q^c$ with $|\Sigma| = d$. Second, we sample a uniformly random matrix $R \in \FF_q^{c \times d}$ and define $Q = \Phi_R[\Sigma]$ as the collection of vectors generated by the random linear map $\Phi_R$. When $d >> c$, with high probability, $R$ has full row-rank, making $\Pr[\vec v \in Q] \approx \frac{d}{q^d}$ for any $\vec v \in \FF_q^d$. It is noteworthy that the marginal probability vector of the above distribution is close to $\frac{d}{q^d} \cdot \vec{1} \in \P_M$.

Before we analyze the pairwise independence of the events $\{v \in Q\}_{v\in \FF_q^d}$, we informally show that the full linear matroid over $\FF_q^d$ does not admit $\frac{c}{d}$-balanced CRS for $\D$. We observe that by construction, $\rank_{\M}(Q) \leq c$ with probability one.

Therefore, we get

$$ \frac{\Ex_{Q \sim \Phi_R[\Sigma]}[\rank(Q)]}{ \Ex_{Q \sim \D}[|Q|]} \lesssim \frac{c}{d} = O\left(\frac{1}{d}\right). $$

Combining the above inequality with Lemma <ref>, we conclude that the full matroid on $\FF_q^d$ does not admit $\omega (1/d)$-balanced CRS for $\D$.

To address the technical challenges of the above approach, let $Q = \Phi_R[\Sigma]:=\set{\vec q_1, \dots, \vec q_d}$. We first observe that due to Lemma <ref>, for any two vectors $\vec v, \vec u \in \FF_q^d$ and $i\neq j \in [d]$, events $\{\vec q_i = \vec v\}$ and $\{\vec q_j =\vec u\}$ are independent of each other. However, the events $\{\vec v\in Q\}$ and $\{\vec u\in Q\}$ are not independent as once we condition on the event $\{\vec v\in Q\}$, $\vec u$ is less likely to be in the set $Q$ as the size of $Q$ is fixed with $|Q|=d$. At first glance, when $d$ is large, a fixed size of $Q$ seems to be a small technical hurdle. However, when the random matrix $R$ is not full rank, then with non-zero probability, the event $\{\vec q_i = \vec q_j\}$ can occur for any $i \neq j$. This makes the analysis of the pairwise independence property of the events $\{\vec v\in \FF_q^d\}_{\vec v \in \FF_q^d}$ notoriously difficult even when $d$ is large. On the brighter side, the random matrix $R$ has a full column rank with high probability which allow us to construct a distribution $\D$ over a slightly modified full $\FF_q^d$ matroid.

We overcome the aforementioned technical challenges and construct a linear matroid $\M$ and distribution over subsets of its elements that do not admit $\omega (1/\rank(\M))$-balanced CRS in Section <ref>. The actual construction is technically involved, hence, here we present a brief overview. We first construct $d$ duplicates of each vector in full linear matroid over $\FF_q^d$ and formulate a matroid $\M^d=(\FF_q^d \times [d], \I^d)$ (See Section <ref> for definition). By making copies, whenever the event $\{\vec q_i = \vec v\}$ and $\{\vec q_j = \vec v\}$ occurs, we can make two distinct copies of $\vec v$ active, i.e., we let two copies $\vec v, \vec v' \in Q$. Subsequently, we mix this distribution with a positively correlated distribution where all elements are active simultaneously to ensure that events $\{\vec v^j \in Q\}_{\vec v^j \in \FF_q^d \times [d]}$ are pairwise independent. Our technique here can be viewed as a generalization of Alon et.al [4] which construct $k$-wise independent distribution over $\{0,1\}^n$ from an almost $k$-wise independent distribution over $\{0,1\}^n$ with small total variation distance. The key difference is that their techniques heavily rely on the fact that each marginal of the joint distribution is almost $\operatorname{Ber}(1/2)$ which is not the case in our construction.

We complement this result with the existence of $\frac{1}{d}$-balanced CRS for matroids over the class pairwise independent distributions $\{\Delta_{\text{pw}}(\vec x): \vec x \in P_\I\}$. We observe that for any $\vec x \in P_\I$, weight assignment $\vec w\geq 0$ and $\D(\vec x)\in \Delta_{\text{pw}}(\vec x)$ we have

\begin{align*}
\Ex_{Q\sim \D(\vec x)}[\rank_{\vec w}(Q)] \geq \Ex \left[\max_{e\in Q} \vec w(e)\right] \geq \frac{1}{d} \cdot \sum_{e\in E}\vec w(e) \cdot \vec x(e) =\frac{1}{d} \cdot  \Ex_{R\sim \D}[\vec w(Q)].
\end{align*}

Hence, Theorem <ref> concludes that there existence of a $\frac 1 d$-balanced offline CRS for a matroid $\M$ with distribution $\D(\vec x)$.

§.§ Optimal Pairwise Independent Matroid Prophet Inequality

Let us first revisit the framework we use to fabricate bad examples for contention resolution schemes. Initially, we assemble a set of vectors, denoted by $\Sigma$, which lays the groundwork for constructing a “bad" distribution $\D \in \Delta_{\text{pw}}(2^E)$. We design $\Sigma$ to ensure two conditions: (i) the vectors within $\Sigma$ are pairwise linearly independent, and (ii) $\Sigma$ presents a “bottleneck" to the primary problem at hand. Following that, we use the random linear map $\Phi_R[\Sigma]$ to yield a set of random vectors (which are elements of the matroid at hand) that are pairwise independent and retain the “bottleneck" characteristics.

We adhere to this same blueprint for crafting a bad example for the Prophet Inequality problem. In what follows, we consider a full binary matroid $\mathbb F_2^{2d}$ and construct a pairwise independent weight distribution $\D\in \Delta_{\text{pw}}(\mathbb R_{\geq 0}^{|E|})$ over elements of $\FF_2^{2d}$. Formally, we create $\kappa=\Theta(\log d)$ many distinct weights $\{1,2^2 , \dots, 2^{\kappa-1}\}$ and (randomly) construct $\tau=\Theta(d)$ many vectors from $\FF_q^{2d}$ such that each vector is assigned one of the $\kappa$ many possible weights and rest of them are assigned a weight of zero. We refer to the vectors with weight $2^\ell$ as vectors at “level-$\ell$"; exchangeably; a vector at level $\ell \in [\kappa]$ is assigned a weight of $2^\ell$.
In constructing the weight assignments over the vectors from $\FF_2^{2d}$, we start by assembling a collection of “raw" vectors $\Sigma = \bigcup_{\ell}^\kappa \Sigma_\ell$ from the vector space $\FF_2^d$. Subsequently, we build “actual” vectors in level $\ell$ by applying a random linear map $\Phi_{R}: \FF_2^d \rightarrow \FF_2^{2d}$ to “raw” vectors $\Sigma_\ell$, i.e. $\Phi_R(\Sigma_\ell)$.

In the construction of each level, we ensure that the rank of the vectors at level $\ell$ is half the rank of vectors at level $\ell -1$.  In our construction, the span of vectors at level one has a rank of $\Theta(d)$. Therefore, the span of vectors at level $\ell$ has a rank of $\Theta\left( \frac d {2^\ell} \right)$. Moreover, the vectors from level $\ell$ are assigned a weight of $2^\ell$. As a result, we observe that the weighted rank of vectors at any level is $\Theta(d)$. The goal here is to construct these levels such that vectors from a given level fall within the span of vectors allocated at the lower levels.

For simplicity, let us assume that the vectors at each level form an independent set in the full matroid $\FF_2^{2d}$.
The essential “bottleneck" we strive to maintain is that vectors with smaller weights, or vectors at lower levels, span all vectors at higher levels, with the “contribution” of each level to the prophet's reward being roughly the same. Consequently, any constant approximate algorithm needs to select a constant fraction of vectors at each level.

To mislead any algorithm/gambler, we intend to ensure that when a vector from level $\ell$ is chosen, without knowing the set of vectors from level $\ell ' > \ell$, then each vector from level $\ell'$ is spanned with a constant probability; this is the key objective of our construction. So, any algorithm oblivious to the vectors in the higher level that selects a vector at level $\ell$ ends up spanning each vector at a higher level with a constant probability. As a result, the algorithm will only be able to select vectors from $O(1)$ many levels before it spans all the vectors at a higher level with a probability of at least $1-o(1)$, leading to the lower bound of $\Omega(1/\kappa)$.

It is not very difficult to construct such weight assignments with arbitrarily correlated distribution. Therefore, the key challenge here is to maintain the “bottleneck" of the problem while preserving pairwise independence.  We overcome this challenge by encoding the underlying bottleneck into $\Sigma = \bigcup_{\ell =1}^\kappa \Sigma_\ell$. To do that,
we choose “raw" basis vectors $B_\ell$ from the canonical basis of $\FF_q^d$ in a way that $B_1 \supseteq B_2 \dots \supseteq B_\kappa$. This selection forms a nested system of subspaces $\mathbf{Span}(\Phi_R[B_\ell])$ for $\ell \in [\kappa]$ within the embedded vector space of $\FF_q^{2d}$. Next, we create “raw" vectors $\Sigma_\ell$ for each level as linear combinations of vectors in $B_\ell$. Therefore, $\mathbf{Span}(\Sigma_\ell) \subseteq \mathbf{Span}(B_\ell)$ and $\mathbf{Span}(\Phi_R(\Sigma_\ell)) \subseteq \mathbf{Span}(\Phi_s(B_\ell))$. However, in the construction of $\Sigma_{\ell}$, there is a possible pitfall that results in $\Sigma_\ell \cap \spn(B_{\ell-1}) = \emptyset$. This condition might inadvertently assist the gambler to extract a significant fraction of the reward in higher levels, even without knowledge of upcoming levels. To evade this trap and to ensure that $\Sigma := \bigcup_{\ell=1}^\kappa \Sigma_\ell$ serves as a tool for crafting a pairwise independent weight assignment yielding high prophet reward, we choose $\Sigma$ to meet certain criteria:

$\Pr[\sigma \in \spn(B_{\ell+1}) \mid B_\ell, \Sigma_\ell]
% = \Pr[\sigma \in \spn(B_\ell \setminus B_{\ell+1}) \mid B_\ell, \Sigma_\ell]
= \frac{1}{2}$ for any vector $\sigma \in \Sigma_\ell$

*  $\rank(\Sigma_\ell) = |\Sigma_\ell| = |B_\ell|/2$, i.e. $\Sigma_\ell$ consists of linearly independent vectors of size $|B_\ell|/2$,

*  $\Sigma := \bigcup_{\ell=1}^\kappa \Sigma_\ell$ are pairwise linearly independent vectors.

For now, let's assume the existence of $\Sigma_\ell$ and $B_\ell$ satisfying the above properties. The technical details for the construction of such $\Sigma_\ell$ and $B_\ell$ are described in Procedure <ref> (Section <ref>).

Consider $X=\Phi_R[\Sigma]$ to be a subset of $\Ftdd$ representing the collection of vectors upon application of the random linear map. Property <ref> implies that the elements of $X$ are pairwise independent vectors. As a natural next step, we would attempt defining a weight assignment $w(\vec v)=2^\ell$ if $\vec v \in \Phi_R[\Sigma_\ell]$. However there are two key challenges that hinder such distributions to be pairwise independent: first, each level contains a fixed number of vectors.  Hence, once conditioned on $w(\vec v) = 2^\ell$, the probability of all remaining vectors to receive the weight $2^\ell$ decreases.

The second, and more challenging technical obstacle, is that this form of weight assignment cannot be considered valid, as $\vec v \in \FF_2^{2d}$ might be part of both $\Phi_R[\Sigma_\ell]$ and $\Phi_R[\Sigma_{\ell'}]$ for distinct $\ell, \ell' \in [\kappa]$, and this happens with a non-zero probability. Despite this, such an event has a small probability of occurrence since the random matrix $R \in \FF_2^{2d \times d}$ become full column-rank with high probability. As $X$ is a set of linear combinations of columns of $R$, when $R$ is a full column-rank matrix, each vector can appear in at most one of the levels. Thus, the weight assignment is “approximately” valid which allows us to construct a valid weight assignments that preserves the required bottleneck for any prophet inequality algorithm with high probability. The actual construction is more involved and deferred to Section <ref>.

For the sake of exposition, let us momentarily consider the above weight assignment distribution $\D$ as a valid and pairwise independent. We define an arrival order of elements (vectors) to the gambler as $\Phi_R[\Sigma_1], \Phi_R[\Sigma_2], \dots \Phi_R[\Sigma_\kappa]$ where elements (vectors) within each group are arranged arbitrarily. This ordering necessitates an adversary who knows all weight realizations beforehand. Assuming provisionally that $w$ is a valid weight assignment, it is observed that Property <ref> and Property <ref> ensure that

$$\Ex[\rank_w(\Phi_R[\Sigma_\ell \cap \spn(B_\ell \setminus B_{\ell+1})])] = \Ex[\rank_w(\Phi_R[\Sigma_\ell \cap \spn(B_\ell)])] = \frac{|B_\ell|}{4}.$$

Therefore, a prophet who knows all the weights in advance can select the set of items $S^* := \bigcup_{\ell=1}^\kappa \Phi_R[\Sigma_\ell \cap \spn(B_\ell \setminus B_{\ell+1})]$ and guarantee that

\begin{align*}
\Ex[\rank_w(S^*)]
&= \sum_{\ell=1}^\kappa \Ex[\rank_w(\Phi_R[\Sigma_\ell \cap \spn(B_\ell \setminus B_{\ell+1})])] \\
&= \sum_{\ell=1}^\kappa 2^\ell \cdot \frac{|B_\ell|}{4} = \sum_{\ell=1}^{\kappa} 2^\ell \cdot \frac{d}{2^{\ell-1} \cdot 4} \\
&= \Omega(\kappa \cdot d).
\end{align*}

On the other hand, when gambler selects $\rho_\ell$ many vectors at level $\ell$, we can leverage concentration inequalities (assuming $d=2^{O(\kappa)}$) and Property <ref> to demonstrate that, with high probability, roughly  $\rho_\ell \cdot \frac{1}{2^{\ell' - \ell}}$ of these vectors will reside in the $\spn(B_{\ell'})$ for any $\ell' \geq \ell$. Additionally, notice that $|B_{\ell'}| = |B_\ell| \cdot \frac{1}{2^{\ell' - \ell}}$. Roughly speaking, $\rho_\ell$ many selected vectors at level $\ell$ spans $\rho_\ell/|B_\ell|$ fraction of the rank of level $\ell'$.
As a result, one can show that for any gambler/algorithm, the sum of fractions of vectors selected from each level is upper-bounded by a universal constant with high probability. Given that the maximum reward obtainable from each level is upper-bounded by $\approx 2^\ell \cdot \frac{d}{2^{\ell-1}} = 2d$, a gambler can achieve the expected reward of $O(d)$. Thus, we have

$$ \frac{\Ex[\text{reward of gambler}]}{\Ex[\text{reward of prophet}]} = \frac{O(d)}{\Omega(\kappa \cdot d)} = O\left(\frac{1}{\kappa}\right) = O\left(\frac{1}{\log d}\right).$$

Lastly, we readdress the techniques used to tackle challenges in creating pairwise independent weight assignments, utilizing a method similar to the CRS construction outlined in a previous section but more involved.
First, we generate $\tau$ many copies of each vector in $\Ftdd$ and obtain a matroid $\M^\tau=(\Ftdd \times [\tau], \I^\tau)$. Next, whenever $\vec v\in \FF_2^{2d}$ appears at different levels, different copies of $\vec v \in \FF_2^{2d}$ are assigned different weights. This way, the resulting distribution becomes “valid". Later, we mix this distribution with two others, one in which all weights are uniformly at random and the other where we randomly select a level $\ell$ and assign all weights to $2^\ell$. Technical details of the description of weight assignment distribution are presented in Section <ref>.

We later introduce an algorithm for the pairwise independent matroid prophet inequality, that matches the upper bound of $O \left( 1 /{\log \rank} \right)$ up to a constant factor. Our algorithm's primary strategy is to group the matroid elements into $O(\log \rank)$ buckets based on their weights. This ensures that within the same bucket, the weight of any two elements is within a factor of $2$ of each other. Following this, we employ a greedy algorithm on the group of elements yielding the highest expected reward. Given that there are $\log \rank$ total groups, our algorithm achieves an approximation factor of $\Omega (1/\log \rank)$. However, one must note that the elements can have weights in $\mathbb R_{\geq 0}$, suggesting the possibility of a group where the weights of elements might vary significantly. We address this challenge in our analysis by leveraging local-lemma type results for the pairwise independent set of events, as proposed in [18], showing that this particular bucket with high probability contains at most one element.

§.§ Stochastic Selection with Partition Property

Finally, we show that when the input matroid $\M$ admits  the $\alpha$-partition property (Formally defined in Section <ref>), allowing the matroid to be approximated by a (random) simple partition matroid, then we can transform the pairwise independent Contention Resolution and Prophet Inequality problems into parallel instances of the same problem with rank one matroid constraints.
To do this, we leverage the $\frac{1}{3}$-approximate pairwise independent prophet inequality for the rank one matroid from [18].
For the construction of a reduction algorithm for Contention Resolution, we first prove a $\frac 1 4$-balanced pairwise independent CRS for the one-uniform matroid. Following this, by exploiting a result from convex geometry, we transform the input distribution of CRS for a general problem into valid input distributions (specifically, ex-ante feasible) for simple partition matroids, thereby simplifying the CRS problem to instances on partition matroids.

§ BUILDING BLOCK: RANDOM LINEAR MAPS

In this section, we devise a generic tool to produce random vectors displaying limited independence, relying solely on a uniformly random map between two finite vector spaces. For two vector spaces $\FF_q^m$ and $\FF_q^d$ over the same finite field $\FF_q$, a random linear map assigns basis vectors of $\FF_q^m$ randomly to vectors in $\FF_q^d$. We demonstrate that this random map transforms linear independence in the domain vector space $\FF_q^m$ into stochastic independence in the range vector space $\FF_q^d$.

To elaborate, consider $R \in \FF_q^{d \times m}$ to be a uniformly random matrix, where each entry $r_{i,j}$ is sampled independently according to the uniform distribution over the finite set of elements $\set{0, 1, \dots, q-1}$. We define a random linear map $\Phi_R: \FF_q^m \rightarrow \FF_q^d$ as $\Phi_R(\sigma) = R \cdot \sigma$. One can also verify that when $R$ is sampled uniformly, $\Phi_R$ has a uniform distribution over all possible linear functions from $\FF_q^m$ to $\FF_q^d$. Let $\Sigma \subseteq \FF_q^m$ be a collection of $k$-wise linearly independent vectors, implying that any subset of size $k$ from $\Sigma$ consists of linearly independent vectors, which we refer to as “raw” vectors. We then observe that by applying the random linear map $\Phi_R$ to these “raw” vectors $\Sigma$, we obtain a collection of $k$-wise stochastically independent vectors. The following lemma formalizes this discussion.

Let $\Sigma \subseteq \mathbb F_q^{m}$ be a collection of vectors $\vec \sigma_1,\dots , \vec \sigma_n \in \mathbb F_q^m$ which are $k$-wise linearly independent, $R\in \FF_q^{d \times m}$ be a uniformly random matrix with entries $r_{i,j} \sim \operatorname{Unif}\left( 0,1,\dots ,q-1\right)$ and $\vec X = \Phi_R[\Sigma]$ with vectors $\vec x_1, \dots \vec x_n$. Then for any subset $S \subseteq[n]$ of size at most $k$ and vectors $\vec v_i\in \FF_q^d$ for $i \in S$, events $\{\vec x_i = \vec v_i\}_{i\in S}$ are mutually independent. Moreover, for any $i\in [n]$ and $\vec v\in \FF_q^d$, $\Pr[\vec x_i = \mathbf v] = \frac{1}{q^d}$.

Let $S' \subseteq S$ be an arbitrary subset and $\vec v_i \in \FF_q^d$ be an arbitrary vector for all $i \in S'$. We note that $|S'|\leq k$.
We start by observing that

\begin{align*}
\Pr\left[ \bigwedge_{i \in S'} \{\vec x_i = \vec v_i\} \right]
&= \Pr \left[ \bigwedge_{i \in S'} \left\{ \sum_{j=1}^m \Phi_R[\sigma_i] = \vec v_i \right\} \right]\\
&= \Pr \left[ \bigwedge_{i \in S'} \bigwedge_{\ell=1}^d \left\{ \sum_{j=1}^m r_{\ell, j} \cdot \sigma_i(j) = \vec v_{i}(\ell) \right\} \right] \\
&= \Pr \left[ \bigwedge_{\ell=1}^d \bigwedge_{i \in S'} \left\{ \sum_{j=1}^m r_{\ell, j} \cdot \sigma_i(j) = \vec v_{i}(\ell) \right\} \right] \\
&= \prod_{\ell=1}^d \Pr \left[ \bigwedge_{i \in S'} \left\{ \sum_{j=1}^m r_{\ell, j} \cdot \sigma_i(j) = \vec v_{i}(\ell) \right\} \right] && (\text{disjoint set of RVs})
\end{align*}

For a fixed $\ell \in [d]$, consider the system of equations with variables $\theta_{j}$ for all $j \in [m]$

$$ \sum_{j=1}^m \theta_{j} \cdot \sigma_i(j) = \vec v_{i}(\ell) \qquad \forall i \in S'. $$

Notice that as $|S'|\leq k$, the subset $\Sigma_{S'} \subseteq \FF_q^{m}$ with vectors $\{\sigma_i \mid i \in S\}$ induces linearly independent vectors by  the definition of $\Sigma$. Therefore, the set of variables that satisfies the system of equations induces a subspace of dimension $m-|S'|$, call $\Theta$. Since any $d$ dimensional subspace of $\FF_q^m$ contains $q^d$ many points, $|\Theta| = q^{m-|S'|}$. Thus, whenever the vector
$(r_{\ell,1}, r_{\ell,2}, \dots r_{\ell,m})$ is in $\Theta$, then $\sum_{j=1}^m r_{\ell, j} \cdot \sigma_{i}(j) = x_{i}(\ell)$ for all $i \in S'$.
So, we can compute the probability as follows.

$$ \Pr\left[ \bigwedge_{i \in S'} \{\vec x_i = \vec v_i\} \right] = \prod_{\ell=1}^d \Pr \left[ \bigwedge_{i \in S'} \left\{ \sum_{j=1}^m r_{\ell, j} \cdot \sigma_{i}(j) = \vec v_{i}(\ell) \right\} \right] = \left(\frac{q^{m-|S'|}}{q^m}\right)^d = q^{-d\cdot |S'|}. $$

On the other hand, the product of probabilities can be computed as

\begin{align*}
\prod_{i \in S'} \Pr[ \vec x_i = \vec v_i] &= \prod_{i \in S'} \Pr \left[ \bigwedge_{\ell=1}^d \set{\sum_{j=1}^m r_{\ell, j} \cdot \sigma_i(j) = \vec v_i(j)} \right] = \prod_{i \in S'} q^{-d} = q^{-d \cdot |S'|}.
\end{align*}

The second equality follows from the fact that $\sigma_i$ is a non-zero vector and a non-zero combination of uniformly random vectors is also a uniformly random vector over $\mathbb F_q^d$. The latter claim can be proved by showing that uniformly random distribution will be preserved under scaling and translation. Thus, we conclude that

$$ \Pr\left[ \bigwedge_{i \in S'} \{\vec x_i = \vec v_i\} \right] = \prod_{i \in S'} \Pr[ \vec x_i = \vec v_i]. $$

Hence the events $\{\vec x_i = \vec v_i\}_{i\in S}$ are mutually independent and $\Phi_R[\Sigma]$ forms $k$-wise independent vectors.

Next, we present a well-known fact about random matrices defined over finite fields. For the self containment of the paper, we provide a simple proof.

Let $R \in \FF_q^{d \times m}$ be a uniformly random matrix, i.e., $R$ be a matrix where each entry is $\operatorname{Unif}(\{0, 1, \dots q-1\})$. Then, for any $m<d$, we have $\Pr[\rank(R)=m] \geq 1-\frac{1}{q^{d-m}}.$

The proof of this lemma proceeds via induction on $m$. The base case where $m=1$ is straightforward, as $\rank(R) \geq 0$, which validates the claim. For the induction step, consider $m>1$, and let $R \in \FF_q^{d \times m}$ be a matrix generated uniformly at random with column denoted by $\vec r_1, \dots \vec r_m$. Then, we have the following:

\begin{align*}
&\Pr[\rank(R)=m] \\
&= \Pr[\rank(\vec{r}_1, \dots \vec{r}_{m-1}) = m-1] \cdot \Pr[\vec{r_m} \notin \spn(\vec{r}_1, \dots \vec{r}_{m-1}) \mid \rank(\vec{r}_1, \dots \vec{r}_{m-1}) = m-1]\\
&\geq \left(1-\frac{1}{q^{d-m+1}}\right) \cdot \Pr[\vec{r_m} \notin \spn(\vec{r}_1, \dots \vec{r}_{m-1}) \mid \rank(\vec{r}_1, \dots \vec{r}_{m-1}) = m-1]\\
&= \left(1-\frac{1}{q^{d-m+1}}\right) \cdot \left(1-\frac{1}{q^{d-m+1}} \right)\geq 1-\frac{2}{q^{d-m+1}}\\
&\geq 1-\frac{q}{q^{d-m+1}}=1-\frac{1}{q^{d-m}}.
\end{align*}

Above, the first inequality follows from the induction on $m$. The second equality holds since $\vec r_m$ is a sampled independent of $\vec r_1,\dots , \vec r_{m-1}$ and  uniformly from $\FF_q^d \setminus \spn(\vec r_1 , \dots, \vec r_{m-1})$ once conditioned on the event $\vec r_m \notin \spn(\vec r_1,\dots , \vec r_{m-1})$. Hence, $\Pr[\vec r_m \notin \spn(\vec{r}_1, \dots \vec{r}_{m-1})\mid \rank(\vec r_1,\dots ,\vec r_{m-1})] = \left(1-\frac{1}{q^{d-m+1}} \right)$.

The following observation, derived from the preceding lemma, essentially states that when the dimension of the range space is considerably larger than that of the domain space, a random linear map tends to become a random linear “embedding” (or an injective function) with a high probability. This observation plays a crucial role in addressing potential issues that could arise from the multiple generations of the same vector in later sections.

Given that the random matrix $R$ possesses full row-rank, the mapping function $\Phi_R:\Ft^{m} \rightarrow \Ft^{d}$ forms a injection, i.e., $\Phi_R(\vec v) = \Phi_R(\vec u)$ holds true if and only if $\vec u=\vec v$. Consequently, when $m < d$, with probability at least $1-\frac{1}{q^{d-m}}$, $\Phi_R$ is one-to-one.

§ LIMITS OF PAIRWISE INDEPENDENT CONTENTION RESOLUTION

In this section, we show that there exists a matroid $\M=(E,\I)$ with rank $2d$ and pairwise independent distribution $\D \in \Delta_{\text{pw}}(2^E)$ that does not admit $O\left( \frac 1 d \right)$-balanced CRS. In particular, we consider the matroid $\M^d = (\FF_q^{2d} \times [d] , \I^d)$ which consists of $d$ labeled copies of each element in full linear matroid $\FF_q^{2d}$, and construct distribution $\D$ over $2^{\FF_q^{2d} \times [d]}$ described in Procedure <ref>. The following is the main theorem of this section:

For $d>2$ and some prime $q>d$, there is no $\frac{3}{d}$-balanced CRS for full linear matroid over $\FF_q^{2d}$.

The key idea here is to construct $d$ many vectors uniformly from $\FF_q^{2d} \times [d]$ with rank $O(1)$ such that each vector is included in the collection independently from any other vector. At a high level, we construct such a collection of vectors as follows: first, construct $d$ many pairwise linearly independent vectors  $\Sigma \subseteq  \FF_q^c$ where $c=2$. In Lemma <ref>, we show the existence of such $\Sigma$ when the $q$ is large enough. Next we consider random linear map $X = \Phi_R[\Sigma] = \{\vec x_1,\dots , \vec x_d\}$ where $R$ is a uniformly random matrix in $\FF_q^{2d \times c}$.

Next, we consider a random permutation $\pi^\vec v$ for each $\vec v \in \FF_q^{2d}$ independently and include each labeled copy $\vec v^i \in \FF_q^{2d} \times [d]$ into the set of active elements $A$ if $\vec x_{\pi(i)} = \vec v$. Recall that Lemma <ref> implies that the events $\{\vec x_{i'} = \vec v\}$ and $\{\vec x_{j'} = \vec u\}$ are independent for any $\vec u, \vec v \in \mathbb F_q^{2d}$ and $i'\neq j' \in [d]$. However, for any distinct pairs of $\vec v^i, \vec u^j \in \FF_q^{2d} \times [d]$, if $\vec v^i$ is active, the probability of $\vec u^j$ being active decreases as $A$ has fixed size of $d$. To overcome this hurdle, with a small probability, we let $A = \mathbb F_q^{2d}\times [d]$. Combining everything, we describe our distribution in Procedure <ref>.

Pairwise Independent Set of Active Elements of $\mathcal M^{2d}_q$
Dist - I :  $\mathcal D_1$

Initialize $A \leftarrow \emptyset$.

* Independently for each $\vec v \in \FF_q^{2d}$, consider a uniformly random permutation $\pi^{\vec v} \sim \Pi[d]$.

Independently for each $\vec v\in \FF_q^{2d}$, define the set of available copies $N^{\vec v}$ as follows

\begin{equation*}
N^{\vec v} = \begin{cases}
\text{Uniformly random  subset of $ [d]$ of size $d/2$} & \text{w.p. } a(d):=\frac{d \cdot (d-2)}{(d-1)^2}\\
\emptyset & \text{otherwise}.
\end{cases}
\end{equation*}

* Let matrix $R\in \FF_q^{c\times 2d}$ to be a random matrix with entries $r_{ij} \sim \operatorname{Unif} \left\{ 0,1,\dots, d-1  \right\}$ independently.

* Let $\Sigma^{\text{CRS}} \subseteq \FF_q^c$ be a collection of pairwise linearly independent $d$ many vectors.

* Define $X = \Phi_R[\Sigma^{\text{CRS}}]$ with vectors $\vec x_1 ,\dots \vec x_d$.

* For all $t \in [d]$, if $\vec v=\vec x_{\pi^{\vec v}(t)}$ then $\vec v^t \in A$ if and only if $t \in N^{\vec v}$.

Dist II : $\mathcal D_2$

* Set $A \leftarrow E^d$.

Dist III : $\mathcal D_3$

* Set $A \leftarrow \emptyset$.

Sample active elements $A$ from $\mathcal D_1$ w.p $p:=1-\frac{1}{q^{2d}}$, $\mathcal D_2$ w.p. $\delta$, and $\mathcal D_3$ w.p. $1-p-\delta$.

In the rest of this section, we aim to prove that Procedure <ref> creates a valid pairwise independent distribution in $\Delta_{\text{pw}}\left(2^{E^d}\right)$. More specifically, we want to show that

\begin{equation}
\Pr[\vec v^i \in A \land \vec u^j \in A] = \Pr[\vec v^i \in A] \cdot \Pr[\vec u^j \in A]
\end{equation}

for any pairs of distinct labeled vectors $\vec v^i, \vec u^j \in \mathbb F_q^{2d}\times [d]$. Observe that even if $\vec v$ equals $\vec u$, the indices $i$ and $j$ associated with them must be distinct. Before delving into probabilistic assurances, we first establish that $\D_1$ is a valid distribution. The only non-trivial part in constructing $\D_1$, specifically Step <ref>, is validated through the subsequent lemma.

Given that $d \cdot q \leq q^c$, there exists a set of vectors $\Sigma^{\text{CRS}} \subset \FF_q^c$, which consists of $d$ pairwise linearly independent vectors.

For any vector $\vec v$ in $\FF_q^c$, the set of scalar multiples $D_{\vec v}$ defined as $\{i \cdot \vec v : i \in \{0, \dots, q-1\}\}$ comprises all vectors linearly dependent on $\vec v$. For any group of vectors $\vec v_1, \dots, \vec v_t \in  \mathbb F_q^c$ with $t < d$,  there exists a vector $\vec u \in \FF_q^c \setminus \bigcup_{j=1}^t D_{\vec v_j}$ which is orthogonal to all $\vec v_1, \dots \vec v_t $  since $|D_{\vec v_j}| = q$ and $|\FF_q^c|=q^c \geq d \cdot q > t\cdot q$. Therefore, a set $\set{\vec v_1, \dots, \vec v_d}$ exists within $\FF_q^c$, and these vectors are pairwise linearly independent.

For the rest of the section, we set $q$ as the nearest prime larger than $d$. Next, we continue by calculating the marginal probabilities for each element and joint probabilities for different pairs, as outlined in the subsequent lemma. The proof of the lemma involves probabilistic calucations and delegated to Appendix <ref>
For any distinct pairs of labeled vectors $\vec v^i, \vec u^j \in \mathbb F_{q}^{2d} \times [d]$,

\begin{align*}
\Pr[\vec v^i \in A] = \frac{p \cdot a(d)}{2 \cdot q^{2d}} + \delta
\qquad\text{and}\qquad
\Pr[\vec v^i, \vec u^j \in A] = \frac{p}{4 \cdot q^{4d}} \cdot \left(\frac{d-2}{d-1}\right)^2 + \delta.
\end{align*}

At this point, we are prepared to present the lemma that verifies Procedure <ref> generates a valid pairwise independent distribution. The proof of the lemma is delegated to Appendix <ref>.
There exists $\delta>0$ such that

* $p+\delta \leq 1$, in particular, $\delta = O(\frac{1}{q^{4d}})$.

* $\Pr[\vec v^i, \vec u^j \in A] = \Pr[\vec v^i \in A] \cdot \Pr[\vec u^j \in A]$ for any two distinct items $\vec v^i, \vec u^j \in \mathbb F_{q}^{2d} \times [d]$.

We now demonstrate that $A$, when sampled in accordance with Procedure <ref>, does not admit $\omega(1/d)$-balanced contention resolution map. Due to Lemma <ref>, it is enough to prove that $\Ex_{A\sim \D}[\rank(A)] \leq O(1/d) \cdot \Ex_{A\sim \D}[|A|]$. The following lemma proves this fact.

$\Ex[\rank(A)] \leq \frac{c+1}{d} \cdot \Ex[|A|] = \frac{6}{\rank(\M^d)} \cdot \Ex[|A|].$

We observe that

\begin{align*}
\Ex[\rank(A)] &= \Ex[\rank(A) \mid A \sim \D_1] \cdot \Pr[A \sim \D_1] + \rank(M) \cdot \Pr[A \sim \D_2]\\
&\leq \Ex[\rank(A) \mid A \sim \D_1] + \frac{2d}{q^{4d}} && \left(\delta \leq \frac{1}{q^{4d}}\right)\\
&\leq c + \frac{2d}{q^{4d}} \leq c+1.
\end{align*}

Since $|A| \geq d$ with probability $1$, we have $\Ex[\rank(A)] \leq \frac{c+1}{d} \cdot \Ex[|A|]$. This completes the proof as $c=2$ and $\rank(\M^d)=2d$.

In the following, we demonstrate that the marginal probabilities of each element's inclusion in $A$ reside within the matroid polytope, denoted as $\P_{\I^d}$.

Let $\vec \mu$ be the marginal probability vector of $A$ where $\mu(\vec v^i)=\Pr_{A \sim \D}[\vec v^i \in A]$. Then,
$\vec \mu \in P_{\I^{d}}$.

Lemma <ref> implies that,

\begin{align*}
\mu(\vec v^i) = \Pr[\vec v^i \in A] = \frac{p \cdot a(d)}{2 \cdot q^{2d}} + \delta \leq \frac{1}{q^{2d}}.
\end{align*}

For any subset $S \subseteq \mathbb F_q^{2d} \times [d]$, observe that

$$\mu(S):= \sum_{\vec v^i \in S} \mu(\vec v^i) \leq |S| \cdot \frac{1}{q^{2d}} \leq \frac{d \cdot q^{\rank(S)}}{q^{2d}} \leq \frac{2d \cdot q^{\rank(S)}}{\rank(S) \cdot q^{2d}} \cdot \frac{\rank(S)}{2}\leq \frac{\rank(S)}{2}.$$

Above, the second inequality holds because $|S| \leq d\cdot q^{\rank(S)}$ as we have $d$ copies of each $\vec v\in \FF_q^{2d}$ in $\mathbb F_q^{2d} \times [d]$. The last inequality follow from the fact that $x q^{-x}$ is a decreasing function of $x$ and $\rank(S) \leq 2d$, hence, $\frac{2d \cdot q^{\rank(S)}}{\rank/2 \cdot q^{2d}} \leq 1$. Thus, $\vec \mu \in P_{\I^{d}}$.

Now we are ready to prove Theorem <ref>.

From Lemma <ref>, we conclude that the set $A$ sampled from the distribution described in Procedure <ref> has marginal inside the full linear matroid over $\FF_q^{2d}$ polytope which is pairwise independent due to Lemma <ref>. Moreover, Lemma <ref>, characterization of CRS in Lemma <ref> and $q>d$ completes the proof of the theorem.

§ LIMITS OF PROPHET INEQUALITY WITH PAIRWISE INDEPENDENT PRIORS

In this section, we construct an instance of the prophet inequality problem with pairwise independent priors that rules out $\omega\left(\frac{1}{\log \rank}\right)$-competitive pairwise independent prophet inequality. We consider a full binary matroid  of rank $2d$ with $\tau$ many copies of each element denoted as $\M^\tau = (E^\tau, \I^\tau)$, i.e. $E^\tau := \FF_2^{2d}\times [\tau]$. The exact value of $\tau$ will be determined later. Our objective is to create a pairwise independent weight distribution over $E^\tau$ such that any algorithm, which does not have prior knowledge of all weight realizations, fails to select an independent set with a high reward.

§.§ Construction of Pairwise Independent Weight Distribution

Revisiting the key concept we discussed in Section <ref>, our approach involves constructing $\kappa$ levels. Elements from $E^\tau$ are randomly (though not necessarily uniformly) assigned into one of these levels, with elements at level $\ell$ receiving a weight of $2^\ell$. This randomized assignment of elements from $E^\tau$ at level $\ell$ is achieved by applying a random linear map $\Phi_{R}: \FF_2^d \rightarrow \FF_2^{2d}$ to a strategically assembled, pairwise linearly independent (random) collection of vectors (in $\FF_2^{d}$), denoted as $\Sigma_\ell$. This random map yields a vector in $\FF_2^{2d}$ for each input vector from $\Sigma_\ell$, and hence, an element from matroid $\M^\tau$.

To construct $\Sigma_\ell$, we start at the first level with the principal bases vectors of $\FF_2^d$, denoted as
$B_1 = \set{\vec e_1, \dots \vec e_{d}}$, call them “alive" basis vectors of level one. At each iteration $\ell$, we randomly select half of the alive basis vectors from $B_{\ell-1}$ to form $B_\ell$. It is crucial to understand that $B_\ell$ is not selected uniformly at random from $B_{\ell - 1}$, but instead is cleverly engineered to “deceive” any prophet inequality algorithm.
Subsequently, $\Sigma_\ell$ is constructed as linear combinations of the alive basis vectors from $B_\ell$. As we revisited in Section <ref>, $\Sigma_\ell$ and $B_\ell$ fulfill the following conditions:

$\Pr[\sigma \in \spn(B_{\ell+1}) \mid B_\ell, \Sigma_\ell]
% = \Pr[\sigma \in \spn(B_\ell \setminus B_{\ell+1}) \mid B_\ell, \Sigma_\ell]
= \frac{1}{2}$ for any vector $\sigma \in \Sigma_\ell$

$\rank(\Sigma_\ell) = |\Sigma_\ell| = |B_\ell|/2$, i.e. $\Sigma_\ell$ consists of linearly independent vectors of size $|B_\ell|/2$,

$\Sigma := \bigcup_{\ell=1}^\kappa \Sigma_\ell$ forms a pairwise linearly independent vectors.

Detailed construction of $\Sigma_\ell$ and $B_\ell$ is presented in Procedure <ref>.
To help understand the process, we give a brief explanation of the construction. We initially identify the set of principal basis vectors as the alive basis vectors, which is denoted as $B_1=\set{\vec e_1, \dots \vec e_d}$. We then partition $B_1$ into $\vec P_1=\set{P_1(i): i \in [d/2]}$, with each element $P_1(i)$ containing two individual basis vectors, precisely, $P_1(i)=\set{\vec e_{2i-1}, \vec e_{2i}}$. We then assemble $\Sigma_1=\set{\vec e_1, \vec e_3, \dots \vec e_{d-1}}$ by selecting the first vector in each part.

Subsequently, we randomly pick half of the parts from $\vec P_1$ to establish $\vec {\bar P_1}$. For simplicity in our discussion, we will renumber the selected parts in $\vec{ \bar P_1}$ as $\set{ \bar P_1(i): i \in [d/4]}$. Following this, we combine consecutive parts in $\vec { \bar P_1}$ to create the second level partition, formally denoted as $\vec {P_2}=\set{P_2(j): j \in [d/8]}$, where $P_2(j)=\bar{P}_1(2j-1) \cup \bar{P}_1(2j)$. Essentially, the collection of basis vectors that appear in a part of $\vec{\bar P_1}$ becomes the “alive" basis vectors at level two. Notice that each basis vector from the first level appears in the second level with a probability of $\frac 1 2$ (with possible correlations across vectors).

Continuing with the construction of $\Sigma_2$, we focus on a specific index $j \in [d/8]$. We enumarate the vectors in $P_2(j)$ as $\set{\vec v'_1, \vec v'_2, \vec v'_3, \vec v'_4}$, and construct $\Sigma_2(j)=\set{\sigma_1=\vec v'_1 + \vec v'_2, \sigma_2=\vec v'_2 + \vec v'_3}$. We then repeat this process for each index $j \in [d/8]$, generating the sets $\Sigma_2(j)$, and define $\Sigma_2$ as $\Sigma_2 = \bigcup_{j=1}^{d/8} \Sigma_2(j)$. Note that every set $\Sigma_2(j)$, and thereby $\Sigma_2$, consists of linearly independent vectors, with $|\Sigma_2| = |B_2|/2$. Moreover, the vectors in $\Sigma_2$ and those in $\Sigma_1$ are pairwise linearly independent, since $\Sigma_1$ and $\Sigma_2$ contain disjoint sets of vectors within $\FF_2^d$.

We inductively implement the following steps for each level $\ell$ using the template provided by the construction of $\vec P_2$ and $\Sigma_2$: (i) we generate partitions $\vec {\bar P}_{\ell - 1}$ and then $\vec P_\ell$ from $\vec P_{\ell-1}$ in a random manner, (ii) we construct $\Sigma_\ell(j)$ by obtaining the linear combination of $2^{\ell - 1}$ consecutive “alive” basis vectors from an arbitrary order of $P_\ell(j)$ for each $j$, (iii) take union of vectors in $\Sigma_\ell(j)$ for each $j$ to form $\Sigma_\ell$. We refer the reader to Figure <ref> for a visualization of the construction of $B_\ell$, $\vec P_\ell$, and $\vec {\bar P_{\ell}}$ for the initial three levels. Also, Figure <ref> provides a visual representation of the construction of vectors in $\Sigma_\ell(j)$ for $\ell=3$ and $P_\ell(j) = \set{\vec v'_1, \vec v'_2,\dots, \vec v'_8}$.

[left] at (1,) $\textbf{P}_1$;

ıin 1,2,...,16
[fill=black, draw=black] (ı+0.3,) circle (1.3mm);
[fill=black, draw=black] (ı+0.7,) circle (1.3mm);
[fill=black, draw=black, opacity=0.2] (ı+0.3,) circle (1.3mm);
[fill=black, draw=black, opacity=0.2] (ı+0.7,) circle (1.3mm);

ıin 1,2,...,16

[fill=red, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);
[fill=blue, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);

[line width=0.35 mm, opacity=1]([ı],+-0.2) – ([ı],+0.2);
[line width=0.35 mm, opacity=1]([ı],+0.2) – ([ı],+-0.2);
[below, font=6pt8pt] at (,-0.32) $P_1(\i)$;

[left] at (1,) $\textbf{P}_2$;

ıin 1,2,...,16
[fill=black, draw=black] (ı+0.3,) circle (1.3mm);
[fill=black, draw=black] (ı+0.7,) circle (1.3mm);
[fill=gray, draw=gray, opacity=0.2] (ı+0.3,) circle (1.3mm);
[fill=gray, draw=gray, opacity=0.2] (ı+0.7,) circle (1.3mm);

ıin 1,2,3,4

[fill=red, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);
[fill=blue, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);

[line width=0.35 mm, opacity=1]([ı],+-0.2) – ([ı],+0.2);
[line width=0.35 mm, opacity=1]([ı],+0.2) – ([ı],+-0.2);
[below, font=6pt8pt] at (,-0.32) $P_2(\i)$;

[left] at (1,) $\textbf{P}_2$;

ıin 1,2,...,16
[fill=black, draw=black] (ı+0.3,) circle (1.3mm);
[fill=black, draw=black] (ı+0.7,) circle (1.3mm);
[fill=gray, draw=gray, opacity=0.2] (ı+0.3,) circle (1.3mm);
[fill=gray, draw=gray, opacity=0.2] (ı+0.7,) circle (1.3mm);

ıin 1

[fill=red, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);
[fill=blue, opacity=0.2] ([ı],+-0.2) rectangle    ([ı],+0.2);

[line width=0.15 mm, opacity=1](-0.25,-0.40) – (+0.25,-0.85);
[line width=0.15 mm, opacity=1](-0.25,-0.85) – (+0.25,-0.40);
[below, font=6pt8pt] at (,-0.30) $P_3(\i)$;

[left] at (1,) $\textbf{P}_3$;

A snapshot of the construction of $B_\ell$ and partition $\vec P_\ell$ for the initial $3$ levels. In this illustration, vertically aligned dots in groups of three represent the same basis vector. At any given level $\ell$, vectors indicated in solid colors denote $B_\ell$, the alive basis vectors of level $\ell$. Furthermore, the colored boxes at each level $\ell$, along with their encompassed alive basis vectors, constitute the parts $P_\ell(i)$ in the partition of $\vec P_\ell$. Random parts $\vec {\bar P_\ell}$ that survive through to the next level are marked without a cross.

After the construction of “raw” vectors $\Sigma_\ell$ for every $\ell \in [\kappa]$, we apply a random linear map $\Phi_R : \FF_2^{d} \rightarrow \FF_2^{2d}$ using a uniformly random matrix $R \in \FF_2^{2d \times d}$ to obtain $X=\Phi_R[\Sigma]$. By demonstrating that $\Sigma$ is composed of pairwise linearly independent vectors, as in Lemma <ref>, we infer that any two different vectors $\vec x_i$ and $\vec x_j$ are independent due to Lemma <ref>. We arrange the vectors in $\Sigma = \set{\sigma_1, \dots \sigma_\tau}$ and define a level map $\psi: [\tau] \rightarrow [\kappa]$, which maps an index of vector $\Sigma$ to one of the levels in $[\kappa]$. For any specified index $i \in [\tau]$, $\psi$ outputs $\ell \in [\kappa]$ if $\sigma_i \in \Sigma_\ell$. As vectors in $\Sigma$ are pairwise linearly independent, they are unique, therefore ensuring the map is well-defined. Here, we fix $\tau = \sum_{\ell=1}^\kappa |\Sigma_\ell |$. The exact value of $\kappa$ is determined in Theorem <ref> which is $O(\log d)$.

Finally, we employ random vectors $X$ and create a weight distribution over the matroid $\M^\tau$. For each vector $\vec v \in \FF_2^{2d}$, we independently sample a uniformly random permutation $\pi^{\vec v} \in \Pi[\tau]$. We define $w(\vec v^i)=2^\ell$ if $\vec x_{\pi^{\vec v}(i)} = \vec v$ and $\psi(\pi^{\vec v}(i))=\ell$. Lemma <ref> signifies that the events $\set{\vec x_i = \vec v}$ and $\set{\vec x_j = \vec u}$ are independent for any $\vec u, \vec v \in \FF_2^{2d}$ and $i\neq j \in [\tau]$. However, for any $\vec v^i\in E^\tau$, upon conditioning on the event ${w(\vec v^i) =2^\ell}$, the likelihood of any other $\vec u^i\in E^\tau$ taking the weight $2^\ell$ decreases, as we have a fixed number of vectors at level $\ell$. To overcome this obstacle, with small probability, we assign the weights of elements in $E^\tau$ using positively correlated and independent distributions. The precise distribution is shown in Procedure <ref>.

Construction of Pairwise Linearly Independent Collection of Vectors $\Sigma$

* Base level $\ell=1$:

* $B_1 = \{\vec e_1 , \dots, \vec e_d\}$ be the principal basis of $\Ft^{d}$.

* $\mathbf P_1 = \{P_1(i) : i \in [d/2]\}$ be a partition of $B_1$ where $P_1(i)=\{\vec e_{2i-1}, \vec e_{2i}\}$.

* Level $\ell>1$:

* Let $\bar{\mathbf{P}}_{\ell-1}$ be uniformly random half of $\mathbf{P}_{\ell-1}$ and define $\bar{\mathbf{P}}_{\ell-1}:=\{\bar{P}_{\ell-1}(i) : i\in[d/2^{2\ell-2}]\}$.

* Define $P_{\ell}(i) = \bar P_{\ell-1}(2i-1) \cup \bar P_{\ell-1}(2i)$ for each $i \in \frac{d}{2^{2\ell-1}}$ and set $\mathbf{P}_{\ell} = \{P_{\ell}(i) : i \in [d/2^{2\ell-1}]\}$.

* Define $B_\ell = \bigcup_{i=1}^{d/2^{2\ell-1}} P_\ell(i)$ which is called as the alive basis vectors of level $\ell$.

*  For any $\ell \in [\kappa]$ and $i \in [d/2^{2\ell-1}]$, define $\Sigma_\ell(i) \subseteq \Ft^d$ as collection of $|\Sigma_\ell(i)|=2^{\ell-1}$ linearly independent vectors which are linear combinations of $2^{\ell-1}$ vectors of $P_\ell(i)$.

* Let $\Sigma_\ell = \bigcup_{i=1}^{d/2^{2\ell -1}} \Sigma_\ell (i)$ and $\Sigma = \bigcup_{\ell=1}^\kappa \Sigma_\ell$.

* Given $\tau=\sum_{\ell=1}^\kappa \frac{d}{2^\ell}$,

let $\Sigma=\{\sigma_1, \dots \sigma_{\tau}\}$ be the collection of “raw” vectors together with a level map $\psi:[\tau] \rightarrow [\kappa]$ where $\psi(i)=\ell$ if $\sigma_i \in \Sigma_\ell$.

Before moving forward, we prove the correctness of Step <ref> of Procedure <ref>. The subsequent lemma demonstrates that the vectors $\Sigma_\ell(i)$ are linearly independent. The construction of $\Sigma_\ell(i)$ is visualized for $\ell=3$ and some $i \in [d/2^{5}]$ in Figure <ref>.

$P_3(j)=\{$          $\vec v'_1,$     $\vec v'_2,$     $\vec v'_3,$     $\vec v'_4,$     $\vec v'_5,$     $\vec v'_6,$     $\vec v'_7,$     $\vec v'_8$     $\}$

4*$\Sigma_3(j)=$ $\Bigg\{$     $\sigma_1=$     $\vec v'_1 + $   $\vec v'_2 + $   $\vec v'_3 + $   $\vec v'_4$            4*$\Bigg\}$

$\sigma_2=$        $\vec v'_2 + $   $\vec v'_3 + $   $\vec v'_4 +$   $\vec v'_5$

$\sigma_3=$           $\vec v'_3 + $   $\vec v'_4 +$   $\vec v'_5 +$   $\vec v'_6$

$\sigma_4=$              $\vec v'_4 +$   $\vec v'_5 +$   $\vec v'_6 +$   $\vec v'_7$

Vector generation.

For any $1 \leq \ell \leq 2d$, let $P \subseteq \Ftdd$ be a collection of $2^\ell$ linearly independent vectors. There exists a set of linearly independent vectors $S \subseteq \Ftdd$ of size $2^{\ell-1}$ such that each vector $\vec \sigma \in S$ is a linear combination of $2^{\ell-1}$ vectors from $P$.

Let $\vec v'_1, \dots \vec v'_{2^{\ell}}$ be an enumeration of $P$ and assume that $\vec v'_i=\vec v'_j$ if $i=j \mod 2^\ell$ to avoid notational clutter. We introduce $\sigma_t :=\sum_{i=t}^{t+2^{\ell-1}-1} \vec v'_i$ for all $t \in [2^{\ell-1}]$ and define $S=\{\sigma_t  : t \in [2^{\ell-1}]\}$.

We claim that $S$ forms a linearly independent set.  For contradiction, suppose there exist coefficients $\vec a \in \FF_2^{2^{\ell-1}}$ such that $\sum_{t=1}^{2^{\ell-1}} \vec a(t) \cdot \sigma_t = \vec 0$. Define $t^*$ as the minimum index with non-zero $a_t$ weight, i.e., $t^*=\min\set{t \in [2^{\ell-1}] : \vec a(t)=1}$. Observe that $\langle \vec v'_{t^*}, \sigma_{t^*} \rangle = ||\vec v'_{t^*}||^2$ and deduce that $\vec v'_{t^*}$ is not orthogonal to $\sigma_{t^*}$. However, $\vec v'_{t^*}$ is orthogonal to any $\sigma_j$ if $j>t^*$ since $\sigma_t = \sum_{i=t}^{t+2^{\ell-1}-1}$ and $|P|=2^{\ell}$. Therefore, $\sigma_{t^*} \notin \spn \set{\sigma_j: j > t^*}$ yields a contradiction.

Next, we observe that the vectors in $\Sigma$ are pairwise linearly independent with probability $1$.

$\Sigma$ consists of pairwise linearly independent vectors with probability $1$.

Any two vectors in $\Sigma$ are expressed as a linear combination of different sets of basis vectors, hence, $\Sigma$ is pairwise linearly independent.

Pairwise Independent Weight Assignments to Matroid $\mathcal M^\tau$
Dist - I :  $\mathcal D_1$

Initialize all weights $w(\vec v^j) = 0$ for all $\vec v\in \Ftdd$ and $j\in [\tau]$.

* Independently for each $\vec v \in \Ftdd$, consider uniformly random permutation $\pi^{\vec v} \sim \Pi[\tau]$.

Independently for each $\vec v\in \Ftdd$, define available copies $N^{\vec v}$ as follows

\begin{equation*}
N^{\vec v} = \begin{cases}
\text{Uniformly random  subset of $ [\tau]$ of size $\tau/2$} &\text{with prob. }\tau \cdot a(\tau)=\frac{\tau(\tau-2)}{(\tau-1)^2},\\
\emptyset & \text{ otherwise  }.
\end{cases}
\end{equation*}

* Let matrix $R\in \Ft^{2d\times d}$ to be a random matrix with entries $r_{ij} \sim \Ber \left( \frac 1 2  \right)$ independently.

* Define $X = \Phi_R[\Sigma]$ with vectors $\vec x_1 ,\dots \vec x_\tau$, where $\Sigma$ is constructed via Procedure <ref>.

* Given enumeration $\Sigma=\{\sigma_1, \dots \sigma_\tau\}$, define level map $\psi:[\tau]\rightarrow[\kappa]$ such that $\psi(i)=\ell$ if $\sigma_i \in \Sigma_\ell$.

* For all $t \in [\tau]$, if $\vec v=\vec x_t$ then $w\left(\vec v^{\pi^{\vec v}(t)}\right) = 2^\ell$ if and only if $\pi^{\vec v}(t) \in N^{\vec v}$ and $\psi(t)=\ell$.

Dist II($\ell$) : $\mathcal D_2(\ell)$

* Set $w(\vec v^j) = 2^\ell$ for all $v\in \Ftdd$ and $j\in [\tau]$.

Dist III : $\mathcal D_3$

* Set $w(\vec v^j) = 2^\ell$ with probability $\frac 1 {2^\ell}$ independently for all $\vec v^j \in E^\tau.$

Dist IV : $\mathcal D_4$

* Set $w(\vec v^j) = 0$ for all $v\in \Ftdd$ and $j\in [\tau]$.

Sample weights

\[
w \sim
\begin{cases}
\D_1 &\text{w.p. } p=1-\frac{d}{2^d},\\
\D_2(\ell) &\text{w.p. } p_\ell= \frac{p}{4} \cdot \frac{a^2(\tau) \cdot d}{2^{4d + \ell}},\\
\D_3 &\text{w.p. } q,\\
\D_4 &\text{w.p. } 1-p-\sum_{\ell \in [\kappa]} p_\ell -q.
\end{cases}
\]

In the following lemma, we will conclude that the weight assignment constructed in Procedure <ref> is pairwise independent. The proof of the lemma is rather technical and we delegate to Appendix <ref> to prevent the interruptions in the flow of the presentation.

There exists $0<q \leq \frac{3\cdot d}{2^{3d}}$ such that for any $\vec v^i $ and $\vec u^j$ $\in E^\tau$, random weights $w(\vec v^i)$ and $w(\vec u^j)$ are independently assigned by Procedure <ref>.

§.§ Upper Bounding the Approximation Ratio

Next, we consider an instance of prophet inequality problem for a matroid $\M^{\tau}$ with rank $2d$ and $E^{\tau} = \FF_2^{2\tau} \times [\tau]$, value distribution $\D$ as detailed in Procedure <ref>, and arrival order $\lambda$ in which elements with positive weights arrive in the increasing order of their weights followed by the elements with zero weight. Ties among elements arriving of the same weight are broken arbitrarily. We note that the arrival order $\lambda$ can only be orchestrated by an adversary who knows all the weight assignments upfront.

§.§.§ Lower bound for Prophet's Value

We first establish that a prophet, who is aware of all realizations within the probability space, can guarantee an expected reward of $\Omega(\kappa \cdot d)$.

Let $\M^\tau=(E^\tau, \I^\tau)$ be a matroid where $E=\Ftdd$ and $\I$ denotes all collections of linearly independent vectors in $E$ for $\kappa \geq 35$ and $d \geq 2^{5\kappa}$. For the pairwise independent weight distribution $\D \in \Delta_{pw}(\R_{\geq 0}^{E})$ described in Procedure <ref>,

$$\Ex[\text{reward of prophet}] = \Ex_{w \sim \D}[\rank_w(E^\tau)] \geq \frac{\kappa \cdot d}{12}.$$

We first primarily focus on instances where weight vector $w \sim \D_1$ and the random matrix $R$ possesses full row-rank.
Notice that these two events are independent where the first one happens with probability $p=1-\frac{d}{2^d}$ and the second does with probability $1-\frac{1}{2^m}$ due to Lemma <ref>. Moreover, Observation <ref> ensures that at most one copy of each vector $\vec v \in \Ftdd$ has a non-zero value. We now transition to examine subsequent computations conditioned on the event $\{w \sim \D_1 \land \rank(A)=d\}$.

Select an arbitrary vector $\vec v \in X$ from $X=\Phi_R[\Sigma]$, and assign $t_X(\vec v)$ to be the unique index satisfying $\vec x_{t_X(\vec v)} = \vec v$. Note that $t_X: X \rightarrow [\tau]$ serves as a random function that maps vectors of $X$ to their respective indices and it is well defined when the random matrix $R$ has full row rank. Furthermore, the only copy of $\vec v$ has a non-zero value with a probability of $\frac{\tau(\tau-2)}{2(\tau-1)^2}$ which occurs if $\pi^{\vec v}(t_X(\vec v)) \in N^{\vec v}$ ($N^{\vec v}$ is defined in Procedure <ref>). Let us denote $\EE(v)$ as the event when $\pi^{\vec v}(t_X(\vec v)) \in N^{\vec v}$.

Next, let $\Sigma'_\ell \subseteq \Sigma_\ell \setminus \spn(B_{\ell+1})$ be the subset of vectors in $\Sigma_\ell$ that do not belong to the span of $B_{\ell+1}$. In essence, the vector in $\Sigma'_\ell$ form a set of vectors orthogonal to $B_{\ell+1}$ and hence, orthogonal to $\Sigma_{\ell'}$ for any $\ell' > \ell$. Now, we define $X'_\ell = \Phi_R[\Sigma'_\ell]$ and a solution $S = \bigcup_{\ell=1}^\kappa \{\vec v^{\pi^{\vec v}(t_X(\vec v))} : \vec v \in X'_\ell\}$.

$S = \bigcup_{\ell=1}^\kappa \{\vec v^{\pi^{\vec v}(t_{X}(\vec v))} : \vec v \in X'_\ell\}$ is an independent set.

Notice that vectors in $X'_\ell$ orthogonal orthogonal to all vectors in $\Phi_R[B_{\ell'}]$ for any $\ell' > \ell$ since $\Phi_R$ is a linear function and $\Sigma'_\ell$ is orthogonal to $\Sigma_{\ell'}$ for any $\ell' > \ell$. Thus, $X'_\ell$ is orthogonal to any $X'_{\ell'}$ for any $\ell' > \ell$. Furthermore, each $X_\ell$ consists of linearly independent vectors when $R$ has full row-rank and $\Sigma_\ell$ is a collection of linearly independent vectors as verified in Lemma <ref>. Therefore, $S$ forms an independent set.

By using the fact that $S$ is an independent set of the matroid $\M^\tau$, we lower bound the expected reward of the prophet under conditioned on the event $\{w \sim \D_1 \land \rank(A)=d\}$.

\begin{align*}
\Ex_{w}[\rank_{w}(E^\tau)] &\geq \Ex_{w}[\rank_{w}(S)] \geq \sum_{\ell = 1}^\kappa 2^\ell \cdot \Ex \left[\sum_{\vec v \in X'_\ell} \mathbbm{1}_{\EE(\vec v)} \right]\\
&= \sum_{\ell = 1}^\kappa 2^\ell \cdot \sum_{\vec v \in \Ftdd} \Pr[\EE(\vec v) \mid \vec v \in X'_\ell] \cdot \Pr[\vec v \in X'_\ell] && (\text{Linearity of expectation})\\
&= \sum_{\ell = 1}^\kappa 2^\ell \cdot \frac{\tau(\tau-2)}{2(\tau-1)^2} \cdot \sum_{\vec v \in \Ftdd} \Pr[\vec v \in X'_\ell] \\
&= \sum_{\ell = 1}^\kappa 2^\ell \cdot \frac{\tau(\tau-2)}{2(\tau-1)^2} \cdot \frac{d}{2^{\ell+1}} && \left(|X'_\ell|=\frac{d}{2^{\ell+1}}\text{ w.p. }1\right)\\
&\geq \sum_{\ell=1}^\kappa \frac{d}{2} \cdot \frac{1}{3} && (\tau \geq 3) \\
& = \frac{\kappa \cdot d}{6}.
\end{align*}

Finally, we release the condition and compute the expected reward of the prophet as follows.

\begin{align*}
\Ex_{w}[\rank_{w}(E^\tau)] &\geq \Ex_{w}[\rank_{w}(E^\tau) \mid w \sim \D_1 \land \rank(A)=d] \cdot \Pr[w \sim \D_1 \land \rank(A)=d] \\
&\geq \frac{\kappa\cdot d}{6} \cdot \Pr[w \sim \D_1] \cdot \Pr[\rank(A)=d]\\
&\geq \frac{\kappa\cdot d}{6} \cdot \left(1-\frac{d}{2^d}\right) \cdot \left(1 - \frac{1}{2^d}\right)\\
&\geq \frac{\kappa \cdot d}{6} \cdot \frac{1}{2} \cdot \frac{1}{2} && (d>10)\\
&= \frac{\kappa \cdot d}{24}. \qedhere
\end{align*}

§.§.§ Upper Bound on the Perfomance of  any Algorithm

Next, we show that the expected reward of the gambler can not be larger than $O(d)$. This implies that no algorithm can obtain the competitive ratio of better than $\Omega\left(\frac{1}{\kappa}\right)=\Omega\left(\frac{1}{\log d}\right)$. Throughout the section, we exchangably use an algorithm as a gambler and vice versa.

Let $\M^\tau=(E^\tau, \I^\tau)$ be a matroid where $E=\Ftdd$ and $\I$ denotes all collections of linearly independent vectors in $E$ for $d>35$ and $\kappa = \frac 1 {10} \cdot \log d$. There is no $\omega(1/\log d)$-competitive strategy for gambler against prophet when weights are distributed according to Procedure <ref>.

Before we discuss the theorem's proof, we recall that with high probability, weight vector $w$ is sampled from $\D_1$, and the random matrix $R$ has full row rank.
Hence, any strategy that competes with the prophet must exhibit strong performance for this event, which we denote as $\EE_{\text{hard}}$. In the subsequent section, we first analyze the performance of an arbitrary algorithm/gambler conditioned on $\EE_{\text{hard}}$. Later, we will eliminate this constraint and complete the proof of the theorem.

In the previous section, we showed that for any level $\ell$, the prophet's selection (or offline optimal solution) entails the selection of vectors that are linear combinations of the vectors from $\Phi_R[B_\ell \setminus B_{\ell+1}]$ due to their orthogonality to vectors in $\Phi_R[B_{\ell+1}]$. The central argument we are making here is that if an algorithm is ignorant of the “active" basis $B_{\ell '}$ for $\ell ' > \ell$ and selects “large” number of vectors to compete against the prophet's utility, then it inadvertently spans a “large” fraction of the rank of $\Phi_R(\Sigma_{\ell'})$ at any higher level $\ell'>\ell$. Consequently, an algorithm can compete against the prophet's utility at only a constant number of levels before it spans nearly all vectors at a higher level, leading to the desired result.

Recall the first step of constructing $\Sigma_\ell$ described in Procedure <ref>: we partition the “alive” basis vectors at level $\ell$ (denoted as $B_\ell$) into  $d/2^{2\ell-1}$ subsets denoted as $\vec P_\ell=\{P_{\ell}(i) : i \in d/2^{2\ell-1}\}$. Given that gambler's selection is $S$, we say that gambler has decision profile $\rho$, if he or she selects $\rho_\ell(i)$ elements among labeled copies of vectors in $X_\ell(i)=\Phi_R[\Sigma_\ell(i)]$, that is, $\rho_\ell(i) = |S \cap X_\ell(i) \times [\tau]|$. Note that $\rho$ is random due to the randomness of both $R$ and the selection $S$ made by the gambler. We define $\rho_\ell = \sum_{i} \rho_\ell(i)$, and obtain

$$ \Ex[\rank_{w}(S) \mid \EE_{\text{hard}}] = \sum_{\ell=0}^{k-1} 2^\ell \cdot \rho_\ell.$$

Remember that at any level $\ell$, $P_\ell(i)$ is formed by merging two parts from level $\ell-1$, say $P_{\ell -1}(j),P_{\ell -1}(j') \in \vec P_{\ell - 1}$ for some distinct $j$ and $j'$. Therefore,  iteratively applying the same argument, we observe that $P_\ell(i)$ comprises $2^{\ell - \ell'}$ many “parts” from each lower level $\ell' \leq \ell$.
Now, we let $\gamma_\ell(i)$ as the
$$\gamma_\ell(i) = \Bigg | \bigg \{ \bigcup_{\ell' \leq \ell} \text{ }  \bigcup_{P_{\ell ' }(i')  \subseteq    P_\ell(i)} \Phi_R[\Sigma_{\ell'}(i')] \bigg \} \bigcap S \Bigg |  = \Bigg | \bigg \{ \bigcup_{\ell' \leq \ell}  \text{ }  \bigcup_{P_{\ell ' }(i')  \subseteq    P_\ell(i)}  X_{\ell'}(i') \bigg \}  \bigcap S\Bigg  | ,$$

which is essentially the number of vectors selected by an algorithm that is in the span of the vectors $\Phi_R[P_\ell(i)]$.

In addition, we can recursively define $\gamma_\ell(i)$ as follows: if $P_\ell(i) = P_{\ell-1}(j) \cup P_{\ell-1}(j')$ for some distinct $j$ and $j'$ at level $\ell-1$, then $\gamma_{\ell}(i) = \rho_{\ell}(i)+ \gamma_{\ell-1}(j) + \gamma_{\ell-1}(j')$. We define $\gamma_\ell = \sum_{j} \gamma_{\ell}(j)$, which is essentially a number of vectors selected by an algorithm upto level $\ell$ contained in the $\mathbf{Span}(\Phi_R[B_\ell])$. We observe that,
$$ \gamma_\ell = \sum_{i}  \left( \rho(i) + \sum_{P_\ell(i)} \sum_{P_{\ell - 1}(i')\subseteq P_\ell(i)} \gamma_{\ell - 1}(i') \right), $$

where unifmormly random half of the parts from level $\ell -1$ are contained in $P_{\ell}(i)$ for some $i\in [d/2^\ell]$.

On the other hand, in accordance with the weight assignment procedure outlined in Procedure <ref>, the weighted rank of any level is bounded by $O(d)$ when  $\EE_{\text{hard}}$ happens. Consequently, any algorithm aiming for a constant competitive ratio must choose at least $\frac{1}{\kappa} \cdot |B_\ell|$ vectors from level $\ell$ for some $\ell \in [\kappa]$, which implies $\rho_\ell \geq \frac{1}{\kappa} \cdot |B_\ell| = \frac{1}{\kappa} \cdot \frac{d}{2^{\ell-1}}$ for some $\ell \in [\kappa]$. Applying concentration inequalities and using the fact that $d > 2^{5\kappa}$, we can argue that whenever $\gamma_\ell > \frac{1}{2\kappa} \cdot |B_\ell|$ is sufficiently large, $\gamma_{\ell+1}$ is roughly $\rho_{\ell+1} + \frac{\gamma_\ell}{2}$ with high probability. Intuitively, this observation says that once the span of selected vectors generates a suitably large subspace within the span of $\Phi_R[B_\ell]$, about half of these vectors also fall within the span of $\Phi_R[B_{\ell +1}]$. In the next lemma, we formalize the above intuition.

For any $1 < \ell \leq \kappa$, if $\gamma_{\ell-1} \geq \frac{1}{\kappa} \cdot |B_{\ell-1}|$,

$$ \Pr\left[ \gamma_\ell \geq \rho_\ell + \left(1-\frac{1}{\kappa^2}\right)  \cdot \frac{\gamma_{\ell-1}}{2}\right] \geq 1-\frac{1}{\kappa^2}. $$

In the following lemma, we demonstrate that once an algorithm selects sufficiently large number of vectors up to level $\ell$, i.e. $\gamma_\ell$ is large, it inadvertently spans a “large” portion of the $\spn(\Phi_R[\Sigma_{\ell'}])$ for any $\ell' >\ell$ via the vectors selected up to level $\ell$. In a way, this lemma illustrates the disadvantage where any algorithm faces due to its lack of information about the alive basis $B_{\ell'}$ and $\Phi_R(\Sigma_{\ell'})$ at higher levels $\ell' > \ell$.

Let $t \geq 0$ be the minimum index with $\rho_t \geq \frac{2}{\kappa} \cdot |B_t|$ then with probability $1-\frac{1}{\kappa}$, for all $\ell \geq t$

$$ \gamma_\ell \geq \rho_\ell + \left(1-\frac{1}{\kappa^2}\right) \cdot \frac{\gamma_{\ell-1}}{2} \qquad\text{and}\qquad \gamma_\ell \geq \left(1-\frac{1}{\kappa}\right)\cdot \sum_{i=t}^{\ell-1} \frac{1}{2^{\ell-i}} \cdot \rho_i. $$

The two prior lemmas set the stage for the upcoming essential lemma that limits the performance of any algorithm, given that the event $\EE_{\text{hard}}$ takes place. Intuitively, any algorithm that aspires to be within a constant factor of the prophet's performance must select at least $\frac 1 \kappa$ fraction of vectors (actually, much larger than $\frac 1 \kappa$) from $\Omega(\kappa)$ levels. Nevertheless, the selection of $\Omega\left(\frac 1 \kappa \right)$ fraction of vectors from any level eventually leads to spanning a large portion of vectors/rank at higher levels. This phenomenon prevents any algorithm from effectively competing against the prophet with high probability.

For any collection of elements $S$ selected by the gambler, we have

$$\Ex[\rank_{w}(S) \mid \EE_{\text{hard}}] \leq 7 \cdot d.$$

Before we proceed with proofs of these lemmas, we utilize Lemma <ref> to prove the main result of this section.

First of all, Lemma <ref> and $\Pr[w \sim \D_1] = 1-\frac{d}{2^{2d}}$ implies that

$$ \Pr[\EE_{\text{hard}}] = \Pr[w \sim \D_1 \wedge \rank(R)=d] \geq 1 - \frac{d}{2^d} - \frac{1}{2^d} \geq 1 - \frac{2}{k}$$

since $d>\kappa\geq35$.
This yields us

\begin{align*}
\Ex[\rank_{w}(S)] &\leq \Pr[\EE_{\text{hard}}] \cdot \Ex[\rank_{w}(S) \mid \EE_{\text{hard}}]  + k \cdot d \cdot \Pr[\EE_{\text{hard}} \text{ does not hold}]\\
&\leq \left(1-\frac{2}{k}\right) \cdot \Ex[\rank_w(S) \mid \EE_{\text{hard}}] + k \cdot d \cdot \frac{2}{k} \\
&\leq \Ex[\rank_{w}(S) \mid \EE_{\text{hard}}] + 2\cdot d\\
&\leq 9 \cdot d && (\text{Lemma~\ref{lem:conditional-upper-bound}}).
\end{align*}

On the other hand, Theorem <ref> shows that the prophet's expected reward is at least $\Omega(k \cdot d)$. Therefore, no algorithm can achieve a competitive ratio better than $O(1/\kappa) = O(1/\log d)$ for the Prophet Inequality Problem when values are distributed according to Procedure <ref> and elements are presented in the order of $\lambda$.

The rest of this section is dedicated to providing proof for the lemmas stated above. Before we proceed with proofs, we state a useful fact about the concentration of the sum of random variables which are sampled from a finite population without replacement.

Let $\mathcal{X}=\left(x_1, \ldots, x_N\right)$ be a finite population of $N$ points and $X_1, \ldots, X_n$ be a random sample drawn without replacement from $\mathcal{X}$. Let

a=\min _{1 \leq i \leq N} x_i \quad \text { and } \quad b=\max _{1 \leq i \leq N} x_i .

Then, for all $\varepsilon>0$,

\mathbb{P}\left(\sum_{i=1}^n X_i-n \cdot \mu \geq n \cdot \varepsilon\right) \leq \exp \left(-\frac{2 n \varepsilon^2}{(b-a)^2}\right),

where $\mu=\frac{1}{N} \sum_{i=1}^N x_i$ is the mean of $\mathcal{X}$.

For any fixed $\ell \in [\kappa]$, recall that $\gamma_\ell(i)$ is the count of vectors selected up to level $\ell$ which are lying in the span of $\Phi_R[P_\ell(i)]$ for each $i \in [d/2^{2\ell-1}]$. Define $\Gamma_\ell = \{\gamma_\ell(i) : P_\ell(i) \in P_\ell\}$. For each $P_\ell(i) \in P_\ell$ let $y_i = \mathbbm{1}_{P_{\ell}(i) \in \bar P_{\ell}}$ denote whether the part $P_\ell(i)$ survives to next level or not. Observe that $\gamma_{\ell+1}-\rho_{\ell+1}$ is the sum of random half of $\Gamma_\ell$. Then,

$$ \gamma_{\ell+1} = \rho_{\ell+1} + \sum_{i=1}^{d/2^{2\ell-1}} y_i \cdot \gamma_\ell(i).$$

Since each $\gamma_\ell(i) \leq 2^{\ell-1}$, by invoking Proposition <ref> with $\epsilon=\frac{1}{\kappa^2}$ and ensuring that $d \geq 2^{5\kappa}$ and $k \geq 35$, we deduce

$$ \gamma_{\ell+1} - \rho_{\ell + 1} \geq \left(1-\frac{1}{\kappa^2}\right) \cdot \frac{\gamma_{\ell-1}}{2} $$

with probability at least $1-\frac{1}{\kappa^2}$. The inequality holds since

$$ d \geq \kappa^4 \cdot 2^{4\kappa} \cdot \log \kappa^2 \implies \exp\left( -\frac{2 d/2^{2\ell-1}}{2^{2\ell-2} \cdot \kappa^4} \right) \leq \frac{1}{\kappa^2}$$

when $d\geq 2^{5\kappa}$ and $\kappa \geq 35$.

We start by defining an event $\EE_\ell$ for each level $\ell \geq t$ each of which holds if $\gamma_{\ell+1} \geq \rho_{\ell+1} + \left(1-\frac{1}{\kappa^2}\right) \cdot \frac{\gamma_\ell}{2}$.
By using the chain decomposition of conditional probability we show that

\begin{align*}
\Pr\left[\bigwedge_{\ell=t}^{\kappa-1} \EE_\ell \right] &=
\prod_{\ell=t}^{\kappa-1} \Pr[\EE_\ell \mid \EE_t \dots \EE_{\ell-1}]\\
% &= \prod_{\ell=t}^{\kappa-1} \Pr[\EE_\ell \mid \EE_t \dots \EE_{\ell-1}]\\
&= \prod_{\ell=t}^{\kappa-1} \Pr\left[\gamma_{\ell+1} \geq \rho_{\ell+1} + \left(1-\frac{1}{\kappa^2}\right) \cdot \frac{\gamma_{\ell}}{2} \mid \EE_t, \dots \EE_{\ell-1}\right]\\
&\geq \prod_{\ell=t+1}^\kappa 1-\frac{1}{\kappa^2} && (\text{Lemma~\ref{lem:error-transition}})\\
&\geq 1-\frac{1}{\kappa}.
\end{align*}

Moreover, with probability $1-\frac{1}{\kappa}$, we have

\begin{align*}
\gamma_\ell
&\geq \rho_\ell + \left(1-\frac{1}{\kappa^2}\right) \cdot \frac{\gamma_{\ell-1}}{2}\\
&\geq \rho_\ell + \cdot \sum_{i=t}^{\ell-1} \left(1-\frac{1}{\kappa^2}\right)^{\ell-i} \frac{1}{2^{\ell-i}} \cdot \rho_i && (\text{Iteratively expanding the summand})\\
&\geq \rho_\ell + \left(1-\frac{1}{\kappa}\right) \cdot \sum_{i=t}^{\ell-1} \frac{\rho_i}{2^{\ell-i}} && \left(\left(1-\frac{1}{\kappa^2}\right)^{\ell-i} \geq \left(1-\frac{1}{\kappa^2}\right)^\kappa \geq \left(1-\frac{1}{\kappa}\right)\right).
\end{align*}

Recall that $\EE_{\text{hard}}$ is the event when $w$ sampled according to $\D_1$ and random matrix $R$ has full row-rank.
Next, we condition on that $\EE_{\text{hard}}$ occurs and compute an upper-bound for $\Ex[\rank_{w}(S) \mid \EE_{\text{hard}}]$.

First of all, observe that for any level $\ell$, $\gamma_\ell \leq \rank(\Phi_R[B_\ell]) = \rank(B_\ell) = d/2^{\ell-1}$. For the simplicity of notation, we define normalized values $\overline{\rho}_\ell = \rho_\ell \cdot \frac{2^{\ell-1}}{d}$ and $\overline{\gamma}_\ell = \gamma_\ell \cdot \frac{2^{\ell-1}}{d}$. Notice that for any $ 1 \leq \ell \leq k$, we have $0 \leq \overline{\rho}_\ell, \overline{\gamma}_\ell \leq 1$.

Let $t$ be the minimum index such that $\rho_t \geq \frac{2}{\kappa} \cdot |B_t|$. If there is no such index, then let $t = \kappa$.
By Lemma <ref>, with probability $\left(1-\frac{1}{\kappa}\right)$, we have

$$\gamma_\ell \geq \rho_\ell + \left(1-\frac{1}{\kappa}\right) \cdot \sum_{j=t}^{\ell-1} \frac{\rho_j}{2^{\ell-j}} \qquad \text{ or equivalently }\qquad \overline{\gamma}_\ell \geq \overline{\rho}_\ell + \left(1-\frac{1}{\kappa}\right) \cdot \sum_{j=t}^{\ell-1} \overline{\rho}_{j}$$

for all $\ell \geq t$.
Therefore, with probability $1-1/\kappa$, $\overline{\rho}_\ell \leq 1 - \left(1-\frac{1}{\kappa}\right) \cdot \sum_{j=t}^{\ell-1} \overline{\rho}_{j}$ for all $\ell \geq t$.

\begin{align*}
\Ex[\rank_w(S) \mid \EE_{\text{hard}}]
&= \sum_{\ell=1}^{k} 2^{\ell-1} \cdot \rho_\ell \\
& \leq \sum_{\ell=1}^{t-1} 2^{\ell-1} \cdot \frac{2}{\kappa} \cdot \frac{d}{2^{\ell-1}} +
\left(1-\frac{1}{\kappa}\right) \cdot \sum_{\ell=t}^{\kappa-1} 2^{\ell-1} \cdot \rho_\ell +
\frac{1}{\kappa} \cdot \sum_{\ell=t}^{\kappa-1} 2^{\ell-1} \cdot \frac{d}{2^{\ell-1}}\\
& \leq 3 \cdot d + \sum_{\ell=t}^{\kappa-1} 2^{\ell-1} \cdot \rho_\ell \\
& \leq 3 \cdot d + \sum_{\ell=t}^{\kappa-1} 2^{\ell-1} \cdot \overline{\rho}_\ell \cdot \frac{d}{2^{\ell-1}} && \left(\overline{\rho_\ell}=\rho_\ell \cdot \frac{2^{\ell-1}}{d}\right)\\
& \leq 3 \cdot d + \sum_{\ell=t}^{\kappa-1} d \cdot \overline{\rho}_\ell\\
&\leq 3\cdot d + d \cdot \sum_{\ell=t}^{\kappa-1} \min\left\{\overline{\rho}_\ell, 1-\left(1-\frac{1}{\kappa}\right)\cdot\sum_{i=t}^{\ell-1} \overline{\rho}_i\right\}.
\end{align*}

Let $t'$ be the minimum index such that $\sum_{\ell=t}^{t'} \overline{\rho}_\ell \geq 1-1/\kappa$. If there is no such index then set $t'=\kappa-1$. Then,

\begin{align*}
\Ex[\rank_w(S) \mid \EE_{\text{hard}}]
&\leq 3\cdot d + d \cdot \sum_{\ell=t}^{\kappa-1} \min\left\{\overline{\rho}_\ell, 1-\left(1-\frac{1}{\kappa}\right)\cdot\sum_{i=t}^{\ell-1} \overline{\rho}_i\right\}\\
&\leq 3\cdot d + d \cdot \left(
\sum_{\ell=t}^{t'} \overline{\rho_\ell} + \sum_{\ell=t'+1}^{\kappa-1} \left( 1-\left(1-\frac{1}{\kappa}\right)\cdot\sum_{i=t}^{\ell-1} \overline{\rho}_i \right)
\right)\\
&\leq 3\cdot d + 2 \cdot d + d \cdot \sum_{\ell=t'+1}^{\kappa-1} \left( 1-\left(1-\frac{1}{\kappa}\right)\cdot\sum_{i=t}^{\ell-1} \overline{\rho}_i \right)\\
&\leq 5\cdot d + d \cdot \sum_{\ell=t'+1}^{\kappa-1}  \left( 1-\left(1-\frac{1}{\kappa} \right)\cdot\left(1-\frac{1}{k} \right) \right)\\
&\leq 5 \cdot d + d\cdot \sum_{\ell=t'+1}^{\kappa-1} \frac{2}{\kappa}\\
&\leq 7 \cdot d.
\end{align*}

Above, the third inequality holds because $\sum_{\ell=t}^{t'} \overline{\rho}_\ell  = \sum_{\ell=t}^{t' - 1} \overline{\rho}_\ell  + \overline{\rho}_{t'} \leq 2 - 1/k \leq 2$ since $t'$ is the smallest index such that $\sum_{\ell=t}^{t'} \overline{\rho}_\ell \geq 1-1/k$. The fourth inequality holds because $\sum_{i = t}^{t'} \overline{\rho}_i \geq 1 - 1/k$ if $t' < \kappa - 1$. Otherwise, the second summation vanishes as $t' +1  > \kappa - 1$.

§ $ \OMEGA \LEFT( \FRAC{1}{\LOG \RANK} \RIGHT)$ PAIRWISE INDEPENDENT MATROID PROPHET INEQUALITY

In this section, we give an algorithm for a pairwise independent prophet inequality problem that matches the upper bound obtained in Section <ref>. We first present useful local-lemma type result for pairwise independent events from [18].

Let $\EE, \F$ be two events on the same probability space. We represent the occurrences of at least one of $\EE , \F$ and both $\EE, \F$ events simultaneously by $\EE \vee \F$ and $\EE \wedge \F$ respectively.

Given the set of pairwise independent events $\{\EE_1,\dots ,\EE_k\}$ on the same probability space, the following lemma from [18] lower bounds the probability of the occurrence of at least one of the random events $\{\EE_1,\dots ,\EE_k\}$ which we present in the following lemma.

Let $\{\mathcal E_i\}_{i=1}^k$ be a collection of pairwise independent events and $\D$ be a pairwise independent distribution over these events. Then

\begin{equation*}
\Pr\left[\bigvee_{i=1}^k \mathcal E_i\right] \geq \frac{\sum_{i=1}^k \Pr[\mathcal E_i]}{1+\sum_{i=1}^k \Pr[\mathcal E_i]}.
\end{equation*}

The following theorem is the main result of the section.

For any given matroid $\M(E, \I)$, there exists an $O\left(\frac{1}{\log\rank}\right)$-approximation algorithm for pairwise independent prophet inequality problem where $\rank$ is a short-hand notation for $\rank(\M)$.

Our algorithm defines a strategy for the gambler by dividing elements into weight buckets. Given a matroid $\M=(E,\I)$ and pairwise independent weight distribution $\w\sim \D$, we denote $\opt =\E_\D \left[\rank_{\w}(\M) \right]$. Next, we set $k = \ceil{4 \log \rank}$ and define $k+2$ buckets $B_0, B_1, \dots B_k$ and $B_\infty$ as follows:

\begin{align*}
B_0 = \left[0, \frac{\opt}{\rank^2}\right),
B_1 = \left[\frac{\opt}{\rank^2}, \frac{2 \opt}{\rank^2} \right), \dots , B_k = \left[ \cdot \frac{2^{k-1}  \opt}{\rank^2},  \frac{2^k  \opt}{\rank^2}\right),
B_{\infty} = \left[ \frac{2^k \opt}{\rank^2}, \infty \right).
\end{align*}

Given any draw of the weights $w \sim \mathcal D$, we partition elements into sets $E_0, E_1, \dots E_k$ and $E_\infty$ as follows. We define $E_i = \{e \in E: w(e) \in B_i\}$ for any $i \in \{0, \dots k, \infty\}$ as elements whose weight lies in bucket $B_i$. Here, note that the sets $E_i$ for $i \in \{0,\dots, k, \infty \}$ are random. We define the expected optimal reward from bucket $B_i$ for any $i\in \{0,1, \dots, k, \infty \}$ as follows,

$$ \opt(B_i) = \Ex\left[ \max_{S \subseteq E_i, S \in \I} \rank_{w}(S) \right] \text{ for any } i \in \{0, \dots k, \infty\}. $$

We can upper-bound the expected reward of the prophet by the total expected optimal rewards from each bucket.

\begin{equation}\label{eq:bound_opt}
\opt \leq \sum_{i=0}^{k} \opt(B_i) + \opt(B_\infty).
\end{equation}

We start by showing that the contribution of bucket $B_0$ can be ignored. More formally,

Given matroid $\M=(E,\I)$ and pairwise independent distribution $w\sim \D$,

\begin{equation*}
\opt(B_0) \leq \frac{\opt}{\rank}.
\end{equation*}

We can bound,

\begin{equation*}
\opt(B_0) = \E \left[ \max_{S \subseteq E_0, S\in \I} \rank_{\w}(S) \right] \leq \E \left[|S| \cdot \frac{\opt}{\rank^2}\right] \leq \frac{\opt}{\rank}.
\end{equation*}

The first inequality holds because $\w(e) \leq \frac{\opt}{\rank^2}$ for any element $e \in E_0$ with probability $1$. The latter follows from the fact that $|S| \leq \rank$ with probability $1$.

Clearly, this claim implies that $\sum_{i=1}^k \opt(B_i) + \opt(B_\infty) \geq \left(1-\frac{1}{\rank}\right) \cdot \opt$.
Next, we propose an algorithm which guarantees at least $\Omega\left(\frac{1}{\log \rank}\right)$ fraction of $\opt$. The algorithm first determines the optimal bucket $B^*$ which guarantees the maximum expected reward as follows:

\begin{equation*}
B^* = \argmax_{B_i \in \{B_1,\dots, B_k, B_\infty\}} \opt (B_i).
\end{equation*}

Later, it greedily picks all elements belonging to bucket $B^*$. We formally state this algorithm as follows.

Pairwise Independent Matroid Prophet Inequality Algorithm.

Input: Matroid $\mathcal M = (E,\I)$ and pairwise independent joint weight distribution $\w\sim \D$.

Output: $S$.

Compute $\opt$ and buckets $B_0,\dots, B_{k+1}$
Let $B^* = \argmax_{B_i \in \{B_1,\dots, B_{k}, B_\infty\}} \opt (B_i)$
Set $S\gets \emptyset$
Visit elements $e \in E$ in given order
$\w(e)\in B^*$ and $S\cup \{e\} \in \I$
Update $S\gets S\cup \{e\}$

In the rest of the section, we aim to show that Algorithm <ref> guarantees the desired approximation ratio. We first observe that

\begin{align}\label{eq:bound opt bucket}
\opt(B^*) &\geq \frac{1}{4 \log \rank} \cdot \left(\sum_{i=1}^k \opt(B_i) + B_\infty \right) \geq \frac{1}{4\log \rank}\cdot \left(1 - \frac 1 \rank \right)\cdot  \opt \notag \\
&\geq  \frac{1}{8\log \rank} \cdot  \opt
\end{align}

Let $S$ be the output of the algorithm for any given problem instance. Next, we aim to show that $\Ex[\w(S)] \geq c \cdot \opt(B^*)$ for some universal constant $c$. We consider the following two cases separately: (i) $B^* \in \{B_1, \dots B_k\}$ and (ii) $B^*=B_\infty$ and start by showing the first.

Let $S$ be the output of Algorithm <ref>. If  $B^* \in \{B_1, \dots B_k\}$ then

$$\Ex[\w(S) ] \geq \frac{1}{2} \cdot \Ex[\rank_{\w}(B^*) ].$$

Let $B_i=B^*$ for some $i \in [k]$ and $\ell = 2^{i-1} \cdot \frac{\opt}{\rank^2}$. Then, observe that $\ell \leq \w(e) \leq 2 \cdot \ell$ for all $e \in B_i$ and $\rank_{\w}(E_i) \leq 2\cdot \ell \cdot \rank(E_i)$. Since the greedy algorithm guarantees an independent set $S$ such that $|S|=\rank(E^*)$ with probability $1$, we have

$$ \rank_{\w}(S) \geq \ell \cdot |S| = \ell \cdot \rank(E_i) \geq \frac{1}{2} \cdot \rank_{\w}(E_i).$$

which completes the proof.

Next, we analyze the case when $B^* = B_\infty$. We start by observing that the probability of having bucket $B_\infty$ nonempty, i.e. $E_\infty \neq \emptyset$ is very small.

Given matroid $\M=(E,\I)$ and pairwise independent distribution $\w \sim \D$,

\begin{equation*}
\Pr\left[ E_\infty \neq \emptyset \right] \leq \frac 1 {\rank^2}.
\end{equation*}

Assume for a contradiction $\Pr\left[ E_\infty \neq \emptyset \right] > \frac{1}{\rank^2}$, then

\begin{align*}
\Ex_{w\sim \D}[\rank_{\w}(\M)]
&\geq \Ex_{w \sim \D}\left[\max_{e \in E} \w(e)\right]\\
&\geq 2^k \cdot \frac{\opt}{\rank^2} \cdot \Pr[E_\infty \neq \emptyset] \\
&\geq \opt \cdot \rank^2 \cdot \Pr[E_\infty \neq \emptyset] && (k \geq 4 \cdot \log \rank) \\
&> \frac{\opt \cdot \rank^2}{\rank^2} && (\text{contradiction assumption})\\
&= \opt
\end{align*}

yields a contradiction.

Before we complete the proof of the second scenario, when $B^*=B_\infty$, we state a fact.

Given matroid $\M=(E,\I)$, pairwise independent distribution $\w\sim \D$ and $e' \in E$,

\begin{equation*}
\sum_{e \in E \setminus \{e'\}} \Pr[\w(e) \in B_{\infty} \mid \w(e') \in B_{\infty}] \leq \frac{\frac{1}{\rank^2}}{1 - \frac{1}{\rank^2}}.
\end{equation*}

First, we note that the set of events $\{w(e) \in B_\infty\}_{e\in E}$ are pairwise independent. Hence, Lemma <ref> implies that,

\[
\Pr[E_\infty \neq \emptyset] = \Pr\left[ \bigvee_{e \in E} \{\w(e) \in B_\infty\}\right] \geq \frac{\sum_{e \in E} \Pr[\w(e) \in B_\infty]}{1 + \sum_{e \in E} \Pr[\w(e) \in B_\infty]}.
\]

Observe that this is equivalent to

\[
\sum_{e \in E} \Pr[\w(e) \in B_\infty] \leq \frac{\Pr[E_\infty \neq \emptyset]}{1 - \Pr[E_\infty \neq \emptyset]} \leq \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}}.
\]

Above, the last inequality follows due to Observation <ref>. Since distribution $\D$ is pairwise independent,

\[
\sum_{e \in E \setminus \{e'\}} \Pr[\w(e) \in B_{\infty} \mid \w(e') \in B_{\infty}] = \sum_{e \in E \setminus \{e'\}} \Pr[\w(e) \in B_\infty] \leq \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}}
\]

completes the proof.

The following lemma establishes the result of this section.

Let $S$ be the output of Algorithm <ref>,

$$\Ex[\w(S) \mid B^* = B_\infty] \geq \frac{2}{3} \cdot \Ex[\rank_{\w}(B^*) \mid B^* = B_\infty].$$

First we can bound the $\opt(B_{\infty})$ as follows:

\begin{align*}
\opt(B_{\infty}) = \E \left[ \max_{I \subseteq E_{\infty}, I\in \I} \rank_{\w}(I) \right]\leq \sum_{e\in E} \E \left[  \w(e) \mid \w(e) \in B_\infty \right] \cdot \Pr[ \w(e) \in B_\infty].
\end{align*}

We note that our algorithm always selects the first element in $B_\infty$ presented by the adversary. Now, we define an event $\mathcal E_e(x) := \{ \w(e) = x \land \bigcap_{e'\neq e\in E} \{ \w(e') \notin B_{\infty}\}\}$ for any $x\geq \rank^2 \cdot \opt$. We can bound the probability of the event $\mathcal E_e$ as follows:

\begin{align*}
\Pr[\mathcal E_e(x)]
&= \Pr\left[\w(e) = x \land \bigwedge_{e'\in E\setminus \{e\}} \{ \w(e')\notin B_{\infty}\} \right]\\
& = \Pr\left[  \bigwedge_{e'\in E\setminus \{e\}} \{ \w(e')\notin B_{\infty}\} \mid  \w(e) = x\right] \cdot \Pr[ \w(e) = x]\\
&=\left(1 - \Pr\left[E_\infty \setminus \{e\} \neq \emptyset \mid \w(e) = x\right] \right) \cdot \Pr[\w(e) = x]\\
&\geq \left( 1 - \sum_{e' \in E \setminus \{e\}} \Pr[e'\notin E_{\infty} \mid \w(e) = x] \right) \cdot \Pr[ \w(e) = x] && (\text{Union bound})\\
&\geq \left( 1 - \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}} \right) \cdot \Pr[\w(e) = x]. && (\text{Proposition~\ref{prop:sum_of_bad_events}})
\end{align*}

As events $\{\mathcal E_e(x)\}_{e\in E}$ are set of disjoint events, we can lower bound the performance of the algorithm as

\begin{align*}
\Ex[\w(S) \mid B^*=B_\infty] &\geq \sum_{e\in E} \int_{x\geq \rank^2 \cdot \opt} x \cdot d \Pr[\mathcal E_e(x)]\\
&\geq\left( 1 - \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}} \right) \cdot  \sum_{e\in E} \int_{x\geq \rank^2 \cdot \opt} x \cdot d \Pr[\w(e) = x] \\
& = \left( 1 - \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}} \right) \cdot  \sum_{e\in E} \E[\w(e) \mid \w(e)\geq \rank^2 \cdot \opt] \cdot \Pr[\w(e) \geq \rank^2 \cdot \opt]\\
&\geq \left( 1 - \frac{\frac{1}{\rank^2}}{1-\frac{1}{\rank^2}} \right) \cdot \opt(B_{\infty}) \\
&\geq \frac{2}{3} \cdot \opt(B_\infty).
\end{align*}

Here, the last inequality follows when $\rank (\M) \geq 2$.

We are now ready to prove the main theorem of the section:

Let $S$ be the output of Algorithm <ref>.  Combining Lemmas <ref> <ref>

\begin{equation*}
\mathbb E [w(S)] \geq \frac{1}{2} \mathbb E [\opt (B^*)] \geq \frac{1}{16 \cdot \log \rank} \cdot \opt.
\end{equation*}

Above the last inequality holds due to Equation <ref>. This concludes the proof.

We note that our algorithm is $\Omega(1/\log \rank)$-approximate against even an “almighty" adversary from [28] who knows all the weight assignments or randomness of the algorithm in advance. This holds because our algorithm is deterministic and it picks a set with the total expected weight of at least $ \frac{1}{2} \E[\rank_{\w} (B^*)]$ for any arrival order.

§ PARTITION PROPERTY AND STOCHASTIC SELECTION PROBLEMS

A matroid $\M = (E,\I)$ is called a simple parition matroid if a partition of $E = \bigcup_{i=1}^d P_i$ exists such that $I\in \I$ if and only if $|I\cap P_i| \leq 1$ for all $i\in [d]$. We recall the following partition property of matroids defined in [8].

Consider a matroid $\M = (E , \I)$. We say that $\M$ satisfies an $\alpha$-partition property for some $\alpha \in (0,1]$ if it is possible to determine a function $f$ that generates a random simple partition matroid $\M' = (E', \I')$ on the set of elements $E' \subseteq E$ such that for any non-negative weight vector $\w$:

* $ \rank_{\w} (\M) \geq \E_{\M' \sim f(\M)} \left[\rank_{\w}(\M') \right] \geq \alpha \cdot \rank_{\w}(\M)$,

* $\I' \subseteq \I$ for any $\M' \in \operatorname{supp}(f(\M))$.

Several families of matroids have been identified to satisfy this property for a global constant or a “small" $\alpha$ [8, 45]. Table <ref> summarizes our results. We regard the function $f$ as a black box function that takes a matroid $\M$ as an input and returns a (random) simple partition matroid $\M'$ which guarantees the optimal possible $\alpha$-partition property for $\M$.

Constraint    CRS     Prophet Inequality     Note and Reference for Partition Property

Partition Matroid    $\frac 1 4 $-balanced    $\frac 1 3$-competetive    Theorem <ref> <ref>

Graphic Matroid     $\frac 1 8$-balanced     $ \frac{1}{6} $ -competetive    Theorem <ref> <ref> and [8]

Co-Graphic Matroid     $\frac 1 {12}$-balanced     $\frac{1}{9} $-competitive     Theorem <ref> <ref> and [45]

Laminar Matroid    $\frac{1}{12\sqrt 3}$-balanced    $\frac{1}{9\sqrt 3}$-competitive    Theorem <ref> <ref> and [34]

Low Density Matroid    $\frac{1}{8\gamma }$-balanced    $\frac{1}{6\gamma }$-competetive   Theorem <ref> <ref> and [45],  $\gamma = \max_{S\subseteq E} \frac{|S|}{\rank(S)}$

Column $k$ Sparse Matroid    $\frac{1}{8k}$-balanced   $\frac{1}{6k}$-competetive   Theorem <ref> <ref> and [45]

Summary of our results for matroids that satisfies $\alpha$-partition property.

§.§ Partition Property and Pairwise Independent Matroid Prophet Inequalities

We reference a theorem from the work that investigates the prophet inequality problem with pairwise independent distributions [18]. This theorem illustrates the existence of a constant approximate pairwise independent prophet inequality algorithm for a one-uniform matroid.

Given a one-uniform matroid over elements $E$ and a pairwise independent value distribution $\D \in \pwvalue$, there exists a $(1/3)$-approximate prophet inequality algorithm.

Broadening this result, we devise an algorithm that admits a $\frac{\alpha}{3}$-approximate pairwise independent prophet inequality when the matroid upholds an $\alpha$-partition property. The algorithm operates in a straightforward manner: when given a matroid $\M$ that satisfies the $\alpha$-partition property, it initially constructs a simple partition matroid $\M'$ and proceeds to execute a $\frac{1}{3}$-approximate algorithm for each partition, treating them akin to a one-uniform matroid.

Partition Based Pairwise Independent Matroid Prophet Inequality Algorithm.

Input: Matroid $\mathcal M = (E,\I)$, pairwise independent value distribution $\D$, $\frac{1}{3}$-approximate pairwise independent prophet inequality algorithm $\A$ for one-uniform matroid

Determine $\M' \leftarrow f(\M)$, which is a simple partition matroid with partitions $P_1, \dots P_r$, where $r:=\rank(\M')$.
For each part $P_i$, let $S_i$ be the output of $\A$ when executed on a one-uniform matroid over $P_i$.

Output: Set $S \leftarrow \bigcup_{i=1}^r S_i$

Suppose $\M=(E, \I)$ is a matroid which holds an $\alpha$-partition property for a certain $\alpha \in (0,1]$, and $\D\in \Delta_{\text{pw}}(\mathbb R_{\geq 0}^{E})$ is a pairwise independent value distribution. Algorithm <ref> yields $\frac{\alpha}{3}$-approximate pairwise independent prophet inequality.

Let's denote $\A_i$ as the run of algorithm $\A$ with inputs $P_i$ and value distribution $\{\w(e) : e\in P_i\}$. Given the random simple partition matroid $\M'$, we can observe that

\begin{align}\label{eq:using_one_uniform_alg}
\Ex_{\w \sim \D}[\w(S) \mid \M']
&= \sum_{i=1}^r \Ex_{\A_i, \w \sim \D}[\w(S_i) \mid \M'] && (\text{Linearity of expectation}) \notag\\
&\geq \sum_{i=1}^r \Ex_{\A_i, \w \sim \D}\left[\frac{1}{3} \cdot \rank_{\w}^{\M'}(P_i) \mid \M' \right] && (\text{Theorem~\ref{thm:1-uniform-prophet}})\\
&= \frac{1}{3} \cdot \Ex_{\w \sim \D}\left[\sum_{i=1}^r  \rank_{\w}^{\M'}(P_i) \mid \M' \right] && (\text{Linearity of expectation})\notag\\
&= \frac{1}{3} \cdot \Ex_{\w \sim \D}\left[\rank_{\w}(\M') \mid \M' \right]. &&(\text{$\M'$ is a partition matroid})\notag
\end{align}

If we drop the condition and use Fubini's theorem , we get that

$$ \Ex_{\M'}\left[ \frac{1}{3} \cdot \Ex_{\w \sim \D}\left[\rank_{\w}(\M') \mid \M' \right] \right]\\
= \frac{1}{3} \Ex_{\w \sim \D} \left[ \Ex_{\M'} \left[ \rank_{\w}(\M') \mid \vec  w \right] \right]\\ $$

given that $\rank_{\w}(\M')$ is a non-negative random variable with a finite expectation. Above the equality holds because $\M'$ is independent of the weight assignments $w\sim \mathcal D$. Thus, we have

\begin{align*}
\Ex[w(S)] &= \Ex_{\M'}\left[ \Ex_{\w \sim \D}[\w(S) \mid \M'] \right]\\
&\geq \frac{1}{3} \Ex_{\w \sim \D} \left[ \Ex_{\M'} \left[ \rank_{\w}(\M') \mid \w \right] \right]\\
&\geq \frac{1}{3} \Ex_{\w \sim \D} \left[\alpha \cdot \rank_{\w}(\M)\right] && (\text{$\alpha$-partition property})\\
&= \frac{\alpha}{3} \cdot \Ex_{\w \sim \D}\left[ \rank_{\w}(\M) \right]. \qedhere
\end{align*}

In Theorem <ref>, our approximation guarantees hold against even an “almighty" adversary from [28] who knows all the weight assignments or randomness of the algorithm in advance. This holds because the pairwise independent prophet inequality algorithm for one-uniform matroid from [18]  is deterministic. Therefore, once we conditioned on $\M'$ Equation <ref> holds against an almighty adversary.

§.§ Partition Property and Pairwise Independent CRS for Matroids

In this section, we demonstrate a $\frac{\alpha}{4}$-balanced Contention Resolution Scheme (CRS) for matroids that exhibit an $\alpha$-partition property. Initially, we present a straightforward $\frac{1}{4}$-balanced pairwise independent CRS for a one-uniform matroid.

For a one-uniform matroid over elements $E$, $\vec x\in [0,1]^{|E|}$ with $\sum_{e\in E} \vec x(e) \leq 1$, and a pairwise independent distribution $\D \in \pwset(\vec x)$, there exists a $\frac{1}{4}$-balanced CRS for $\D$.

Due to Lemma <ref>, it is enough to show that for any weight vector $\w \in \mathbb R^{|E|}_{\geq 0}$, $\Ex_{A \sim \D}[\rank_{\w}(A)] \geq \frac 1 4 \cdot \sum_{e\in E} \w(e)\cdot \vec x(e)$. For the set $A\sim \D$, we construct $A'$ by independently choosing each element from $A$ with probability $\frac{1}{2}$. Noting that $\Pr[e\in A'] = \frac{\vec x(e)}{2}$, we can formulate the following bound:

\begin{align*}
\Ex_{A \sim \D}[\rank_{\w}(A)] &\geq \Ex_{A'}[\rank_{\w}(A')]\\
&\geq \sum_{e\in E} \w(e) \cdot \Pr_{A'}[A' \cap E = \set{e}]\\
&= \sum_{e\in E}\w(e) \cdot  \Pr_{A'}[e \in A'] \cdot \Pr[(A' \cap E) \setminus \set{e} = \emptyset \mid e \in A']\\
&\geq \sum_{e\in E}\w(e) \cdot \Pr_{A'}[e\in A'] \cdot \left( 1 - \sum_{e'\in E\setminus \{e\}}\Pr_{A'}[ e'\in A'\mid e\in A']\right) && \text{(Union Bound)}\\
&=\frac 1 2 \cdot \sum_{e\in E}\w(e) \cdot \vec x(e) \cdot \left( 1 - \frac 1 2 \cdot \sum_{e'\in E\setminus \{e\}}\vec x(e')\right) &&\text{(Pairwise Independence)}\\
&\geq \frac 1 4 \cdot \sum_{e\in E}\w(e) \cdot \vec x(e)  && \qedhere
\end{align*}

Next, similar to the prophet inequalities, we reduce CRS for matroids with $\alpha$ -partition property to one uniform matroid. The following is the main theorem of this section:

Let $\M=(E, \I)$ be a matroid that satisfies $\alpha$-partition property for some $\alpha \in (0,1]$, $\vec x \in P_\I$ and $\D\in \Delta_{\text{pw}}(2^E)(\vec x)$. Then $\D$ admits an $\frac{\alpha}{4}$-balanced CRS.

Before we prove the theorem, we prove a crucial lemma that for any matroid and $\M$ satisfying $\alpha$-partition property and $\vec x \in \P_\I$, there exists $\vec x'\in \P_{\I'}$ that approximates $\vec x$ in expectation, where $\M' = (E,\I')$ is a (random) simple partition matroid that approximates the (expected) rank of $\M$ within $\alpha$ factor.

Let $\M=(E, \I)$ be a matroid that satisfies $\alpha$-partition property associated with the black box function $f$, $\vec x\in \mathcal P_\I$ and weight vector $\w \in \mathbb R^E_{\geq 0}$ and $\M' = (E, \I')$ be a random partition matroid produced by $f(\M)$. Then there exists (random) $\vec x'$ such that:

*  $\vec x' \in \P_{\I'}$ with probability $1$,

*  $\vec x'(e) \leq \vec x(e)$ for all $e \in E$ with probability $1$,

*  $\sum_{e\in E} \w(e) \cdot  \Ex[\vec x'(e)] \geq \alpha \cdot \sum_{e\in E} \w(e) \cdot  \vec x(e)$.

Due to Caratheodory's theorem, we can express $\vec x = \sum_{j=1}^{k} c_j \cdot \mathbbm{1}_{I_j} $, where $\sum_{j=1}^{k} c_j=1$ and  $I_j \in \I$ for every $j \in [k]$, where $k = |E| +1$. Next, let us define $\w^j = \w \cdot \mathbbm{1}_{I_j}$, and notice that the $\alpha$-partition property implies

\begin{equation}\label{eq:apply-alpha-partition}
\Ex[\rank_{\w^j}(\M')] \geq \alpha \cdot \Ex[\rank_{\w^j}(\M)] = \alpha \cdot \sum_{e \in I_j} \w(e)
\end{equation}

where the equality follows because $I_j \in \I$. For all $\M' =(E',\I') \in \operatorname{supp}(f(\M)) $, we define $\vec x'$ such that for any $e \in E$:

\begin{equation}\label{eq:desired-x}
\vec x'(e) = \sum_{j=1}^k c_j \cdot \mathbbm{1} \left[e \in \argmax_{S \in \I'} \w^j(S)\right],
\end{equation}

Notice that $\vec x' \in \P_{\I'}$ since $\sum_j^k c_j=1$ and $\vec x$ is convex combination of independent sets of $\M'$. Also, observe that $\vec x'(e) \leq \vec x(e)$ as $\sum_{j=1}^k c_j \cdot \mathbbm{1}[e \in I_j] = \vec x(e)$ due to Caratheodory's theorem. In addition,

\begin{align*}
\sum_{e \in E} \Ex[\vec x'(e)] \cdot \w(e)
&= \sum_{e \in E} \sum_{j=1}^k c_j \cdot \Pr[e \in \argmax_{S \in \I'} \w^j(S)] \cdot \w(e) && \eqref{eq:desired-x}\\
&= \sum_{j=1}^k c_j \cdot \sum_{e \in E} \Pr[e \in \argmax_{S \in \I'} \w^j(S)] \cdot \w(e)\\
&= \sum_{j=1}^k c_j \cdot \Ex[\rank_{\w^j}(\M')] && (\text{Definition of }\rank_{\w^j}(\cdot))\\
&\geq \sum_{j=1}^k c_j \cdot \alpha \sum_{e \in I_j} \w(e) && \eqref{eq:apply-alpha-partition}\\
&= \alpha \cdot \sum_{e \in E} \w(e) \cdot \vec x(e) && (\text{Caratheodory's decomp.}) \qedhere
\end{align*}

We now move forward to provide a proof for the main theorem of this section.

Let $\w \in \R_{+}^E$ be an arbitrary weight assignment of elements, and $\vec x \in \P_\I$ be an arbitrary vector of marginal probabilities. Let  $\vec x'$ be the random vector that is generated as per Lemma <ref>. For any realization $\M'$, let us define $N_{\M'} \subseteq E$ as a randomly chosen set of elements, where each element $e \in E$ is included with a probability of $\frac{\vec x'(e)}{\vec x(e)}$, independently. We observe that the set $A\cap N_{\M'}$ is sampled from a distribution belonging to $\Delta_{\text{pw}}(2^E)(\vec x')$ since $\vec x'(e) \leq \vec x(e)$ due to Lemma <ref>.  We have:

\begin{align*}
\Ex[\rank^\M_{\w}(A)] &\geq \Ex[\rank_{\w}^{\M'}(A)] && (\I' \subseteq \I)\\
&\geq \Ex[\rank_{\w}^{\M'}(A \cap N_{\M'})] && (\text{monotonicity of } \rank_{\w}(\cdot))\\
&=\Ex\left[ \Ex[\rank_{\w}^{\M'}(Q \cap N_{\M'}) \mid \M'] \right]\\
&\geq \Ex\left[ \frac{1}{4} \cdot \sum_{e \in E} \vec \w(e) \cdot \vec x(e) \cdot \Pr[e \in N_{\M'} \mid \M'] \right] && (\text{Lemma~\ref{lem:1-uniform-crs}})\\
&= \Ex\left[\frac{1}{4} \cdot \sum_{e \in E} \w(e) \cdot \vec x'(e)\right] && (\text{Construction of }N_{\M'})\\
&=\sum_{e\in E} \frac{1}{4} \cdot \w(e) \Ex[\vec x'(e)] && (\text{Linearity of Exp.})\\
&\geq \frac{\alpha}{4} \cdot \sum_{e \in E} \w(e) \cdot \vec x(e) && \text{Lemma~\ref{lem:partition-marginal-decomposition}}\\
&= \frac{\alpha}{4} \cdot \Ex_{A \sim \D}[\w(A)]
\end{align*}

Concluding from Lemma <ref>, we find that the distribution on the set of active elements, if pairwise independent, admits an $\frac{\alpha}{4}$-balanced CRS when the matroid satisfies the $\alpha$-partition property.

Theorem <ref> combined with impossibility result for CRS from Theorem <ref>, we conclude that the class of linear matroids does not satisfy $\alpha$-partition property for $\alpha \leq O(d)$. In addition, in the analysis of Thoerem <ref>, by setting $c = \log_2 d$ and $q=2$, we conclude that the full binary matroid does not satisfy $O(\log d / d)$-partition property.

§ OPEN QUESTIONS

In this work, we explore the pairwise independent prophet inequality in scenarios where the arrival order is determined by an adversary who is aware of all the weight assignments beforehand. We question if a comparable upper limit on the approximation ratio is valid for models with the worst-case arrival or random arrival models. In these models, the sequence of elements is either chosen by an adversary who does not have access to the weight assignments in advance, or is selected uniformly randomly.

Due to the relation between matroid secretary conjecture and prophet secretary problem from [24],  we note that demonstrating an upper limit for the random arrival order would refute the matroid secretary conjecture. Here, we would like to point our that our lower-bound construction for the matroid prophet inequality appears highly nontrivial even if considered in the random-order setting. Therefore, algorithmic attacks against our construction in the random-order setting could serve as a stepping stone towards the matroid secretary conjecture.

[1]
Dorna Abdolazimi, Anna R. Karlin, Nathan Klein, and Shayan Oveis Gharan.
Matroid Partition Property and the Secretary Problem.
In Yael Tauman Kalai, editor, 14th Innovations in Theoretical
Computer Science Conference (ITCS 2023), volume 251 of Leibniz
International Proceedings in Informatics (LIPIcs), pages 2:1–2:9, Dagstuhl,
Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

[2]
Marek Adamczyk, Fabrizio Grandoni, and Joydeep Mukherjee.
Improved approximation algorithms for stochastic matching.
In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras,
Greece, September 14-16, 2015, Proceedings, pages 1–12. Springer, 2015.

[3]
Marek Adamczyk and Michał Włodarczyk.
Random order contention resolution schemes.
In 2018 IEEE 59th Annual Symposium on Foundations of Computer
Science (FOCS), pages 790–801. IEEE, 2018.

[4]
Noga Alon.
A simple algorithm for edge-coloring bipartite multigraphs.
Information Processing Letters (IPL), 85(6):301–302, 2003.

[5]
Noga Alon, László Babai, and Alon Itai.
A fast and simple randomized parallel algorithm for the maximal
independent set problem.
Journal of Algorithms, 7(4):567–583, 1986.

[6]
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta.
Simple construction of almost k-wise independent random variables.
Proceedings [1990] 31st Annual Symposium on Foundations of
Computer Science, pages 544–553 vol.2, 1990.

[7]
Georgios Askalidis and Edward C. Malthouse.
The value of online customer reviews.
In Proceedings of the 10th ACM Conference on Recommender
Systems, RecSys '16, page 155–158, New York, NY, USA, 2016. Association
for Computing Machinery.

[8]
Moshe Babaioff, Michael Dinitz, Anupam Gupta, Nicole Immorlica, and Kunal
Secretary problems: weights and discounts.
In Proceedings of the twentieth annual ACM-SIAM Symposium on
Discrete Algorithms, pages 1245–1254. SIAM, 2009.

[9]
Moshe Babaioff, Michal Feldman, Yannai A. Gonczarowski, Brendan Lucier, and
Inbal Talgam-Cohen.
Escaping cannibalization? correlation-robust pricing for a
unit-demand buyer.
In Proceedings of the 21st ACM Conference on Economics and
Computation, EC '20, page 191, New York, NY, USA, 2020. Association for
Computing Machinery.

[10]
Maryam Bahrani, Hedyeh Beyhaghi, Sahil Singla, and S. Matthew Weinberg.
Formal barriers to simple algorithms for the matroid secretary
In Michal Feldman, Hu Fu, and Inbal Talgam-Cohen, editors, Web
and Internet Economics, pages 280–298, Cham, 2022. Springer International

[11]
Rémi Bardenet and Odalric-Ambrym Maillard.
Concentration inequalities for sampling without replacement.
Bernoulli, 21(3), aug 2015.

[12]
MohammadHossein Bateni, Sina Dehghani, MohammadTaghi Hajiaghayi, and Saeed
Revenue maximization for selling multiple correlated items.
In Algorithms-ESA 2015: 23rd Annual European Symposium, Patras,
Greece, September 14-16, 2015, Proceedings, pages 95–105. Springer, 2015.

[13]
Alok Baveja, Amit Chavan, Andrei Nikiforov, Aravind Srinivasan, and Pan Xu.
Improved bounds in stochastic matching and optimization.
Algorithmica, 80:3225–3252, 2018.

[14]
Curtis Bechtel and Shaddin Dughmi.
Delegated stochastic probing.
arXiv preprint arXiv:2010.14718, 2020.

[15]
Curtis Bechtel, Shaddin Dughmi, and Neel Patel.
Delegated pandora's box.
In Proceedings of the 23rd ACM Conference on Economics and
Computation, pages 666–693, 2022.

[16]
Xiaohui Bei, Nick Gravin, Pinyan Lu, and Zhihao Gavin Tang.
Correlation-robust analysis of single item auction.
In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on
Discrete Algorithms, SODA '19, page 193–208, USA, 2019. Society for
Industrial and Applied Mathematics.

[17]
Yang Cai and Argyris Oikonomou.
On simple mechanisms for dependent items.
In Proceedings of the 22nd ACM Conference on Economics and
Computation, EC '21, page 242–262, New York, NY, USA, 2021. Association
for Computing Machinery.

[18]
Ioannis Caragiannis, Nick Gravin, Pinyan Lu, and Zihe Wang.
Relaxing the independence assumption in sequential posted pricing,
prophet inequality, and random bipartite matching.
In Michal Feldman, Hu Fu, and Inbal Talgam-Cohen, editors, Web
and Internet Economics, pages 131–148, Cham, 2022. Springer International

[19]
J. Lawrence Carter and Mark N. Wegman.
Universal classes of hash functions.
Journal of Computer and System Sciences, 18(2):143–154, 1979.

[20]
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan.
Multi-parameter mechanism design and sequential posted pricing.
In Proceedings of the 42nd Annual ACM Symposium on Theory of
Computing (STOC), pages 311–320, 2010.

[21]
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen.
Multi-budgeted matchings and matroid intersection via dependent
In Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1080–1097, 2011.

[22]
Michael Dinitz.
Recent advances on the matroid secretary problem.
ACM SIGACT News, 44(2):126–142, 2013.

[23]
Shaddin Dughmi.
The outer limits of contention resolution on matroids and connections
to the secretary problem.
In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th
International Colloquium on Automata, Languages, and Programming, ICALP
2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference),
volume 168 of LIPIcs, pages 42:1–42:18. Schloss Dagstuhl -
Leibniz-Zentrum für Informatik, 2020.

[24]
Shaddin Dughmi.
Matroid secretary is equivalent to contention resolution.
arXiv preprint arXiv:2103.04205, 2021.

[25]
Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel.
On sparsification of stochastic packing problems.
arXiv preprint arXiv:2211.07829, 2022.

[26]
Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.
Prophet inequalities made easy: Stochastic optimization by pricing
nonstochastic inputs.
SIAM Journal on Computing (SICOMP), 49(3):540–582, 2020.

[27]
Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang.
Online stochastic max-weight matching: prophet inequality for vertex
and edge arrival models.
In Proceedings of the 21st ACM Conference on Economics and
Computation (EC), pages 769–787, 2020.

[28]
Moran Feldman, Ola Svensson, and Rico Zenklusen.
Online contention resolution schemes.
In Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete
Algorithms (SODA), pages 1014–1033, 2016.

[29]
Nick Gravin and Pinyan Lu.
Separation in Correlation-Robust Monopolist Problem with
Budget, pages 2069–2080.

[30]
Nikolai Gravin and Hongao Wang.
Prophet inequality for bipartite matching: Merits of being simple and
non adaptive.
In Proceedings of the 20th ACM Conference on Economics and
Computation (EC), pages 93–109, 2019.

[31]
Jason D Hartline et al.
Bayesian mechanism design.
Foundations and Trends® in Theoretical Computer
Science, 8(3):143–263, 2013.

[32]
Theodore P Hill and Robert P Kertz.
A survey of prophet inequalities in optimal stopping theory.
Contemporary Mathematics, 125:191–207, 1992.

[33]
Nicole Immorlica, Sahil Singla, and Bo Waggoner.
Prophet inequalities with linear correlations and augmentations.
In Proceedings of the 21st ACM Conference on Economics and
Computation, pages 159–185, 2020.

[34]
Patrick Jaillet, José A Soto, and Rico Zenklusen.
Advances on matroid secretary problems: Free order model and laminar
In International Conference on Integer Programming and
Combinatorial Optimization, pages 254–265. Springer, 2013.

[35]
Howard Karloff and Yishay Mansour.
On construction of k-wise independent random variables.
In Proceedings of the Twenty-Sixth Annual ACM Symposium on
Theory of Computing, STOC '94, page 564–573, New York, NY, USA, 1994.
Association for Computing Machinery.

[36]
Jon Kleinberg and Robert Kleinberg.
Delegated search approximates efficient search.
In Proceedings of the 2018 ACM Conference on Economics and
Computation, pages 287–302, 2018.

[37]
Robert Kleinberg and S Matthew Weinberg.
Matroid prophet inequalities and applications to multi-dimensional
mechanism design.
Games and Economic Behavior, 113:97–115, 2019.

[38]
Michael Luby, Avi Wigderson, et al.
Pairwise independence and derandomization.
Foundations and Trends® in Theoretical Computer
Science, 1(4):237–301, 2006.

[39]
J. Naor and M. Naor.
Small-bias probability spaces: Efficient constructions and
In Proceedings of the Twenty-Second Annual ACM Symposium on
Theory of Computing, STOC '90, page 213–223, New York, NY, USA, 1990.
Association for Computing Machinery.

[40]
Pranav Nuti and Jan Vondrák.
Towards an optimal contention resolution scheme for matchings.
arXiv preprint arXiv:2211.03599, 2022.

[41]
James G Oxley.
Matroid theory, volume 3.
Oxford University Press, USA, 2006.

[42]
Do-Hyung Park, Jumin Lee, and Ingoo Han.
The effect of on-line consumer reviews on consumer purchasing
intention: The moderating role of involvement.
International Journal of Electronic Commerce, 11(4):125–148,

[43]
Tristan Pollner, Mohammad Roghani, Amin Saberi, and David Wajc.
Improved online contention resolution for matchings and applications
to the gig economy.
In Proceedings of the 23rd ACM Conference on Economics and
Computation, pages 321–322, 2022.

[44]
Yosef Rinott and Ester Samuel-Cahn.
Optimal stopping values and prophet inequalities for some dependent
random variables.
Lecture Notes-Monograph Series, 22:343–358, 1992.

[45]
José A Soto.
Matroid secretary problem in the random-assignment model.
SIAM Journal on Computing, 42(1):178–211, 2013.

[46]
Aravind Srinivasan, David Wajc, et al.
Online dependent rounding schemes.
arXiv preprint arXiv:2301.08680, 2023.

[47]
Salil P. Vadhan.
Foundations and Trends® in Theoretical Computer
Science, 7(1–3):1–336, 2012.

[48]
Jan Vondrák, Chandra Chekuri, and Rico Zenklusen.
Submodular function maximization via the multilinear relaxation and
contention resolution schemes.
In Proceedings of the forty-third annual ACM symposium on Theory
of computing, pages 783–792, 2011.

[49]
Mark N. Wegman and J. Lawrence Carter.
New hash functions and their use in authentication and set equality.
Journal of Computer and System Sciences, 22(3):265–279, 1981.

[50]
Dominic JA Welsh.
Matroid theory.
Courier Corporation, 2010.

§ MISSING PROOFS FROM SECTION <REF>

Recall that we define $a(d)=\frac{d \cdot (d-2)}{(d-1)^2}$.

Observe that for any $\vec v\in \FF_q^{2d}$ and $i \in [d]$

\begin{equation}
\begin{aligned}
\Pr[\vec v^i \in A] &= \Pr[\vec v^i \in A \mid A \sim \D_1] \cdot \Pr[A \sim \D_1] + \Pr[\vec v^i \in A \mid A \sim \D_2] \cdot \Pr[A \sim \D_2]\\
&= \Pr[\vec v^i \in A \mid A \sim \D_1] \cdot p + \delta\\