More results about Ruzsa distance #
More facts about Ruzsa distance and related inequalities, for use in the m-torsion version of PFR.
Main definitions #
multiDist: An analogue ofrdistfor the m-torsion version of PFR.condMultiDist: A conditional analogue ofmultiDist
Main results #
kvm_ineq_I,kvm_ineq_II,kvm_ineq_III: Variants of the Kaimanovich-Versik-Madiman inequalitymultiDist_chainRule: A chain rule formultiDistcor_multiDist_chainRule: The corollary of the chain rule needed for the m-torsion version of PFRent_of_sub_smul_le: ControllingH[X - aY]in terms ofH[X]andd[X ; Y].
Let X, Ybe random variables. For any function f, g on the range of X, we have
I[f(X) : Y] ≤ I[X : Y].
Let X, Y be random variables. For any functions f, g on the ranges of X, Y respectively,
we have I[f ∘ X : g ∘ Y ; μ] ≤ I[X : Y ; μ].
Let X, Y, Z. For any functions f, g on the ranges of X, Y respectively,
we have I[f ∘ X : g ∘ Y | Z ; μ] ≤ I[X : Y | Z ; μ].
If X, Y are G-valued, then d[X;-Y] ≤ 3 d[X;Y].
If n ≥ 0 and X, Y₁, ..., Yₙ are jointly independent G-valued random variables,
then H[Y i₀ + ∑ i in s, Y i; μ] - H[Y i₀; μ] ≤ ∑ i in s, (H[Y i₀ + Y i; μ] - H[Y i₀; μ]).
The spelling here is tentative.
Feel free to modify it to make the proof easier, or the application easier.
If n ≥ 1 and X, Y₁, ..., Yₙ$ are jointly independent G-valued random variables,
then d[Y i₀; μ # ∑ i in s, Y i; μ] ≤ 2 * ∑ i in s, d[Y i₀; μ # Y i; μ].
If n ≥ 1 and X, Y₁, ..., Yₙ$ are jointly independent G-valued random variables,
then d[Y i₀, ∑ i, Y i] ≤ d[Y i₀, Y i₁] + 2⁻¹ * (H[∑ i, Y i] - H[Y i₁]).
Let X₁, ..., Xₘ and Y₁, ..., Yₗ be tuples of jointly independent random variables (so the
X's and Y's are also independent of each other), and let f: {1,..., l} → {1,... ,m} be a
function, then H[∑ j, Y j] ≤ H[∑ i, X i] + ∑ j, H[Y j - X f(j)] - H[X_{f(j)}].
Let X,Y,X' be independent G-valued random variables, with X' a copy of X,
and let a be an integer. Then H[X - (a+1)Y] ≤ H[X - aY] + H[X - Y - X'] - H[X]
Let X,Y,X' be independent G-valued random variables, with X' a copy of X,
and let a be an integer. Then H[X - (a-1)Y] ≤ H[X - aY] + H[X - Y - X'] - H[X]
Let X,Y be independent G-valued random variables, and let a be an integer. Then
H[X - aY] - H[X] ≤ 4 |a| d[X ; Y].
Let X_[m] = (X₁, ..., Xₘ) be a non-empty finite tuple of G-valued random variables X_i.
Then we define D[X_[m]] = H[∑ i, X_i'] - 1/m*∑ i, H[X_i'], where the X_i' are independent copies
of the X_i.
Equations
- D[X ; hΩ] = H[fun (x : Fin m → G) => ∑ i : Fin m, x i ; MeasureTheory.Measure.pi fun (i : Fin m) => MeasureTheory.Measure.map (X i) MeasureTheory.volume] - (↑m)⁻¹ * ∑ i : Fin m, H[X i]
Instances For
Pretty printer defined by notation3 command.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Let X_[m] = (X₁, ..., Xₘ) be a non-empty finite tuple of G-valued random variables X_i.
Then we define D[X_[m]] = H[∑ i, X_i'] - 1/m*∑ i, H[X_i'], where the X_i' are independent copies
of the X_i.
Equations
- One or more equations did not get rendered due to their size.
Instances For
If X_i has the same distribution as Y_i for each i, then D[X_[m]] = D[Y_[m]].
If X_i are independent, then D[X_{[m]}] = H[∑_{i=1}^m X_i] - \frac{1}{m} \sum_{i=1}^m H[X_i].
We have D[X_[m]] ≥ 0.
If φ : {1, ..., m} → {1, ...,m} is a bijection, then D[X_[m]] = D[(X_φ(1), ..., X_φ(m))]
Let m ≥ 2, and let X_[m] be a tuple of G-valued random variables. Then
∑ (1 ≤ j, k ≤ m, j ≠ k), d[X_j; -X_k] ≤ m(m-1) D[X_[m]].
Let m ≥ 2, and let X_[m] be a tuple of G-valued random variables. Then
∑ j, d[X_j;X_j] ≤ 2 m D[X_[m]].
Let I be an indexing set of size m ≥ 2, and let X_[m] be a tuple of G-valued random
variables. If the X_i all have the same distribution, then D[X_[m]] ≤ m d[X_i;X_i] for any
1 ≤ i ≤ m.
Let m ≥ 2, and let X_[m] be a tuple of G-valued random
variables. Let W := ∑ X_i. Then d[W;-W] ≤ 2 D[X_i].
If D[X_[m]]=0, then for each i ∈ I there is a finite subgroup H_i ≤ G such that
d[X_i; U_{H_i}] = 0.
If X_[m] = (X_1, ..., X_m) and Y_[m] = (Y_1, ..., Y_m) are tuples of random variables,
with the X_i being G-valued (but the Y_i need not be), then we define
D[X_[m] | Y_[m]] = ∑_{(y_i)_{1 \leq i \leq m}} (∏ i, p_{Y_i}(y_i)) D[(X_i | Y_i = y_i)_{i=1}^m]
where each y_i ranges over the support of p_{Y_i} for 1 ≤ i ≤ m.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Let X_[m] = (X₁, ..., Xₘ) be a non-empty finite tuple of G-valued random variables X_i.
Then we define D[X_[m]] = H[∑ i, X_i'] - 1/m*∑ i, H[X_i'], where the X_i' are independent copies
of the X_i.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Pretty printer defined by notation3 command.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Conditional multidistance is unchanged if we apply an injection to the conditioned variables
Conditional multidistance against a constant is just multidistance
Conditional multidistance is nonnegative.
If (X_i, Y_i), 1 ≤ i ≤ m are independent, then
D[X_[m] | Y_[m]] = H[∑ i, X_i | (Y_1, ..., Y_m)] - 1/m * ∑ i, H[X_i | Y_i]
If (X_i, Y_i), 1 ≤ i ≤ m are independent, then D[X_[m] | Y_[m]] = ∑_{(y_i)_{1 ≤ i ≤ m}} P(Y_i=y_i ∀ i) D[(X_i | Y_i=y_i ∀ i)_{i=1}^m]
Let π : G → H be a homomorphism of abelian groups and let X_[m] be a tuple of jointly
independent G-valued random variables. Then D[X_[m]] is equal to
D[X_[m] | π(X_[m])] + D[π(X_[m])] + I[∑ i, X_i : π(X_[m]) ; | ; π(∑ i, X_i)]
where π(X_[m]) := (π(X_1), ..., π(X_m)).
Let π : G → H be a homomorphism of abelian groups. Let I be a finite index set and let
X_[m] be a tuple of G-valued random variables. Let Y_[m] be another tuple of random variables
(not necessarily G-valued). Suppose that the pairs (X_i, Y_i) are jointly independent of one
another (but X_i need not be independent of Y_i). Then
D[X_[m] | Y_[m]] = D[X_[m] ,|, π(X_[m]), Y_[m]] + D[π(X_[m]) ,| , Y_[m]]
+ I[∑ i, X_i : π(X_[m]) ; | ; π(∑ i, X_i), Y_[m]].
Let m be a positive integer. Suppose one has a sequence G_m → G_{m-1} → ... → G_1 → G_0 = {0}
of homomorphisms between abelian groups G_0, ...,G_m, and for each d=0, ...,m, let
π_d : G_m → G_d be the homomorphism from G_m to G_d arising from this sequence by composition
(so for instance π_m is the identity homomorphism and π_0 is the zero homomorphism).
Let X_[m] = (X_1, ..., X_m) be a jointly independent tuple of G_m-valued random variables.
Then D[X_[m]] = ∑ d, D[π_d(X_[m]) ,| , π_(d-1)(X_[m])]
+ ∑_{d=1}^{m-1}, I[∑ i, X_i : π_d(X_[m]) | π_d(∑ i, X_i), π_(d-1})(X_[m])].
Under the preceding hypotheses,
D[X_[m]] ≥ ∑ d, D[π_d(X_[m])| π_(d-1})(X_[m])] + I[∑ i, X_i : π_1(X_[m]) | π_1(∑ i, X_i)].
Let G be an abelian group and let m ≥ 2. Suppose that X_{i,j}, 1 ≤ i, j ≤ m, are
independent G-valued random variables. Then
I[(∑ i, X_{i,j})_{j=1}^m : (∑ j, X_{i,j})_{i=1}^m | ∑ i j, X_{i,j}]
is less than
∑_{j=1}^{m-1} (D[(X_{i, j})_{i=1}^m] - D[(X_{i, j})_{i = 1}^m | (X_{i,j} + ... + X_{i,m})_{i=1}^m])
+ D[(X_{i,m})_{i=1}^m] - D[(∑ j, X_{i,j})_{i=1}^m],
where all the multidistances here involve the indexing set {1, ..., m}.