Discrete Markov Probabilistic Models: An Improved Discrete Score-Based  Framework with sharp convergence bounds under minimal assumptions
Authors: Le-Tuyet-Nhi PHAM
Dario Shariatian
Antonio Ocello
Giovanni Conforti
Alain Oliviero Durmus
Venue: ICML 2025 poster (2025)
Keywords: generative models
score-based generative models
discrete data
categorical data
convergence bound
Primary area: deep_learning->generative_models_and_autoencoders
TL;DR: An algorithm based on the score function for generating discrete data, together with their convergence bounds

Abstract: This paper introduces the Discrete Markov Probabilistic Model (DMPM), a novel algorithm for discrete data generation. The algorithm operates in discrete space, where the noising process is a continuous-time Markov chain that can be sampled exactly via a Poissonian clock that flips labels uniformly at random. The time-reversal process, like the forward noise process, is a jump process, with its intensity governed by a discrete analogue of the classical score function. Crucially, this intensity is proven to be the conditional expectation
 of a function of the forward process, strengthening its theoretical alignment with score-based generative models while ensuring robustness and efficiency. We further establish convergence bounds for the algorithm under minimal assumptions and demonstrate its effectiveness through experiments on low-dimensional Bernoulli-distributed datasets and high-dimensional binary MNIST data. The results highlight its strong performance in generating discrete structures. This work bridges theoretical foundations and practical applications, advancing the development of effective and theoretically grounded discrete generative modeling.

Discrete Markov Probabilistic Models: An Improved Discrete Score-Based Framework with sharp convergence bounds under minimal assumptions
Le Tuyet Nhi Pham
*1
Dario Shariatian
Antonio Ocello Giovanni Conforti Alain Durmus
Abstract
ct al., 2024). In continuous time, this approach benefits from strong theoretical framework, and scalable, stable learning objective.
This paper introduces the Discrete Markov Prob- abilistic Model (DMPM), novel algorithm for discrete data generation. The algorithm operates in discrete space, where the noising process is a continuous-time Markov chain that can be sam- pled exactly via a Poissonian clock that flips labels uniformly at random. The time-reversal process, like the forward noise process, is a jump process, with its intensity governed by a discrete analogue of the classical score function. Crucially, this in- tensity is proven be the conditional expectation of function of the forward process, strengthening its theoretical alignment with score-based gener- ative models while ensuring robustness and effi- ciency. We further establish convergence bounds for the algorithm under minimal assumptions and demonstrate effectiveness through experiments low-dimensional Bernoulli-distributee datasets and high- -igh-dimensional binary MNIST data. The results highlight its strong performance in gener- ating discrete structures. This work bridges the- oretical foundations and practical applications, advancing the development of effective and theo- retically grounded discrete generative modeling.
By contrast, discrete generative modeling continues to pose significant challenges. Multiple diffusion- based methods have recently been proposed for discrete spaces (Austin et al., 2021; Hoogeboom et al., 2021; Shi et al., 2024; Camp- bell et al., 2022; Holderrieth et al., 2024; Ren et al., 2024), or spaces of mixed type (Bertazzi et al., 2024), but there is still no consensus on which approach is theoretically sound or most practically efficient. Various formulations rely on complex forward kernels or computationally unsta- ble ratio-based estimators for backward transitions, leading to limited convergence guarantees and high computational costs in high dimensions. Furthermore, recent analyses of discrete diffusions have introduced valuable theoretical tools (Campbell et al., 2022; Holderrieth et al., 2024; Ren et al., 2024), yet most methods remain either overly generic or require strong assumptions, making them difficult to scale or deploy with simple, stable training objectives.
Contributions. In this paper, introduce Discrete Markov Probabilistic Models (DMPMs), a score-based generative models for discrete data inspired by Sohl-Dickstein et al. (2015) and Austin et al. (2021) that bridges these gaps. Our framework specializes the forward noising process to continuous-time Markov chain on the hypercube (0. 1]dd Leveraging theoretical insights on time-reversal Markov dynamics of this process, this choice preserves the key strengths and structure of continuous SGMs, addressing the issues raised in prior work. Our main results are sum- marized as follows:
Introduction
Score-based Generative Models (SGMs) have become a key reference for generating complex data, such images (see, e.g., Rombach et al., 2022; Ramesh al., 2022; Saharia et al., 2022), audio (Chen et al., 2020; Kong et al., 2020), and video (Ho et al., 2022; Villegas et al., 2022; Bar- Tal
Borward-Backward Construction. We provide prin- cipled derivation of the noising (forward) and denois- ing (backward) processes.
Equul contribution 'Centre de Mathématiques Appliquées (CMAP), École Polytechnique, Institut Polytechnique de Paris, 91120 Palaiseau, France "Sierra lab, Inria, Paris, France 'Department of Mathematics, University of Padova, Le Tuyet Nhi Pham <le-tuyet- nhi.pham @ polytechnique..du>>>
Score and denoiser function and stable estimation. Our analysis reveals that the time-reversed process in- herits a score function with an explicit conditional ex- pectation form. By formulating the learning objective as an L projection onto this score, we obtain a simple and principled regression loss term, as opposed to the high-variance estimators based on probability ratios
Italy. Correspondence
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Discrete Markov Probabilistic Models
used in some prior work. Furthermore, we introduce denoiser reparameterization of the score function, closely paralleling the continuous setting, which pro- vides an interpretable and practical target for model training.
1.1. CTMCs on discrete state-spaces
A CTMC (X1)eejo,r;1 defined over the discrete space X is a Markovian stochastic process which is piecewise constant with jump at random times following non-homogeneous Poisson process. As we shall see, under mild assumption, a (non-homogeneous) CTMC is uniquely characterized by a family of rate matrices (4)))e(o,T qi X x X + R. which constitutes the infinitesimal generator of the process, and should satisfy Σyex qe (z. y) = 0, for any x E X. In particular, this object allows to define Markov process whose transitions are informally characterized as h + 0 by:
Theoretical Guarantees. We prove that DMPMs con- verge to the underlying data distribution under minimal assumptions, providing non- con-asymptotic error bounds that underscore the method's reliability, In contrast to many earlier works, we prove that the sampling error grows linearly rather than exponentially with respect to dimension.
P(X+++ x| x) 52( + hg v) + o(h), (1)
Empirical Performance. We demonstrate that our approach attains competitive or superior performance on discrete datasets, including binarized MNIST, fre- quently with fewer function evaluations compared to existing discrete diffusion frameworks (e.g., 2.89 vs 7.34 FID compared to Discrete Flow Matching, Gat et al., 2024, with 2.5x fewer network calls).
where is the standard little-o Landau notation.
Definition and sampling procedure. When simple char- acterization of the transition probability matrix is not avail- able or does not exist, it is possible to simulate the process using the rate matrices, as suggested by equation (1). Pop- ular sampling strategies include Gillespie's s algorithm or r-leaping (Gillespie, 2007). In our case, we introduce the former which uses the jump rate and jump kernel associated to the process, defined as:
Notation. Given measurable space (E, E), we denote by PEE) the set of probability measures on E. Given two probability measures jr, v E P(E), the Kullback-Leible di- vergence (also called relative entropy) of with respect to v is defined as (L(u))) == log de tinuous with respect to v4, and KL(p))) p/) = too otherwise. The total variation distance between μ and v is defined as ||e - =l|ty = supAes [μ(A) - ((A].. Consider random variable X, denote by Law(() the law of X. We denote by Se the Dirac mass at æ.
(x(2, v)
de dp if / is absolutely con-
Xx(x) = Eg((zv) ke v) = -xzy
de {z
(2)
yEX
Informally, the jump rate governs the frequency of the ran- dom jumps of the process, and the jump kernel the next state at these jumps. More precisely, starting from a drawn X, from Ao and a sequence of i.i.d. random variables dis- tributed according to the exponential distribution with pa- rameter 1, {E (Te) of the process and its transition by induction setting To 0. Given (T, ), we define the next jump time as T T, + AT;+1, where
1. Forward and backward process of DMPMs
E NN J. we can define the jump times
We propose generative modeling framework that adapts diffusion-based methods to discrete spaces. Let (X, ())teo,r be forward Markov process on f0, 13dd initialized from the data distribution n², and evolving over fixed time horizon Ty > 0 toward a simple base distribution. In the continuous setting, this role is often played by the Ornstein-Uhlenbeck process converging to a Gaussian. We define the correspond- ing backward process (X xx)eetu,Ty as X, ;= XT-., which reconstructs μ* from the base distribution. While the back- ward process can be Markovian too, its transition rates or drfit terms are typically intractable and must be approxi- mated from forward trajectories, commonly done via score matching in continuous domains.
AT:1 = 1ft4==in((220 :0: 1' AT > E.}
(3)
Then, set Xx =XT, for t E (Tr, A ATy). and finally if THt1 TT, XTi. Y for Y distributed according to Cate (KT, (Xz,,)))xxx). Note that in the case where X = >> 0 for any & E [0. Ty). (T.)ien simply corresponds to the jump times a simple homogeneous Poisson process with rate X, defined as M. = EE>1 17, Another equiva- lent procedure for simulating the process is provided in the supplement (see Appendix C.I). In practice, since the inte- gral in (3) cannot be computed exactly, time-discretized sampling strategy must be employed. We present these methodological considerations in Section 1.5 below.
To adapt this idea, we introduce forward CTMC {0, 1)d where each bit flips via an independent Poisson clock. We show that its time-reversa remains a tractable CTMC with backward rates given by conditional expectations over the forward process, enabling efficient regression-bar based training in the discrete setting.
Kolmogorov equation. As a final remark, the time- marginal distributions of the process (X1)se(0,T)) starting
2

---

Discrete Markov Probabilistic Models
from Xo, of (x)) = P(X, = 2) and identified as tuple,
Ty. we denote by Me the forward marginal distribution:
satisfy the backward Kolmogorov equation:
mx(x) = P(X, =x).
(8)
div (x) (x) = [u To( (z)))= = Σ
2 (x)) (v)..v.)).
Since our chosen rate matrix 7/ is symmetric (see (5)) and pr,-o(z) > 0 for all E X, t E [0,T,), we deduce that the backward generator & for 0 & t < T is given for any x + e x
MEX
(4)
Here, we identify qi as matrix, similarly to ((X)) When the rate matrix is simple (e.g., as we use in forward process in Section 1.2), we can use the Kolmogorov equa- tion to derive the transition probability matrix (T xz) = (2o) (at)) = IP(;; xx = zo), for zo, It E x,0 & I E Ty. yielding a simulation-free procedure.
)) = = x) MT, + (1)
(9)
MT, (z))
vi
Discrete score function. Define : X - R for any E X
1.2. Simple case X {0, 1}
by
JT,, (x) MT,
x))
To introduce the key ideas, we first consider the simple case where the state space is X {00, 1). i.e., when d = 1. We will then extend our method to d > by factorizing the forward process over dimensions.
St (2)
(10)
PT,-
8t acts as a discrete derivative in X of log Pe, and thus serves as a discrete analogue of the score function in continuous models. With this notation, q (zz, y) (9) can be expressed, for any x # y E X, for 0 < t < Ty, as:
Forward process. We define the forward process (X (Xe)etoor)) as the homogeneous CTMC starting from Xo n"," and driven by a simple bit-flip process associated with the rate matrix defined for any x. y E X, as
(), = A(1 s())) -2(1 -1(1-s( st otherwise.
(11)
7'(2, v) =
if y otherwise. .
(5)
Access to the sequence (e is equivalent to having access to (77 !) [o[TT)))) and therefore allows to sample from X, for any t E [0, using the procedure described in Section 1.1. However, the score function 8 is generally intractable, as it depends on the unknown marginal distribu- tions (J4)) To address this, we derive an alternative expression for 8, in terms of a conditional expectation over the forward process. For x E X and t [0,Ty).
In the case of a constant forward rate matrix 7', the transi- tion probability matrix d!, for 0 < t < Ty, is known to be /. = exp((7/2) (Liggett, 2010), which we compute as:
(l =
1
2M 2 2
+
z otherwise
(6)
2Az
20
sx(2)=
The detailed derivations are given in the supplementary material B.1 and rely on equation (4). We note that us- ing time-dependent rate X is a straightforward exten- sion, as defining /1 = de q yields the transition matrix exp(7' S6 A,ds) = P) {- J. d,ds and leave it to future work.
2 +
4or,, - Xo (TT,
E
Tr
= Ø
1 1
+
1 a aT,- -1
(12)
with
Backward process. To recover the data distribution, we analyze the time-reversed process, which is denoted by (X (X))eeooTT)) and detined as X, XT,- t for any E J0. Tyl- Conforti & Léonard (2022, Theorem 2.8) show that (Xt)eeJ,rr) is also non- non-homogeneous CTMC, associated with a family of generator matrices ('7 ()ee(o.T,)) satisfying the time-reversal formula:
a2 e -2ht
(13)
Indeed, the score function can be computed as
(x) = 1- 1T,, (1) =1
Pr, Pr,-0o((1200)
1¹ (10)
1T, 11x)
1T, 1TT)
RXEX
PT, PTy-eju(y/zz0 200)
=
PT, - [|0([ (r) (ro) POjT, -x(ol())))
MT, (T, (Z) y) = p(, (1.
(7)
x
PT, - -10 Xno
X XT,-1=x
for any 0 & t < T and x + Ly E X, where for any t E
E
1
Pr, p Xn)
and plugging in the expression for our forward transition
3

---

Discrete Markov Probabilistic Models
matrix given in (6) we obtain equation (12). Therefore, the function s is an proopeeetiio and its approximation boils down to regression problem.
the vector in R4, with components & E {1, (I,...,dd d).
(x) := |TT- - MT, - (x))
(17)
1T,-1(x)
1.3. General state space X - 10,
where sp(() X - X is defined as (l() (x) = y, with y obtained by flipping the f-th bit of x. i.e. yf = x', and y² = x¹ for + l. Then, for 0 < t < Ty, x + y X, we can write the backward generator ' (x, y). as given in (7), as:
Forward process. We generalize the previous results for the hypercube in R",ie, i.e., the state space is X = {0. 13 with d E N We consider the homogeneous CTMC (X (y))) starting from Xa μ², defined with the following rate matrix:
( - Ex(1
X(1 ((0) 8=1
A
if lly 2112- -1
(I,
Ad 0
y x,
(14)
Score function. Note that the function thus defined is an extension to the case d > 1 of the function defined for d = 1 in (10). As a result, 8, is a conditional expectation over the forward process, where each of its components admits an expression similar to the 1d case (12).
otherwise
The corresponding sampling procedure following the one provided in Section 1.1 is given in Appendix B.2 for com- pleteness. Similarly to the one-dimensional case, we can establish an explicit expression for the transition probability matrix p, for 0 < t & T as
Proposition 1.1. The score function can be expressed as conditional expectation:
5x = E X1
(18)
)e( 9)
II (
(15)
where 1 E 10,TH), E x
1, I...., d, sy is the t-th
where 7t is defined in (6) and x (x'))=1,"' = (y') E X. The detailed computation is given in the supplementary material B.2.1 The factorization of the transition probabil- ity in (15) is of great practical interest, this tells us that the dynamic of the forward process simply consists in the single-bit forward dynamic applied independently to each component, as described in Section 1.2. As a consequence, the forward marginal distribution μr of X, admits the for- mula
component of the score function and
20
40 A0rI,-1(X
(1) Tx-t
X2)
(x 0. XT,-1) 1 1+ar,-t
-
(19)
The proof of this result is given in Appendix B.2.2. Simi- larly to the 1d case, access to the score allows to simulate the backward process following the procedure described in Section 1.1 since the the non- non-homogeneous jump rate X and jump kernel 1 of the backward process are given by
Me(x)= Σ (2(2) SEX
II F.(z,)). 1=1
(16)
Backward process and score function. Denote by (Xohejo,r)) the time-reversal process associated with (X.)eeo,ry)) and defined X, XT,-, for any E [0, As in the case d 1, Conforti & Léonard (2022, Theorem 2.8) shows that (Xx)ee0orry) is also a non-homogeneous CTMC, with backward generator matrix (7T (Te)),),T)) that satisfies (7) and therefore (9), proceeding as before. As in the case d 1, we show that ('q ().T)) depends only discrete score function, which we now introduce.
d Tx(Z)) = > =xEa {((x))
t=1
(20)
To (x(2,0) = Σ ))= 1(1- - s1(2))/ Ae(x).
for a # E X and E (0,T,).
1.4. Approximating the score function
In this section, derive the training objective to estimate the score function (s:)cejoTT)) defined in (17), which gov- erns the backward rate matrix. As in standard diffusion models, our goal is to sample from the time-reversed pro- cess, requiring approximation of the (intractable) score. Leveraging its conditional expectation structure (Proposi-
First, note that (9) and (14) yield T (e(x.)) v) = 0, for x, E X satisfying || - y/l2 + 1 and x # y. Then, for 0 < <t<<<T <T,, T
define 8; : X + nd for any I E X. sx(x) = (z)()) as

---

Discrete Markov Probabilistic Models
tion 1.1), we approximate 8n using a parameterized family {(t,z) sx())) age: where 0 is optimized via an adapted score-matching objective, defined as the function
dx(x), we introduce an additional cross-entropy loss ECE:
Ty
d
LCB : +
E
1 X xit log
log di' ( (x))
TT E
L1 : 0
- f X ]1p] dt.
+ (T x
1) log(1 - (x dt.
(21) Another objective function to fit A can be derived by using the fact that for any x E X, t E [0,Ty), E {l.....d) d}.
Based on the previous discussions, we consider linear com- bination of the losses 2den Le, SeF, respectively weighted by factors w1, w2, w3, which results in the loss Lz:
1 - (1)) is non-negative. Thus, we introduce the following entropy-based term:
A
Tf E
0.E sTy -1
st 0.2
(X.) dt,
L w 2
22e + w3LCB
(26)
$Ty
The expected value of di is given by
where h(aa) = a log(a) - (a- - 1). Minimizing this function is equivalent to minimizing:
[ (1) (27)
d
as detailed in Appendix C.4. Thus, we scale losses L1², LCE by 1/wr, ensuring a more balanced average magnitude across timesteps; see (50) and Figure 4 in Appendix C.4. This leads to the updated loss L (see (52)). Detailed deriva- tions are provided in Appendix C.4. The final training pro- cedure is outlined in Algorithm 2.
Le 0 ++
E
0.1
(x,)
T
+ ( - 1) log(1 ST, s (x(1)) ) dt.
(22)
1.5. Generative process
We further derive a discrete denoiser structure in Ap- pendix C.3, rewriting the score function as
Alike classical continuous diffusion models, exact simula- tions of the reverse process are not possible and face the same challenges: i) we do not have access to i.i.d. samples from μT,, ii) the backward process characteristics depend the score function of the forward process defined in (17), which is intractable, and iii) we have to discretize the con- tinuous process.
2 4ar, (1)) a4,
(x) 1+ 1+aT,-
(23)
where (((x)= A xz (T,
x) serves as a clas- sifier referred to as a discrete denoiser. We leverage this structure by reparameterizing our score model as:
Initialize the backward from the uniform distribution. We show that (X, +)0e,002 converges geometrically to y0, the uniform distribution over X (see Appendix B.2.3 in the supplementary document). This should be put in parallel with diffusion-based models, where the stochastic process at hand, e.g., Omsstenn-Uhlenbeed converges geometrically fast to some Gaussian distribution. The generative model can then be initialized to yd rather than pr,,
201 400, -1 (x) 8t (x)) 1 1+ aT,
(24)
1 07,-
As result, we modify our objective Σ1= 2 to fit the conditional expectations (de)cE(oTT,) instead of the score functions (se))e(0,2y)) as follows:
Tyy
d
Score approximation. We have access to a score ap- proximation )eEjo,r)) so the generative model can then be sampled analogously to the backward process, re- placing (s))ee(orT) with (sf" )re(o,Ty), leading to the non- homogeneous jump rate and kernel approximating (20):
24 0 +
/"
E
1 t=1
Bee
T
(x.) -
di,
(25)
see Appendix C.4 for more details. This reparameteriza-- tion moves the approximation from a space of ratios into probability space, which is smoother and more amenable to learning, mitigating the instability of direct score or rate estimation as reported in (Lou et al., 2024). To fit de (z) to
X
(x)
(1
((x))
t=1
Rg (xx = Σ 1 )=)(0(x)) X(1 - -11- {x)' (x).
5

---

Discrete Markov Probabilistic Models
for z.y E and t ',, Ty), where we denote by s the E-th component of sf" For completeness, Algorithm in Appendix C.2 provides the pseudo-code for ideal, continuous-tin time approximation of the backward process.
Ee defined in (22) of the loss function we consider in prac- tice. This condition naturally appears we bound the KT. divergence of the path probability measures corresponding to the approximate score s" and the ideal one respec- tively. Indeed, we prove a Girsanov type theorem which provide an explicit expression of the density between these two measures in Theorem F.12 the supplement F.2.1. While standard Girsanov theorem for diffusion implies an I.2 -type approximation error condition for generative mod- els (see, e.g., Conforti et al., 2025; Lee et al., 2023; Chen et al., 2022a), our result naturally involve the entropic-type condition (28) due to the discrete structure of our noising process.
Time discretization. Exact integration of jump rates is infeasible in practice, so we discretize time and approxi- mate the backward rate and kernel using piecewise con- stant functions. Let {t*] be time grid with step sizes Tk 1x- 1--1- Given Xi, for x # y X and t E [t,, 1R+1), we set:
(/ (z. =
(1
5/
0-,1 (X 1/ 11 (=)
8=1
Assumption 2.2. The data distribution does not admit any zero-value, i.e., 4 (a) E (0, 1) for any x E X.
= 34 (I, u)) 1 (I,y),
where 8g (x. = Ete o (x: y=p()))) t/
Assumption 2.2 implies that the data distribution has the finite Fisher-like information
Sic
This yields a tractable CTMC (1ee which can simulated starting from yd. Under mild conditions, its final law converges to the target distribution. The associated DMPM sampler is given in Algorithm 3, Appendix C.5, with time-schedule choices listed in Table 2.
Σ h (00380)-(000
(rr(1() = E
< <00,
(29)
with == - log((du "lyp""dd")), Note that Assumption 2.2 is put in parallel with the finite relative Fisher information condition provided by Conforti et al. (2025). However, Assumption 2.2 is much simpler as the state space finite, and the function is only infinite μ² has not full support.
Flips sampler. The standard sampler updates one bit at each timestep. To improve parallelism and sample diver- sity, we propose flip-schedule where Mr, components are flipped simultancously at step ts. based on the probability distribution defined by h.a. We consider linear and cosine fii-scheduless (Table 3), implemented in Algorithm 4, Ap- pendix C.5.
We now ready to state the error's bound of the generated data using DMPMs given in Algorithm 3, noting that every measure on the hypercube possesses finite entropy.
Denoise-renoise sampler. We also introduce denoise- renoise sampler based on the discrete denoiser from Equa- tion (23). Inspired by multistep consistency models (Song et al., 2023), this method alternates denoising from lu = to Ty and re-noising back to 4,, and so on. The full procedure is detailed in Algorithm 5 and Appendix C.5.
Theorem 2.3. Under Assumption 2.1 and Assumption 2.2, the following bound holds
KL (Law (7, Ee ANT (L
(30)
+ A (M*) XCT,,
with == max
K).
2. Convergence of DMPMs algorithm
This section provides quantitative error estimates between the generated final distribution Law( { and our data distribution μ² via the Kullback-Leibler divergence KL. To this end, we consider the following assumptions the parameterized score and the original data distribution:
Theorem 2.3 is one of our distinguishing results, which guar- antees the convergence of DMPMs algorithm, and makes it stronger than other algorithms built before for discrete target distribution.
The term cTy in (30) appears because the score function st is replaced in the discretization by its approximation of sat- isfying Assumption 2.1. The term 4XT, KLTT repre- sents the initialization error, as backward dynamic starts at 7d instead of μr,, Finally, the term ((²)((")) means that the data distribution μ²' cannot be peculiar, in the sense that μ does not admit any zero-value. The detailed proof of Theorem 2.3 is given in the supplementary material F.5.1.
Assumption 2.1. Let h(a)= == log(a) - (a- 1) for a > O. There exists E (0, 1) such that
d Σ (1
0², Ayh
1 St F
(XT)-aa)
(X
max EE oEkgk
Sec
Se.
1=1
tt
(28)
Note that Assumption 2.1 is induced by the entropic term
Following Conforti et al. (2025, Theorem 3), a tighter
6

---

Discrete Markov Probabilistic Models
bound on the sampling error, one that scales logarithmically rather than linearly with the discrete Fisher information, is achieved with appropriate sequence of step sizes.
information By (Ra) is always finite. As a result, Assump- tion 2.2 is no longer required. To obtain then complexity bound for DMPMs on its discretization error without As- sumption 2.2, we bound in our next result, the total variation distance between je and pry for rj > 0.
Theorem 2.4. Let e E (0, 1/2] and f > 1 2c. Sup- pose Assumption 2.1 and Assumption 2.2 hold, and L d- (1²) 2. Choose an exponentially decreasing step- sizes, i.e., Tk+11 mmin {max {Ty Lx, a) 13 for k < K, with = 1/ L. then we have that
Proposition 2.7. For any nj E (0, {Ty, 2)), the fol- lowing holds
| - 1 1 < 2(1 (1)
(34)
KL(Ø" [Lw (x S
-ANT -LAT/KK((A h1t) + ACT,
The proof of Proposition 2.7 is provided in the supplement F.6.2. Combining Theorem 2.6 and Proposition 2.7, we deduce that Corollary 2.8. Connsider the sequence of step-size as in Theorem 2.6 and let Assumption 2.1 hold. Choosing
+ AAel[1 + log( L)] (31)
The proof of Theorem 2.4 benefits from the choice of the step-size's 's scheme and is postponed to Appendix F.5.2. We deduce the following complexity result for DMPMs to achieve an é > discrctization error.
1 1 (1 c)/ld
22
1 =
c= Ad + log(n (35)
Corollary 2.5. Consider the sequence of step-size as in The- orem 2.4 and suppose Assumption 2.1 I and Assumption 2.2 hold. Choosing
A
d
Ty = + 4X
log
ne2
kT(()²)))))
implies that
c= Ad[1 + log(L))
and Ty
log
4A
(32)
K d'1 [=50l--Hogg////llllodd//+/+++++
we gel
and the following bound holds
K s d[1 log(L) [log(KL(** (/e) + log(L)) /e,
1| - Law -n)
(x |TV Set v VelTT - 1)
and makes the approximation error Ö(e (og((L((m* (7))), where the notation Ô means that logarithmic factors of d, have been dropped.
The proof of Corollary 2.8 is given in Appendix F.6.3.
The proof of Corollary 2.5 is provided in Appendix F.5.3.
3. Existing works on diffusion-hased generative models for discrete data
In our next result, we get rid of Assumption 2.2 using an early stopping strategy.
We briefly review existing approaches to discrete gener- ative modeling based on diffusion processes. Additional discussion is provided in Appendix A.
Theorem 2.6. Under Assumption 2.1,for any E (0,TH) let E (0,1/2 and T -1 11 2 21+ 11+2 2c. Set T- (1a)) and assume that L > 2. Choose the constant and expo- nentially decreasing sequence of step-size, i.e. satisfying Tk+11 = c mmin {max {T, - 7 - tx, 1/L), 13 for le < K and the associated discrete time scheme {1x { such thut to = 0 and tk- = =Ty- - 17. Then, the following bound holds
A first class of methods maps discrete variables into continu- ous spaces, enabling the use of classical diffusion machinery (Dieleman et al., 2022; Chen et al., 2022b; Richemond et al., 2022), but struggle to scale in dimensions and lacks theoret- ical guarantees.
(T,(H,, [Law( X x))= S -o + +AcTTT - 11)
Other methods, such as Argmax Flows and Multinomial Diffusion (Hoogeboom et al., 2021), operate directly in discrete spaces and use categorical noise models or argmax transformations handle discrete tokens, but can impose considerable computational overhead.
Aed[1 + log(n -1]]
(33)
Theorem 2.6 consequence of Theorem 2.4 when the backward dynamic stops early at M, instead of μ². We benefit from the structure of M4 to obtain a bound growing linearly with dimension, which is advantageous for high- dimensional sampling. The full proof is deferred to Ap- pendix 1. It is worth noting that (16) ensures that (ay always positive for any 1) E (0, Ty), thus the Fisher-like
More recently, CTMC-based frameworks were introduced (Campbell et al., 2022), upon which flow matching tech- niques were adapted to the discrete domains (Gat et al., 2024; Campbell et al., 2024), using conditionally con- structed rate matrices built ad-hoc, contrasting with our
7

---

Discrete Markov Probabilistic Models
principled time-reversal derivation.
sumption 4.5 corresponds to the Lipschitz continuity of the score function." However, it is now well known that such an assumption is unnecessary in the continuous setting.
Holderrieth et al. (2024) proposed a general framework for generator matching over arbitrary Markov processes, assuming access to conditional interpolating distribution, leaving the choice of interpolating process and loss function to problem-specific adaptation.
4. Experiments
The full experimental details are available in Appendix D. We evaluate our Discrete Markov Probabilistic Model (DMPM) two datasets. The first is low-dimensional synthetic sawtooth dataset, with dimension 4 < d < 16. The second is binarized MNIST, with d = 32 x 32. We ex- plore various design choices, and compare DMPM against MD4 (masked diffusion) (Shi et al., 2024) and DFM (dis- crete flow matching) (Gat et al., 2024), two state-of-the-art discrete generative approaches.
Alternative directions include masked diffusion models (Austin al., 2021) and stochastic integral formulations (Ren et al., 2024), aiming to balance tractability and the- oretical soundness. Shi et al. (2024); Sahoo et al. (2024) propose efficient training via absorbing-state kernels, opti- mizing model parameterization and loss. Meanwhile, Lou et al. (2024) model the score function as density ratio rather than discrete denoiser. This yields an entropic regu- larization loss equivalent (22), missing the L projection and cross-entropy terms applied to the discrete denoiser employed in our formulation.
4.1. Experiments on limeniiaimnniinnll Bernoulli Data
We study a discrete data distribution such that each com- ponent of X = (X:) ~ p is independently distributed as Bernoulli(ps). The map i ++ p; forms a sawtooth pattern (see Figure 6). We evaluate performance using custom Sliced Wasserstein Distance (SWD) between the learned and true distributions (see Appendix D.3). Indeed, the state space size 2d can get too big for traditional histogram-base metrics like KL divergence or Hellinger distance.
Concurrently with our work, Bach & Saremi (2025) propose a discrete analogue of Gaussian smoothing, entirely forgo- ing the continuous-timg framework. Their denoising-bar based method offers static-noise alternative to CTMCs, yielding Langevin-type sampling dynamics on the hypercube.
Theoretical results for discrete generative models are much scarcer than for their continuous counterparts. To the best of our knowledge, only Camphell et al. (2022); Ren et al. (2024) provide theoretical guarantees, and these rely on significantly stronger assumptions than those used in our work.
Regarding Theorem 1 in Campbell et al. (2022), we note that our approach does not require L -bound on the score approximation error, but only an LL-bound. Moreover, we do not impose any assumptions on the marginal density of the forward process (cf. Assumption 2), but only on the data distribution itself. We also avoid placing assumptions on the backward transition rates (cf. Assumption 3). In contrast to Campbell et al. (2022), we impose no conditions the rates or densities of the forward and backward processes. Additionally, their discretization error scales linearly with the time horizon, whereas our bounds do not incur such a cost.
SWD
T/-3
1
cosine; T
linesr, T. 3
lineer, Tim
quadratic, Tym
quath sti. Ti
12 16 30 50
100
Reverse Stops
Figure 1. Comparison of time-schedules (cosine, linear, quadratic) and time horizon (Ty vs. Ty = 10).
Time horizon and time-schedule. We study the impact of the time horizon Tr and various time-schedules--nifon quadratic, and cosine (see Table 2)-on model performance. Figure 1 presents results for a model trained with the basic LLa loss on data with d = 16, evaluated across multiple reverse step counts. The cosine schedule with T, yields the best performance in terms of sliced Wasserstein distance (SWD), outperforming other schedules and longer horizons, while also requiring fewer reverse steps. This indicates that T, 3 is sufficient to reach near-unifornity during forward diffusion, without excessive transitions to uniform states. We adopt this configuration for all subsequent experiments.
Concerning Ren et al. (2024), and in particular Theorems 4.7 and 4.9, we highlight that make no assumptions on the score function. In their Assumption 4.4, time- dependent -.--nbund of the form (.)) & 1 V t-1 is imposed on the true score 8t, and time-uniform L -bound is assumed for the learned score sf. As in Campbell et al. (2022), these assumptions are arguably unnatural, as they are not placed directly on the data distribution but on more com- plex transformations of it. Furthermore, Assumption 4.5 in Ren et al. (2024) imposes quantitative form of Lipschitz continuity on st, and as the authors themselves state," "As-
Comparison with tate-of-the-art methods. We compare
8

---

Discrete Markov Probabilistic Models
d
4
8
12
16
Method
10
25
50
100
200
500
DEM
6.102
8.864
5.019
8.302
FID
227.55
156.26
88.93
39.62
16.26
7.34
DFM
MD4
9.376
7.670
4,045
8.037
Pt"
0.00
0.00
0.01
0.14
0.41
0.68
DMPM
3,174
3.308
2.34
2.515
97.97
33.50
14,06
4.48
3.43
MD4
0.04
0.29
0.57
0.76
0.83
0.86
Figure 2. SWD J, in 1e-3, for DMPM, MD4, and DFM across data dimension d. Selected the best result with #steps 2 & K & 200 for cach method.
FID
16.30
9,98
11.07
9.07
7.80
10.84
DMP
0.64
0.92
0.93
0.93
0.93
0.70
FID
78.20
20.94
8.62
3.98
2.89
4.36
DMPM
F(
0.13
0.67
1.00
1.00
Plas: constior Tips
Table I. FIDJ (first row cach method) and Ff t (sccond row) MNIST for various total reverse steps. We highlight the best result in bold, the 2nd best in italics, and underline the 3 best.
Ti co corstont fits
Inver flize
2
10
Denoise-renoise sampler and comparison with state-of- the-art. We further exploit the discrete denoiser struc- ture through a denoise-renoist sampler (Algorithm 5, Ap- pendix C.4), which alternates single-step denoising and re-noising in a multistep loop. This approach leverages the model's learned transitions more effectively, leading to notable gains in sample quality.
FeVerSe steps
Figure 3. FID MNIST, linear vs. constant schp-sceeuules scaled for d total bit flips, with various loss configurations.
We compare DMPM, trained with the balanced loss 21,1, under two sampling strategies-ddenoissreennoe car hiip-shedule-agglie (masked diffusion) and DFM (discrete flow matching). Re- sults are reported for varying numbers of reverse steps K, using both Fréchet Inception Distance (FID) and the File metrie, harmonic mean of coverage and density (Naeem et al., 2020). While FID captures overall realism, F re- flects local distributional fidelity; full details are in Ap- pendix D.3.
DMPM (with cosine schedule, Ty 3, and Σ1 loss) against MD4 and Discrete Flow Matching (DFM). Fig- ure 2 shows SWD scores across varying data dimensions d. DMPM consistently outperforms both baselines, achiev- ing superior results with significantly fewer reverse steps (typically 30 vs 100), highlighting its sampling efficiency.
and lin- state-of-the-ar baselines: MD4
4.2. Experiments on MNIST
Binary
DMPM sampler and flip-schedule. We evaluate the DMPM sampler using constant and linear flip-schedules (M,, ) Empirically, performance is optimal when the total number of flipped bits matches the input dimension, i.e. Ek_ Mr = d. We scale each ftip-schedule accord- ingly. Figure 3 illustrates that performance remains stable across different values of K as long as the total number of flips is held constant, allowing for significant speedups by reducing the number of reverse steps and thus network calls.
As shown in Table 1, both DMPM variants (rows 3 and 4) consistently outperform the baselines. At K 200, DMPM (denoise-renoise) achieves the best FID (2.89) and perfect rde (1.00), surpassing MD4 (4.48) and DFM (16.26). Even with K = 50, it maintains strong results (FID 8.62, F 0.87). Similarly, DMPM with flip-schedule achieves FID below 10 and ry above 0.90 at K = 25, demonstrating excellent efficiency with minimal network calls.
Sample grids illustrating visual quality are shown in Figure 7 and Figure 8.
Using a model trained with the weighted loss Ow 1//3,1/3.1/3 and a linear flip-schedule, we achieve best FID of 4.77 using only 25 network calls. The linear schedule consis- tently outperforms the constant variant; flipping fewer bits early helps guide the model toward more coherent samples, similarly as what is reported for MD4 (Shi et al., 2024).
4.3. Conclusions
Our experiments show that DMPM consistently matches surpasses state-of-the-ard performance both low- and high-dimensional discrete datasets. On binarized MNIST, it achieves better FID and F than competing methods, with fewer network calls. These gains stem from our princi- pled reparameterization of the score function as a denoiser, and a stable, well-structured training objective. Together, they yield a scalable and theoretically sound framework for discrete generative modeling.
Loss function contiguration. Among the losses we tested, the balanced form 2 I.. consistently yields the best results. The weighting factor w helps normalize the scale of the l2. cross-entropy, and KL components at each timestep, improving overall synergy. Figure illustrates these effects. Nonetheless, simpler variants such as ΣLa and 2/; already achieve near-optimal performance in many settings.

---

Discrete Markov Probabilistic Models
Impact Statement
co-design, 2024. URL www.t:ttttssiii...eeea 2402.04997.
2402. 04997.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which feel must be specifically highlighted here.
Chen, N., Zhang. Y., Zen, H., Weiss, R. J., Norouzi, M., and Chan, W. Wavegrad: Estimating gradients for waveform generation. arXiv preprint (rXiv:2009.00711 2020.
Chen, S., Chewi, S., Li, J., Li, Y., Salim, A., and Zhang, A. R. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. arXiv preprint arXiv:2209. 11215, 2022a.
Acknowledgements
The work of L.T.N.P. was supported by the École Doctor- ale de Mathématiques Hadamard (EDMH). The work of A.O. was funded by the European Union (ERC-2022-SYG: OCEAN-101071 (61). The work of D.S was funded by the European Union (ERC. Dynasty, 101039676). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Nei- ther the European Union nor the granting authority can be held responsible for them.
Chen, T., Zhang, R., and Hinton, G. Analog bits: Gen- erating discrete data using diffusion models with self- conditioning, arXiv preprint arXiv:2208.04202, 2022b.
Conforti, G. and Léonard, C. Time reversal of markov processes with jumps under a finite entropy condition. Stochastic Processes and their Applications, 144:85-124, 2022.
This work was granted access to the HPC resources of IDRIS under the allocation 3025-AD011015320 made by GENCI.
Conforti, G., Durmus, A., and Silveri, M. G. KI convergence guarantees for score diffusion models under minimal data assumptions. SIAM Journal on Mathematics of Data Science, 7(1):86- (00),,6-109, 2025.
References
Delatte, P. Lecture 5. hahn-banach extension theorem. Lec- ture note, 2022.
Austin, J., Johnson, D. D., Ho, J., Tarlow, D., and Van Den Berg, R. Structured denoising diffusion models in discrete state-spaces. Advances in Neural Information Processing Systems, 14:17981-17993 2021.
Dieleman, S., Sartran, L., Roshannai, A., Savinov, N., Ganin, Y., Richemond, P. H., Doucet, A., Strudel, R., Dyer, C., Durkan, C., et al. Continuous diffusion for categorical data. arXiv preprint arXiv:2211. 2.t.::2211./5099, 2022.
Bach, F. and Saremi, S. Sampling binary data by denoising through score functions, 2025. URL httpps://axxiv
Gat, I., Remez, T., Shaul, N., Kreuk, F,, Chen, R. T., Syn- naeve, G., Adi, Y., and Lipman, Y. Discrete flow match- ing. Advances in Neural Information Processing Systems, 57:133345-13332 2024.
Bakry, D., Gentil, I., Ledoux, M., et al. Analysis and geome- try of Markov diffusion operators, volume 103. Springer, 2014.
Gavrilyuk, I., Makarov, V., and Vasylyk, V. Exponentially convergent algorithms for abstract differential equations. Springer Science & Business Media, 2011.
Bar-Tal O., Chefer, H., Tov, O., Herrmann, C., Paiss, R.,
Zada, S., Ephrat, A., Hur, J.. Liu, G., Raj, A., et al. Lu- miere: A space-time diffusion model for video generation. In SIGGRAPH Asia 2024 Conference Pupers, pp. 1-11, 2024.
Gillespie, D. T. Stochastic simulation of chemical kinetics. Annual Review of Physical Chemistry, 58(Volume 58, 2007))35-55, 2007. ISSN 1545-1593. doi: https:
Bertazzi, A.. Oliviero-Durmus, A., Shariatian, D., Simsekli, U., and Moulines, E. Piecewise deterministic generative models. arXiv preprint arXiv:2407.194448 2024.
URL
http:::/www..ammaarevvieeee crg/
physchem. 55.00mm.......0........0.000 104633
Campbell, A., Benton, J., De Bortoli, V., Rainforth, T., Deli- giannidis, G., and Doucet, A. A continuous time frame- work for discrete denoising models. Advances in Neural Information Processing Systems, 35:28266-28279, 2022.
Ho, J., Salimans, T., Gritsenko, A., Chan, W., Norouzi, M., and Fleet, D. Video diffusion models. Advances in Neural Information Processing Systems, 35:8633 2022.
Campbell, A., Yim, J., Barzilay, R., Rainforth, T., and Jaakkola, Т. Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein
Holderrieth, P., Havasi, M., Yim, J., Shaul, N., Gat, I., Jaakkola, T. Karrer, B., Chen, T., and Lipman,
10

---

Discrete Markov Probabilistic Models
Generator matching: Generative modeling with arbitrary markov processes. arXiv preprint arXiv:2410.20587, 2024.
Naeem, M. F., Oh, S. J., Uh, Y., Choi, Y., and Yoo, J. Re- liable fidelity and diversity metries for generative mod- els. In International conference machine learning, pp. 7176-7185, PMLR, 2020.
Hoogeboom, E., Nielsen, D., Jaini, P., Forré, P., and Welling, M. Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 14:12454-12465 2021.
Nichol, A. Q. and Dhariwal, P. Improved denoising diffu- sion probabilistic models. In International conference on machine learning, pp. 8162-8171. PMLR, 2021.
Ikeda, and Watanabe, S. Stochastic differential equations and diffusion processes, volume 24. Elsevier, 2014.
Nutz, M. Introduction to entropic optimal transport. Lecture
notes, Columbia University, 2021.
Karras, T., Aittala, M., Aila, T., and Laine. Elucidating the design space of diffusion-based generative models. Advances in neural information processing systems, 35: 26565-26577, 2022.
Owen, A. B. Monte carlo theory, methods and examples; 2013. statweb, 2021.
Ramesh, A., Dhariwal, P., Nichol, A., Chu, C., and Chen, M. Hierarchical text-conditional image generation with clip latents. arXiv preprint wrXiv:220..06125, 1(2):, 2022.
Kong, Z., Ping, W., Huang. J., Zhao, K., and Catanzaro, B. Diffwave: A versatile diffusion model for audio synthesis. arXiv preprint XXX1:2009.009760 2020.
Rao, M. M. and Ren, Z. D. Theory of orlicz spaces. (No Title), 1991.
Kynkäänniemi, T., Karras, T., Laine, S., Lehtinen, J., and Aila, T. Improved precision and recall metrie for assess- ing generative models. Advances in neural information processing systems, 32, 2019.
Ren, Y., Chen, H.,, Rotskoff, G. M., and Ying, L. How discrete and continuous diffusion meet: Comprehensive analysis of discrete diffusion models via stochastic inte- gral framework. arXiv preprint arXiv:2410.0360) 2024.
Laszuk, D. Python implementation of empirical mode decomposition algorithm. ht https: http://ggttthhocco com/ Aaszukdawid/PyEnee 2017.
Richemond, H., Dieleman, S., and Doucet, A. Cat- egorical sdes with simplex diffusion. arXiv preprint arXiv:2210. 14784, 2022.
Lee, H., Lu, J., and Tan, Y. Convergence of score-based generative modeling for general data distributions. In In- ternational Conference on Algorithmic Learning Theory, pp. 946-985. PMLR, 2023.
Rombach, R., Blattmann, A., Lorenz, D., Esser, P., and Ommer, B. High-resolution image synthesis with latent diffusion models. In Proceedings of the IEEF/CVF con- ference on computer vision and pattern recognition, pp. 10684-10695, 2022.
Léonard, C. Orlicz spaces. Unpublished notes, available the Internet, 2007.
Saharia, C., Chan, W., Saxena, S., Li, L., Whang. J., Denton, I.,, Ghasemipour, K., Gontijo Lopes, R., Karagol Ayan, B., Salimans, T., et al. Photorealistic text-to-image dif- fusion models with deep language understanding. Ad- vances in neural information processing systems, 35: 36479-36494, 2022.
Léonard, C. Girsanov theory under finite entropy condi- tion. In Séminaire de Probabilités XLIV, pp. 429-465. Springer, 2012.
Liggett, T. M. Continuous time Markov processes: an introduction, volume 113. American Mathematical Soc., 2010.
Sahoo, S. S., Arriola, M., Schiff, Y., Gokaslan, A., Marro- quin, E., Chiu, J. T., Rush, A., and Kuleshov, V. Simple and effective masked diffusion language models, 2024. URL https: //tp///aaivvvv//////ea org/ wttg///////// / /2004 07524.
Lou, A., Meng, C., and Ermon, S. Discrete diffusion lan- guage modeling by estimating the ratios of the data dis- tribution, 2024. URL hitps: httplpp:///pppeeeeee opw.reviewwwwweem/m//e/.. net/ forum? hatmmmdd==1mmmmmttememmmm
Shariatian, D., Simsekli, U., and Durmus, A. De- noising Lévy probabilistic models. arXiv preprint arXiv:2401, 22440718600 18609, 2024.
Méliot, P.-L. Convergence of random variables and large deviations. Lecture note, 2025.
Shi, J., Han, K., Wang, Z., Doucet, A., and Titsias, M. Simplified and generalized masked diffusion for discrete data. Advances in neural information processing systems, 37:103131-103166 2024.
Mozumder, M. S. U. Some derivations on levy and jump processes. GANIT: Journal of Bangladesh Mathematical Society, 29:11-22, 2009.

---

Discrete Markov Probabilistic Models
Sohl-Dickstein, J., Weiss, E., Maheswaranathan, N., and Ganguli, S. Deep unsupervised learning using nonequi- librium thermodynamics. In International conference machine learning, pp. 2256-2265. pmlr, 2015.
Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., and Poole, B. Score-based generative model- ing through stochastic differential equations, 2021. URL https: / arxiv.iiivvv//vvi org/ abs///s///////// 2011 11. 13456.
Song, Y., Dhariwal, P. Chen, M., and Sutskever, Con- sistency models, 2023. URL htttp:://axxiv.orrtt
abs/2303. 01469.
Touzi, Optimal stochastic control, stochastic target prob- lems, and backward SDE, volume 29, Springer Science & Business Media, 2012.
Villegas, R., Babaeizadeh, M., Kindermans, P.-J., Moraldo, H., Zhang, H., Saffar, M. T., Castro, S., Kunze, J., and Erhan, D. Phenaki: Variable length video generation from open domain textual descriptions. In International Conference Learning Representations, 2022.
Yoon, E. B., Park, K., Kim, S., and Lim, Score-based gen- erative models with Lévy processes. Advances in Neural Information Processing Systems, 36:40694-40707, 2023.
Zitkovic, G. Uniform integrability. course noles: Theorem if Probability II, Fall 2015: Lecture, 12, 2015.
12

---

Discrete Markov Probabilistic Models
A. Existing works on diffusion-based generative models for discrete data
This section provides details of the recent researches on discrete generative models.
Embedding discrete structure in the continuous space. To keep the benefits of continuous representations, Dieleman al. (2022) and Chen et al. (2022b) mapped discrete structures into Euclidean space, while Richemond et al. (2022) placed them into the simplex, all while continuing to use forward continuous diffusion models. In particular, Dieleman et al. (2022) proposed a continuous diffusion model for categorical data, which has some advantages over autoregressive models, such as the ability to perform arbitrary infilling and a more flexible sampling process. However, this method comes with an expensive training cost and lacks of strong theoretical guarantees.
Argmax flows and Multinomial Diffusion. Hoogeboom et al. (2021) introduced two new generative models, Argmax Flows and Multinomial Diffusion, to handle categorical data like text and image segmentation. Argmax Flows connect discrete data with continuous models by using an argmax function combined with a probabilistic inverse, making categorical distributions casy-learning Multinomial Diffusion process uses a categorical distribution to add noise to discrete data and then trains model to reverse the process. However, both Argmax Flows and Multinomial Diffusion have some limitations: computational costs increase due to additional steps, and the theoretical guarantee is missing.
Designing the flow processes over the discrete state space. Campbell et al. (2022) introduced the first complete continuous-time framework for denoising diffusion models applied to discrete data. They used CTMCs to model the forward noising process and its time-reversal dynamics. While the core idea is similar to ours, their approach is more complex because their method consider generic CTMC and is not specialized to the noising process that we consider. As result, their method essentially boils down learning density ratios which can be computationally demanding and fail to offer efficient approximation in high dimensions. They also added a correction step to bring the sample distribution closer to the desired one, which increased the practical training cost Gat et al. (2024). By focusing on the random-walk CTMC on X, we were able to provide a discrete counterpart to the score function that is learn in continuous diffusion models and also to establish strong convergence guarantees for our method. Campbell et al. (2024) further extended this line of work by adapting flow-matching techniques to discrete domains using conditionally defined rate matrices. However, their method does not derive the reverse process from a time-reversal principle, and thus relies on hand-crafted dynamics with limited theoretical justification.
Generator Matching, Another recent approach to handle discrete data is generative modeling with arbitrary Markov processes using generator matching, introduced by Holderrieth et al. (2024). In this approach, the authors design an appropriate Markov process that transforms a simple distribution into the desired data one using a generator, which can be efficiently trained with neural network. This method quite flexible and can be applied to different state spaces, especially in discrete settings. However, this method being very generic suffer from the same drawback as Campbell al. (2022).
Masked diffusion models. One important step toward more advanced models is the "masked" diffusion process, discrete diffusion approach first introduced by Austin et al. (2021). Recently, Shi et al. (2024) looked into this model further, simplifying its training objective by expressing it as a signal-to-noise ratio, which helps highlight some useful features. However, despite these improvements, the model still lacks theoretical guarantees. Sahoo et al. (2024) improved upon this direction by leveraging the structure of the absorbing kernel and refining the bridge-based reverse process, leading to more efficient optimization. The model's reliance on absorbing-ste approximations and heuristic training objectives limits its theoretical grounding.
Direct score parameterization. Lou al. (2024) propose to learn the score function directly as density ratio rather than denoising map. This formulation leads to single entropic regularization loss equivalent to (22) in our paper. However, it misses our discrete denoiser decomposition we use and the associated L projection and cross-entropy terms, which improve training stability.
Discrete Diffusion Models via a Stochastic Integral Framework. Ren et al. (2024) introduced a new way to analyze discrete diffusion models via Lévy-type stochastic integrals and expanded Poisson random measures. Specifically, they established the stochastic integral expressions of the noising and denoising processes for the categorical data. They provided unified error analysis framework and showed the first error bound for their algorithms in KL divergence. However, their results rely on strong assumptions in contrast to our results. Besides, our bounds are simpler and better, in particular with respect to the time horizon.
Denoising without time dynamics. Concurrently with our work, Bach & Saremi (2025) propose a discrete denoising model
13

---

Discrete Markov Probabilistic Models
that avoids continuous-time formulations altogether. Their method treats Bernoulli corruption analogue of Gaussian smoothing, enabling Langevin-style sampler the hypercube. This approach is complementary CTMC-based methods and their dynamic interpretability.
Our paper takes step toward bridging these gaps. By clearly describing the forward Markov process, we can express the score function as a conditional expectation, which helps us avoid the costly signal-to-noise ratio training used Shi et al. (2024). This way, we not only offer simpler and more affordable training approach, but also provide solid theoretical guarantees for our models in practice.
B. Interpretation of DMPMs
B.1. The simple case X = {0,1}
We start by explicitly constructing our forward process (X (Xt)) starting from X 0 ~ μ², Consider the fixed jump times (Ti)ee (1.....yyIII üd (ni of a Poisson process over [0, Tyl where N ~ Pn(ATT) is the number of jumps, and x > 0 is a prescribed jump rate. Without loss of generality, we assume that 0 = To & T1 < < TTN- We define recursively ())eE)o,Ty) over (Ti, 1+ Suppose that Xr, has been defined set X, = Xr, for any t E Ti+1) and XT.. 1- Xr. It is well known that (X (e)eet0,r is a Markov jump process (Owen, 2021, Section 6) with generator 7 defined for any E X as
&
X, yy
7' = 1-x,
(36)
otherwise.
The transition probability matrix IxX,= = y/ x) = 7 v). for x, EEEEEXIIISS Ty, is known to be
1 + 20-22M 2M
=
71((,))= =
(37)
1 -2M
otherwise
Detailed calculation of the transition probability in (6). Based on the Kolmogorov equation, the transition matrix P ! for 0 D& & , admits the following formula
8!=e7"'
where 7 is define in (5). Clearly, the generator 7' admits two eigenvalues 0 and 22 associated with the eigenvectors respectively. Thus we can diagonalize 7 as
(1 1)² and (1 -1)" T
7'= = ( (
(1 114 1 : 22
0 2
-
and the transition matrix 7i follows
-!=C = - ) (1)
-1
1
1 c 2At
1 1- 2-20
2
1 2ht
1 e -21
B.2. General state space X 10
B.2.1. FORWARD PROCESS
We consider the jump times (I.... iid On, Ty]) of a Poisson process over [0, Tyl where N Pn(XT)) is the number of jump. Without loss of generality, suppose that T₁ 0 < Ti
< Tx. We define recursively (X ()ETO.TT) over (T,, T--1l as follows. Suppose Xr, has been defined. We set X, = Xz, for t E (T,, TH11, and finally, set X T = 1 - X T where & ~ Unif([L,.... (I,...,d)),, with & independent from the past, and X T;+1 The associated generator matrix given in (14). We now seek to obtain the associated transition matrix.
X1 T; for j # l.
14

---

Discrete Markov Probabilistic Models
Proof of (15). We start with note that the generator matrix of be expressed sum of matrices 7e follows
X
if = y² for i + and of # y
with (' y)
if x
0.
otherwise..
Notice that 7' also admits the following formula with respect concerning the tensor product
/ল 11 I ... 1 & 1 2xl8 81.
(38)
d times
with I the 2 identity matrix and À --X X )) which is the 9t matrix in the previous product. Indeed, by the
definition of tensor produet, for any x (x') (w')=_ E X, we observe that
(T & & 7 8 3 (), T(x MT) "......A I(. (x0,0²)
if x yi for i + and x² + y²
- if y
0
otherwise
which is exactly the expression of (x, y). We now use the Kolmogorov equation combined with the expression of 7f in (38), and apply the formula [S4++ e B for any matrix A, B (Gavrilyuk al., 2011, 1, Appendix) to get
p. न ecin 17
A @.. @..@ X e
d times
We are thus left with the computation of e!A, It is clear that the eigenvalues of À are 0 and -2,, with the corresponding eigenvectors (1 1)" and (1 -1)" respectively. Consequently, we can compute e² as: for any a, b E {0, 1),
bl(a,b) = at (a,b) (a, = 2 + e 2ht
a =b b, if #
2
and the formula of transition probability d. for 0 EL T follows: for any
(x*) ( and y (1)) in X,
d
1
if =x'=yy-
(z = 11 ol 1/)), with 71
z
2M
otherwise
B.2.2. CONDITIONAL EXPECTATION EXPRESSION OF THE SCORE FUNCTION
Proof of Proposition I.I. Fix x E X and 1,..., First note that by definition pry as the marginal distribution of the noising process, we have
(Ty-<(x)= UT, (x(( = Σ (1
- -D (0)
(39)
zeX
15

---

Discrete Markov Probabilistic Models
The formula of transition probabilities (2) (x)) (x)) combined with the definition of (z(( lead to
(=)) = II pl, (x' pl(x)) [=1
(x(x)))((
- (1))) II 1 -
7 - {1((1))
1 (2,2))
(z),x)
Substituting this into (39) implies
pry-)(x) - Mr, (1,-(((((xx)) = => (o(2) (2)
D' r, 1 (2)
xEX
Σ
2c 2x(TX
40 2A(T - 1) (1 222
P xo xo= 2, -
1 + 1 -
1 1- e-e 42(Ty-1)
xex
where the last equality comes from the formula of 7, and the fact that if 2º = (z())(x)) then of # x.. Therefore, the score function in components are
(x(x) = MT,, (1)) PT, (
MS, -1)-
2e -1(
4e (e-2XTT--1 2)2
p No xxo 2| σ
+ c- 22(T)-1)
1 1 c-c-4a11 --1TTT-T-1)
xEX
-X8/2
X1y-1= = ]
-0
4a0, -1 (X T--t
=
+ ar,
1 1-0 0T,-1
2
for E [0. Ty)
where ---22 -2xt and we finish the proof of Proposition 1.1.
B.2.3. INVARIANT MEASURE OF THE FORWARD PROCESS
As we have a comprehensive understanding of the forward process, we observe that its invariant measure is the uniform distribution over X, denoted by nd Indeed, for any X and E [0,
1 Σ
1 1/2 -x)
( ()))) Σ (()
)((z,z)=
=
2d
2d
ZEX
ZEX
Furthermore, by formula of 7' given in (15), we have 7 1 y) tx, holds for any x E X,
for any x, X. Consequently, the following
zz
pe(x) = Σ (a)22)(((z)))
Σ
Po(2)
2d = 7 (x),
1
2d
ZEX
ZEX
meaning that the forward dynamic (X ()eeoo,Ty converges geometrically fast to n
C. Implementation of DMPMs
C.1. Alternative ideal backward simulation
Besides the simulation of the backward process provided in Section 1.3, we can also use the following procedure to produce the time-reversal dynamic.
16

---

Discrete Markov Probabilistic Models
The second procedure to sample (X, () is to consider a sample Xo from Jry, and a sequence of i.i.d. random variables distributed according to the exponential distribution with parameter 1, { i N, & E (l....,d d J. we can define the jump times (Ei) of the backward process and its transition by induction setting To 0. Given (T,, XT,), we define the next jump time as TV = T: AT; i+1. where AT/+1 = inf > 0 So A r:))dr > E Then, set T++1 = T where l = arg min (e......d)) T/41 and X, = Xy. for t E (T, T.+1 A Ty), and finally T1+1 < Ty, T(+s = X for & (1.....d} d).
C.2. Perfect backward approximation
We provide here the pseudo-code of backward approximation sampling in continuous time scheme:
Algorithm DMPMs Algorithm (Continuous time scheme)
Input: time horizon T'y > 1 large enough, a prescribed jump rate X, approximate score function
Backward process:
Set To = 0 and initialize X. ma
t-0
while T; < T do
Draw E, Exp(1)
Solve AT;+1 = it 00: J0 Nrt (Xn, > Esj, with (x"(x) A AE 8 (x))
Set 1:+1 = T; AT;+1
if T; < < min(Ti-1. Ty) then
Set X. x
end if
if Ti+1 < T then
Draw 4 {I....,d} ~ Cate((A(1- - S.. - (x:))/2f (I
Set X XT.I= = (p(l))(x))) (X))
end if
t ++1
end while Output: X,,
C.3. Discrete denoiser and score reparameterizzttoon
Discrete-denoserr structure.
Recall from Proposition 1.1 that each score component admit the following conditional expectation:
<((x) E -,,
(40)
where
(( X (1) 1 aT,-1
2ar,-t
x T,-t 4aT, (x
X(j3
(41)
az
for E [0,Ty), x E X and f d.
Remark that
4
(X T,-1 - -
20T,- -t
E (X XT,
(42)
1 OT,
1-0 2
17

---

Discrete Markov Probabilistic Models
Thus introduce the function dy defined
21 d 2
(X X -
(43)
which can be further rewritten
x1) 2
d,(x) E
X Ty-t
X Ty Tt- =
1
X 14
rj
* x
X
+ xx X (T-1=
In some sense, this the discrete version of the continuous denoiser TE. X nl X approximated by classical diffusion models (Song et al., 2021), as obtained from the score by Tweedie's formula. Thus we call (x) the discrete denoiser.
Score reparameteriiztion. Based on the previous derivations, each score component (2) can be written as function of d;:
200,- -0
(x)
(44)
1 OCTy-t -
1 1-07, 2 QT
So we can reparameterize our score models of as
200,-1
400,,- , 0. (1)((x)
(x) 1 -T,
(45)
1 - 0 T
where (x) aims to approximate (ar).
C.4. Objective functions derived from the discrete denoiser structure
Inspired by the previous derivations, modify existing Σ₁,2 loss function replace by denoising loss equivalent. We introduce a cross-entropy loss, and finally propose a scaling of the loss functions, based on the average output magnitude of the discrete denoiser, thus helping with the learning, and improving synergies between loss elements.
Score-matching objective L1,,. We rewrite the objective function Σ1 to fit the discrete denoiser, considered as a conditional expectation:
0 + 1" (f)) (0)= = [lld,, -xx, Xx - KD|p]
cilen L
(46)
where d is the element clement-wise wise product.
Cross-entropy objective Leg. Instead of the Ln loss suggested by the conditional expectation structure, we can consider
cross-entropy loss fit our model to the correct distribution: classical derivations from the conditional log- ligllikeddood where
d
E log
0.f (X T, [x()
(xT, 1 de. (xr,-t)
if If + Xo
Pt 9.8 (xTy-1/250)
(47)
else
lead to the following cross entropy loss:
ECe(0) = I/" Th
(O)dt
(48)
18

---

Discrete Markov Probabilistic Models
where
d Y log de (X + x1) log (1- di (X (Z
(0) - E
Y
else
Further improvements. To address training efficiency, we inspect the average magnitude of the loss across the dataset, at each timestep. Indeed, the average value of el
X (1) = r
de [
WT
P 6 * X
{
= E
a1- oT, aT,-
(49)
given by the formulas for the transition kernels of the forward process. We can see that the value of w, is close for small values of t, which stalls the learning process. Empirically, find that dividing the integrand of either loss terms Lt. or Scn by wi yields improvements. As result, we modify the losses counterbalance their diminishing magnitude across
timesteps: 2111
2 ECC
SLicE and define the associated losses we
an
Tt
Qw (B = = -
Ty 2
L (0)
Eu (0)a,
(.,CE(0)d)
(50)
Comparing 21,2, ECE, -1,2 CC.-
In Figure 4, we plot the average loss timestep, for trained model on MNIST (following the specifications given in Appendix D.2)). It shows that, on average, the Σr. loss effectively becomes scaled variant of the cross-entropy objective, which is reflected similar performance results. This corroborates our derivation that L2 acts as an effective lower bound to the log-likelihood. This also supports its relevancy with respect to the underlying structure this generative model. must be noted that both losses still benefit from positive synergies when used together.
Importantly, dividing by w, (1 22 particularly helps at smaller timesteps, and keeps the loss values at the same magnitude across timesteps, enhancing training dynamics. This is illustrated in Figure 5, where scaling the losses with the scale factor consistently yields improvements.
10
101
Monssas Saassas
4,435,0
Baaznae Massas
30
10
ICe
Figure 5. FID4, on MNIST, for models trained with L and 2 losses, evaluated using 200 reverse steps with the denoise-renoise sampler. Scaling with yields consistent improvements, with the best loss configuration G 21/3,1/3.1 involving all the methodologi- cal improvements we discussed.
Figure 4. Comparison of E,,; EC,, Lia; Sie average losses over timesteps. The two losses become scaled version one another only when averaged over data, but otherwise benefit from positive synergies when mixed together.
19

---

Discrete Markov Probabilistic Models
Final objective functions. We choose linear combination of the previous loss objectives, weighted by positive coefficients w 22,; w.
L = 212 + w2 + waLCE
(51)
and, if we choose their version weighted by 1/w;:
- = 0 + w2 + w3lCE
(52)
Algorithm 2 Training Algorithm for DMPM (Reparameterized Score)
Require:
Dataset D of samples X {0, 13d.
Time horizon T and rate À > 0:
Parameterized discrete denoiser model {at (d..t (x) E 0)
Derived score function of. Tt
-
4ar, - T-
(score reparameterization (24));
Define a₁ as in (13), fr as in (19);
Loss coefficients 11, 22, w3 > 0;
1: while optimization has not converged do
2: Sample batch (X:) from D.
3: Draw .I..... tB ~ (ni Ty))
4: Forward sampling: fast simulation via Prjo = (ph)) )dd
5: i = to do
6:
X - X;
7: Pry-t, (1 (1-ar,-1)/2
Compute X -t, by flipping each bit of X aoo independently with probability Pr,-t 9: if Scalinn losses with average de magnitude then
8:
10: Wi + (1 0r, (1)
11: else
12:
wi 1
end if
14:
end for
(0)
+ 1/2 B 1
(i) (XIT,,t.
-x,o)d -X,TT----1
x0)l
B Wi
16:
(f) t
Bd
1 EB 1 Et=
Li=l mi
12 log A. (X -1:) + - 1x logg(1 - di, (X
17:
(0) + ト Σ t=
sT,-,, (Z + ( (X.,) 1) log(1 - 0. - -1 (X (..))
8.
18: (0) + 1
-12
Oden
+ 22 L. + W3 LeE
19: Perform a gradient step on Sm (0) w.r.t. 0.
20: end while
Return the final parameter 8'
C.5. Generative process and sampling procedures
Once we obtain our neural network dx approximating de, we use to produce fresh samples that closely mimic the observed data. To do so, we first introduce DMPM sampler based on the true reverse process. We then propose a slight modification, leveraging the distribution on indices available at each step, by flipping multiple bits instead of just one, using flip-schedule. Finally, we derive a denoise-renoise sampler, solely based the discrete denoiser structure of the problem, as inspired by similar lines of work in conitnuous diffusion.
DMPM sampler. A first sampling procedure is given in Algorithm 3. It is designed to be as close as possible to the true backward process, while enabling efficient parallelization when implemented. It consists in a the functions of interest, parameterized by the choice of a time discretization grid 0 = to < t1 < ... < tx = Ty, which we call time-schedule.
of
20

---

Discrete Markov Probabilistic Models
In Table 2, we give the different time-schedules we experiment with. We draw inspiration from numerous lines of work continuous and discrete diffusion (Shi al., 2024; Karras et al., 2022), in which these are common choices.
DMPM sampler with flip-schedule In Algorithm 4, we further take advantage of the specific structure of our backward process, by leveraging the distribution over indices given by the learned score model at each timestep t. Instead of flipping single bit per timestep 4s, we flip a total of Mr, bits sampled without replacements from the given distribution. We call the sequence { {M, JOGETT, the flip-schedule. When a time-schedule {tx 14 has been chosen, we also call the corresponding R==1 a scheuue.
discrete sequence (Mr }
In Table 3, we give the two flip-sheedules we explore in this paper. The choice for the linear schedule is inspired from the philosophy of the masking schedule introduced in the context of masked diffusion by Shi et al. (2024).
Time-schedule
Value of
Flip-schedule
Value of M,
Linear
Ty K
Constant
M
Quadratic
Ty R
Linear
M 7
Cosine
T cos
k/Kim
Table 3. Different flip schedules (Me)o used in our experi- ments. both schedules, is constant to fixed and controls the total number of bits flipped during generation.
Table Different time schedules (tx )== used our experiments. Ty denotes the final time, and K is the number of reverse steps.
Denoise-renoise sampler. In Algorithm 5, introduce the following denoise/renoise cycle, interpreting the model output de as the probability that each bit should be flipped at timestep to reach timestep 0. After doing full denoise pass (from time T + 0), we noise the sample with the transition kernel of the forward process (from time 0 + Ty A). Then we can do another denoise pass from (Ty- A) + 0, etc.
Algorithm 3 Backward sampling of DMPM with piccewise-constant score
Require: Time horizon y > 0 and rate À 0;
K > 0 number of reverse steps and time-schedule 0 = tg < t < < <tk = Ty;
Flip-schedule, i.e,, sequence of positive integers (M₁, )
Discrete denoiser model d8;
20r,, 4a0, 4 a
Derived score function of = 1 T-
(score reparameterization (24));
Define ag in (13);
1: X ~ Unif(O, 1))
2: ~ E(1)
3: A 0
4: for k 0 K do 0.1
5:
Ne. + x
8iz
6:
Atr + t++1 t
7:
A A+ A + dea Ale
8:
A E then
8t ~ Cate {
(1
Stc
0.0
9:
dex
1-11
S +
10:
li
11:
A+0 0
12:
E E(1
end if
X
Xi
14:
1x+1
15:
end for
Output:
X x
21

---

Discrete Markov Probabilistic Models
Algorithm 4 Backward sampling of DMPM with piccewise-constant score and flip-schedule
Require: Time horizon T' > 0 and rate 0;
K > 0 number of reverse steps and snne-schedule 0 bn < < < tk = Ty; Flip-schedule, Le., sequence of positive integers (Mr, k=
Discrete denoiser model dB;
200,,
4 : 1 1-
Derived score function sf 1taI,
(score reparameterization (24));
Define a as in (13);
1: 0 (n, 1)6d
2: E E(1)
3: A
4: for = 0to K 1 do
0.f) de f X >E
5:
6:
Atk + 1++1 - tx
7:
A+ A de, Ale
8:
A E then
(()(1-)
sbr)) )a dre emm
9:
[9 Eisl
Hypergeometric
Men)
10:
for 1 to Mr, do X t- x Ex
11:
12:
end for
13:
A+0
E E(1
15:
end if
X
X
16:
1x+1
12
end for
Output: xT,
Algorithm 5 Denoise -Nise Cycling with Discrete Denoiser Model
Require: Time horizon T3 > 0 and rate À > 0;
> 0 number reverse steps and time-schedule 0 = to < t1 < < tk = Tyi
Discrete denoiser model d":
1: X ~ Un, 1d (initial sample in (0, 1]d)
2: for = 0 to K- do
3: Denoise phase:
4: diz + di (xx)
5: Compute r, by flipping each component I of Xg, with probability di
6: Noise phase:
Sample X f Pr, Pry-teis 1 (1 ). as in Algorithm
8: end for
Output: X T
22

---

Discrete Markov Probabilistic Models
D. Experiments
All experiments are conducted using PyTorch. All the training and experiments are conducted on four NVIDIA RTX8000
GPU.
We the parameterization introduced in (45):
201,-1 40XT, 1 (x)
(1)
(x) 1+ - 1 01,
(53)
where the neural network ( aims to approximate d((x) = -P + x² X x x). Since the output of the neural
network is di (z) E (0, 1)", we add a sigmoid activation function at the last layer.
We consider various loss configurations Lw dn as introduced (26), (52), with choices of coefficients (#1, W22 Wa) normalized in the 2-simplex 4₂ C R3, We test all 2 combination (#2 = 1), as the latter only acts as entropic regularization and does not perform well by itself. This lets us study the synergies between the different loss terms.
possible non-emply combinations, minus the single &e loss
D.1. Small dimension data
We first conduct experiments on a discrete data distribution p supported on {0,1)* Each component of x (Xi) ~ p independently distributed Bernoulli distribution with parameter pı:
d
(ax)
II p:(aa),
(54)
where the map Pt forms sawtooth-like pattern, oscillating linearly between 0.05 and 0.95, can be seen in Figure 6.
Figure 6. Sawtooth pattern used to define + p.. plotted with d 16. Values oscillate linearly from 0.05 to 0.95, and back.
For training, we use 20 000 datapoints resampled at each epoch, and a batch size of 1024. We train each model for 300 epochs, using Adam W with a learning rate of 1e-3. We employ network composed of multiple MLP blocks: residual blocks, each consisting of two feed ferdard layers of width 256; layer normalization and SiLU activations each block; a feed-forward embedding for the timesteps. mapping R a hidden dimension of 256, whose output is then injected into each residual block by an additional MLP of dimension 256 256.
For evaluation, estimate each distribution with 20,000 samples, and draw 1000 vectors uniformly on the simplex Ad to compute our SWD metric (see Appendix D.3).
D.2. Image data
We work on the binarized MNIST dataset, which we scale from 28 28 to 32 x 32 in order to fit in the U-Net architecture. We set the pixel value to 0 if its intensity is below 0.5, and to 1 otherwise.
We compare DMPM to MD4 (masked diffusion, as in Shi et al. (2024)) and DFM (discrete flow matching, as in Gat et al. (2024)). We reimplement MD4 with the cosine schedule and the algorithms given in Appendix F of Shi et al. (2024). We implement DFM based on the Pytorch implementation ht / thub. com/gle- wewlleleeee..... wewlierrddscreeeeeeeeeeeeeeeeeee fm,
23

---

Discrete Markov Probabilistic Models
and we use corrector sampling for better results.
For DMPM, are using the cosine time-schedule and time horizon T'- = 3. For both MD4 and DFM, we set the mask value to the integer 2.
To establish a fair comparison, we use the same network model for every method. We use a U-Net following the implemen- tation of (Nichol & Dhariwal, 2021) available in https: htap::://githhae //gthub...//////g/// coon//ppenaiimmpprreeeee di diffusion. We dimension the network as follows.
The first layer is an embedding layer of output dimension 32 and input dimension dinpur. where dinpot 2 for DMPM (input values are either 0 and 1) and dipp for MD4 and DFM (imput values are either 0, 1 or the mask value 2).
We set the hidden layers to [128, 256, 256, 256), fix the number of residual blocks to 2 at each level, and add self-attention block at resolution 16 x 16, using 4 heads. We use an exponential moving average with rate of 0.99. We use the silu activation function at every layer. Timestep is fed to the model through the Transformer sinusoidal position embedding.
For DMPM and MD4, we set the number of output channels to and add a sigmoid activation at the last layer. For DFM, we set the output channels 3 and apply softmax channel-wise.
The optimizer is AdamW with learning rate 5c-4. We use the StepLR scheduler which scales the learning rate by y .99 every 400 steps. We train on MNIST for 120 000 steps with batch size 256. A single training run on MNIST takes approximately 6 hours per GPU, and requires about 6-12GB of VRAM for our settings.
To assess the quality of our generative models, we compute our metrics between 4 000 real images and 4 4000 generated images. Generating 000 images with 000 reverse steps takes approximately hours on one GPU.
D.3. Metrics
For oww-dimesioonal data, we use a custom sliced Wasserstein metric. For image data, in addition to the classical FID metric, we use a FPC summary score, based on the density and coverage metrics.
EPC. as summary metric of density-coverage The density and coverage metrics are introduced in the setting of generative models by (Naeem et al., 2020). They assess the overlap of sample distributions using local geometric structures. Density measures how much the generated distribution is contained in the original data distribution (measuring quality), and coverage measures how much of the original data distribution is covered by the generated distribution (diversity).
These metrics are improvements of the precision and recall metrics for generative models (Kynkäääniemi et al., 2019). They offer different measures to characterize the performance of generative models. For instance they can decorrelate the negative effect of mode collapse from the negative effect of noisy/blurry generations, each of them decreasing respectively coverage and density, and have been of importance in recent studies, e.g., in heavy-tailed generative modeling (Shariatian et al., 2024; Yoon et al., 2023).
We consider a single summary FDC score, which we define as the harmonic mean of these two values:
FPC = 2- density coverage
(55)
density + coverage
Sliced Wasserstein metric SWD.
Since the state space of our dataset over (0, 1]d is of size 24, we cannot work with histogram-based metrics, which would require exponentially many samples when d increases.
We address this issue with our sliced Wasserstein metric SWD. This metric is defined between distributions v on {0,1] as:
1]d
/
SWD(H, v) = JA.
W (u (up) du
(56)
where, for E Ag, the pushforward uy is derived from the function
I E {0, 13dd (u, E [0.
(57)
Simple Monte-Carlo averages are used to evaluate the integral with respect to the uniform distribution over the simplex A
24

---

Discrete Markov Probabilistic Models
and we compute the Wasserstein distance between the pushforward measures with the pyemd package (Laszuk, 2017).
E. Additional results
In this section, we give grid images of generated samples for DMPM models trained on binarized MNIST, with the loss
2 13/3///3,1/3
4
2
4
8
7
5
3
0
4
4
5
4
5
9
7
1
C
2
7
/
4
O
1
&
S
2
4
2
3
O
5
2
1
4
O
4
8
8
2
9
3
9
8
7
5
/
1
5
3
4
4
9
9
3
7
9
8
8
I
0
2
5
3
2
7
7
S
1
6
7
0
5
S
8
9
4
2
$
6
Figure 7. Default DMPM sampler, 25 reverse steps, cosine time- schedule, linear flip-schedule dimensioned for 1000 total bit flips.
Figure 8. Denoise-renoise sampler, 200 reverse steps, cosine time- schedule.
25

---

Discrete Markov Probabilistic Models
F. Convergence of DMPMs
The proof of DMPMs' convergence requires understanding the backward dynamic under the canonical process point view equivalent the transition matrix point of view we provided in Section 1, We provide first some essential preliminaries on Poisson measures and the corresponding Itô's formula.
F.I. Some basic facts on stochastic calculus for CTMCs
F.1.1, POINT PROCESSES AND POISSON POINT PROCESSES
Let (Y, be measurable space. Let Al be the set of non-negative (possibly infinite) integer-valued measures on (Y,
Let My be the smallest a-field on My with respect which the mappings μ E My μBB) E N [U{o))) Y measurable.
Definition F.1 (Poisson random measure). An (-yy, My) random variable I (i.e., mapping μ p S + My defined on a probability space FP) which M/My-rarsrrr is called a Poisson random measure if
for each B E y. (B) is Poisson distributed; i.e., P( n) A (B)" (B))/) for any n E N where (B) = (B)] B E V. Note that if ( = 00, we understand that (B) 3 a.s.
If B1, Bg. Bn E y are disjoint, then (BB1), (B2)....... (B()),,...... are mutually independent.
Remark that it is easy show that y is non-negative measure (Y,)) that uniquely determines the distribution of μ by the monotone class theorem; see (Ikeda & Watanabe, 2014, Chapter Section 9). It is called the mean measure the intensity measure of the Poisson random measure μ..
Let (X, X) be a measurable space. We define a point function p on X by mapping p Dp - X, where its domain Dp is a countable subset of (0, oo). p defines a non-negative (possibly infinite) integer- measure N, on (0, oo) x X endowed with the product a-field (((0, oc)) X by
N₂ ((0, x U) = Card E E D, 8 L
1>0, Uex.
point process is obtained by randomizing the notion of point functions. Let 11x be the set of point functions with values in and ((Ixx) be the smallest o-field on IIx with respect which the mappings p + N0, t] x U), > 0,U E X, are measurable.
Definition F.2 (Point process). point process p on X is a (ITx. ((TT)((())alllill vaaledd random variable, that is, a mapping p:Ω > IIx defined on probability space (S2, F,,))) which is F/I((Ix) (/[[[Ix)-maauurabll measurable.
A point process p is called stationary if for every 0, p and 0,p have the same probability law, where 0,p is defined by Da.p {s (0, oc) s +tt Dp} and (0.p) (s) p(s + t).
Definition F.3 (Poisson point process). point process p called Poisson if Np a Poisson random measure on (0, oo) X.
Poisson point process is stationary if and only its intensity measure (d(ddd)) = B[N, (dtdzz) is of the form
(d(ddrr) dtu(dx)
for measure (X, X.).
1.1.2. STOCHASTIC INTEGRAL WITH RESPECT TO POINT PROCESS
Here, we review the construction and definition of stochastic integral with respect to Point Processes for completeness; see (Ikeda & Watanabe, 2014, Chapter II, Section 3).
Let (9, (Fi)ezo IP) be a filtered probability space, where P defined on the smallest o-algebra containing all F,, > and (Fi)ez0 satisfies the usual conditions (i.e., right-continuity and completeness). A point process p= = (p(t)) on X defined on Ω is called (Fr) (FFdaadaptedd if for every > 0 and U X, N₂ (t, U) = Exer, lu(p(s)) is Fe-measurable, p is called o-finite if there exist U, E Xnn = 1, 2... such that U, U, = X and EiN, U,)]] < oo for all > and n = 1,2, For given (Fe) addaped,, a-finite point process p. let r = {U E X: Et, U)] <o for all 0). If E Tp. then
26

---

Discrete Markov Probabilistic Models
E 00) U) is an adapted, integrable increasing process and hence there exists natural integrable increasing process (p,t, Definition F,4. An aFap-ade point process p on F.,, is said to be of the class (QL) (quasi left-continuous) (w.r.t (Fi)) it is o-finite and there exists Np such that
(tt, U) such that Npp: Wp:t. E (0, + Npt(t, U) Nt,(t, U) (t, U) is a martingale.
1. for e Tp, E (0, o0) + (t, U) is a continuous -adapedd increasing process,
2. for each t 00) and 22, U (t. U) is o-finite measure (X, 2'),
3. for U e Pp.t oo) + Np U) = Np U) - (t, f U) is an (Fr)-martingale.
The random measure Np called the compensator of the point process (or Np).
Definition F.5. A point process p is called an -Piissonsoon point process if it is an (Fi)addapedd, o-finite Poisson point process such that (t + h, U) (4, U) )>>uuxxx is independent of F, for any E [0, oo).
(4,
An (Fis-Poisson point process is of class (QL) if and only if ++ Et,,(t, U)] is continuous for U E I pp in this case, the compensator Np is given by Np(t, U) (t, U)].
Theorem F.6. Let be point process of class (QL) W.E. (Fi) on some state space (X, X) such that its compensator Np (d(dd) is a non-random o-finite measure on [0, co) x X. Then is an (Fi)-Poisson point process. If. in particular, Np (dtdz)= = dtu(dx) where n(dz) is non-random o-finite measure X, p is stationary (Fi)-Poisson point process with as its characteristic measure.
We now going to discuss stochastic integrals w.r.t. given point process of the class (QL). For this it is convenient to generalize the notion of predictable processes.
Definition E.7 (Predictable functions). A real function f(t, x, w) defined on [0, oo) Qs called (Fr)-predictable the mapping (t, x. w)) > (t,, x, w) is S S/B((R)-meauurall measurable where S is the smallest a r-field on [0, oo) x X x Ω w.r.t which all y having the following properties are measurable:
1. for each & > 0, (ar, w) - ((,, xr w) X x Fe-measurable;
2. for each (x, t (o) + g(t, x,w) is left continuous.
We introduce the following classes
Pp- f(t,2,w); is (F,) preddctbae and for each f. > 0, L. / [(8, ((ss,,,))) < oo ass
p+
(58)
F2 f(t,2,w); is (Fi) preddicaae and for each t 0, E S'' 1.
00
Theorem F88 (Stochastic integral). For f E Fp. the stochastic integral t Sx f x, x. (d(dddr) is well-defined a.s. and equals the absolutely convergent sum,
Sta [, ) N
Σ ((x,
sET,DED,
We then denote the stochastic integral w.n.t. No as
h ++ [ -N = ((² [ f(5, (NN f/' / f(s, x, (dsddr))
and the process 1 + 1e+ 18,,,2 -) (pdsdar) is an (Fi)-local martingale.
27

---

Discrete Markov Probabilistic Models
Now let S E pp. the stochastic integral Se Jx [8, N (ddsdx) satisfies
1o [ 11(,, )) (1 =B Do J [1, (.),, -))ppddd
E
This implies, in particular, that Fo C Fp. Then the stochastic integral t ++ Sot [(5, -N with f E F. is an (Fi) martingale.
F.1.3. ITô'S FORMULA FOR POINT PROCESS
Itô's formula is one the most important tools in the study of mami-martingalss provides with the differential-imeee -intraal calculus for sample functions stochastic processes.
Let (9, 10 PP) be a filtered probability space given as above and let (X, X') be measurable space. Define d- dimensional semi-martingale X, = (X) x?....,X X adapted to (Fi)ezo, taking values in X by
nt [ 2, = + Mi Ai ///
L// (x
i 1,2,...,.4 d, where
each (Mi) E MM2 with
M {(Mo))zo; (M))zo is locally square integrable (Fi)-martingale, Mo = a.s. ; +> X, is continuous a.s.)
each (A))e2 is continuous (F,) -ddapted process satisfying A = 0 and for almost every E S2 the sample path
+ (w) has bounded variation on each finite interval;
p is point process of the class (QL) w.r.t. (FF) on some state such that f'(t, x, w)) (t, for any (,,,,, (I......d] dj2 [0, 20) X Qi furthermore, we assume that a constant C exists such that
x1, < for all (1,1,,,)) (1...... d) x (0, x Ω
each X/ is an Fo-measurable random variable.
Denote also f= "f' (d) and (g'....,
Theorem E.9 (Itô's formula, (Ikeda Watanabe, 2014, Chapter II, Section 5)). Let be a function of class C2 on Rd and let (X)) be a d-dimensional manimmartingale given above. Then the stochastic process (F(X)))zo is also semi-marlingale w.r.t. (Fi)azo and the following formula holds:
d OF
OF Σ /
F(X.) - F(Xo)
Σ
(X
)dM +
(X.)dA
dz;
Ox,
1=1
OF
+
(X,)d MM).
2
dx,0z,
4-=1
/ (F(X,- + f(8,2,)) F(X,-)) (dsddr)
+
/ (F(X,- + -(s,,x))) - F(X,-)), ()x,)))pppdsda (dsdr)
+
1- ( F(X. + -gx,2.))2.))) F(X.)
OF
+
Σ
g"t (s, (X.)
No (dsdd))).
dr
1=1
28

---

Discrete Markov Probabilistic Models
Corollary F.10 (Itō's isometry). Let No Np and No given as above. Then the following holds for real-valued functions
f PL
[V." /
-B [T [ ())
=B
Proof of Corollary F.10. Denote the process (X,) by
X, = Lod J (l x,=
and apply Itô's formula (see Theorem E.9) for function F(x) = x², we get that
++ 1/e [ (Xx. + ((, - -x;- (dsdz)
x² x3
1/" / ((x,+ -x 2x,,(,, N (p(dsdz), for > 0.
Taking expectations on both sides and using the martingale property of the stochastic integral with respect Np implies that
X - - = E
P(s
Plugging the formula of X, into the above and noting that Xo = 0 yields the desired equation,
[1% J f(s, f(s,2..) ) = [ / (ws,
and concludes the proof.
F.1.4. APPLICATION TO CTMCs
Let (X, X)) be measurable space with X C Rd and let (Xe)eεto,r;1 be CTMC on X associated with the jump rate function :: [y] + R2 and the kernel & 2x) determining the probability of jumping into æ E X at time t, given jump represents the rate of time E (0, Ty}. The CTMC (Xr)sejozzy) defines Poisson
occurs from a current state X,_. The generator qı is defined by (X,,,, x) (X jumping from the current state X,_ the new state point process Px- (Px(t))eeooT)) (X, X), where
Px Dpx (0,Tg)- (x = X2, E Dpx
with Dpx is the set of jump times of (Xt)tEjo,Ty)- We observe that px describes the new state after jumping at time t (0, Ty] and constructs a corresponding Poisson random measure Npx (dtdæ) on (0, Ty] by
Npx ((0, t] x U) = Card {s E Dpx :s (xtp))))
Σ
((,x,)((0, U) for (0,Ty), UEx,
sEDpx
that counts the total jumps into U X' occurring during (0,4). Then the random compensator ñi of Npx is given by
n (dtdr) Σ -9(X1 y) & (dz)
yEX
since the corresponding compensated measure
29

---

Discrete Markov Probabilistic Models
Ng (dtdæ) = Npx (didx) n (dtdd)
is an (Fi) (Fi)-martingale, where (Fr)ce)o,Ty) denotes the right-continuous and complete natural filtration generated by the process (e)))e(o.Ty) Indeed, we can show the martingale property of NNp as follows. For any function f E Fpx where the class Fbx is given in (58), define the following stochastic integrals:
f / 1(8,2,,)) (ds(d)))) E s(8..xx(5))),,
1+
0c sEPxx
J / f(,,,, (dsdr) 1/0
/+
1 [(8 )Nxx (dsdx) - S / f(8, I,, -ja"
Then for 0 & <<<tt & TG. we have
1+ [ f(2, ->xxx (dzdz) Fs =
Σ f(z,
S<IEE
BED
r(X:-) U.J. f(2,0, ((,,,))((x-) ((XX))))((0-)))) a(xx_, I x ta Fg
E
J. J [2,,0 (X x)xx, undoda Fa
E
E J. [ f(2,2, )) Fg
meaning that n indeed the compensator of the Poisson random measure Npx With those notations in hand, we can decompose the CTMC (X1)te as
X, No Σ (X, 1X,-x x,-)= No f/¹ (05 Xx- Xxx) (dsdæ), for / [0, Tp)
O<S!!
xEDpx
under the assumption [(s, x, : x We- E Fpx. where Fpx defined in (58). Applying ItO's formula to this process, for any function in (X))). we get that
F(X.) - 1"t ( [F((X= - ---)-F(2 F(Xx-)) Npx (dsdx)
++
1a² ( (F(a)- (o(())F(Xx-))) Npx (dsdr)
prt
Expressing the Poisson random measure Npx Nop + h and plugging it into the formula above yield
F(X)) - F(Xo) ((X)) - ( F) (1C -fa² 1+ ((F(2)
-
F(X.-)) Aig (dsdæ).
other words, the process
F(Xi) -((x) 1/' (F(x) 1x e q(X,, dr)dds
(E(0,Ty]
30

---

Discrete Markov Probabilistic Models
(Fi)-local martingale the compensated measure Ng was shown be an (Fr)-martingale in the previous computation. It follows that for the CTMC (Xt)1e(o,T)) with generator q, Itô's formula asserts that the process
(((x)) F(Xo) - S: 9F((x=)dss) rE(o,Ty)
an (Fr)-local martingale for any function F (X)... This result aligns with Dynkin's formula.
E.2. Canonical process point of view
We now want to give a description of the time reversal process as a controlled process like in the continuous setting in Conforti et al. (2025). To this purpose, we consider the following canonical setting. Let Dr, = D[ Ty]; X) be the canonical space of all cådlàg (right-continuous with left limits) paths from [y, to X = {0, 1)d, and let (Xx)cej0.ry) be the canonical process defined by
X, (w) wi: for t E Tyl. (W)))ε(o.T)) E Dry
We endow this space with the canonical filtration, that is, the right-continuous and complete augmentation of the filtration generated by (X))) denoted by (Fr)ee(o.T))
For any P E P(TTr, we denote by E& the corresponding expectation. For any E [0, Ty), we denote by Pr, the distribution of X, under IP.
As usual convention, simply denote the the random variable xw) xt, for predictable process U : Dr, x [0, X + RR.
For any random generator q Dr,, x Ty] x x - IR and predictable process U DT, x [0,Ty] x + R, the new random generator Uqq Dr, x [0, [ x X2 + R is defined as (U,)(w, t, x) == U(w, t. (W,)),,,t,,,.., y) for x #
For convenience, we denote by F(X) the set of functions from X IR.
We now follow the approach for time reversal used in Léonard (2012) characterize the distribution of (X:) the solution of martingale problem.
Definition F.11 (Martingale problem). Let q: Dr, [0, Ty] X be non-homogeneous predictable random generator. We say that P (Dr,,, ) solves the Martingale problem (P with initial condition Po. and write P MM)g),, if under P, X, has distribution μo and the process
(((X)) ((xo) q(s)s(xx.))d
rE(o,Ty)
is an (Fi) -local martingale for any function f E IFXX), where we denote (()) Eyex x,,,t,,,,)
Note that by Itô's formula and Appendix F.1.4, if under P. (Xt) (X()uejo,r;) is CTMC with generator q, then P solves MP(g). Recall that for the forward process under consideration, the generator / is defined as
X
if y = (x (z) for some l E {l....,d}
(x,1)=
Ad if y = x, 0 otherwise
(59)
where p(() : X - X is the function which flips the ê-th component for E (1....,d d). Note that by (15), 7dh = Uni an invariant distribution for the CTMC with generator 7.e., fact the transition density 7, is reversible with respect to ad for any E [0, Ty} using (15), i.e. for any 2.y E X and t E [0,Ty].
i.e., for any measurable function f, Exex 7. (x) =
Exex (x)
(x) = A²) 7e(,,
As result, we get that for any th ... bn & Ty. under Rhe where Ah denoted the distribution of the CTMC with
31

---

Discrete Markov Probabilistic Models
generator 7/ started stationarity 7", (X Xt,)) has the same distribution (Xi,-t1 -t. and therefore the reference path measure R is reversible, i.e., R R, where R is the distribution of (Xr,-t))e(o.7) under R.
Following Appendix F.1.4, for any IP E P(Drr, such that (X,)) is CTMC with generator q: [0, Ty) x X2 R under IP, we denote by px the point process and by Nx the Poisson random measure associated with (X)))e
We also define for any (w)) E Dry
((W))))E)) didx) = (1, da)dd, n1(1, = Σ
Tw ())
(60)
BEX
By convention, we denote n (Xx)) dtdz) by n (dtdx) which corresponds to the compensator of (X,))eja,T,) under ] CTMC with generator q X² - R. Consequently, the compensated sum of jumps N2 = Nx - n forms a martingale under IP.
P. if under this distribution
F.2.1. GIRSANOV'S THEOREM
As proven Léonard (2012, Theorem 2.6-2.9), the relative entropy of two path measures associated two jump processes can be expressed using the Young function
e(a) == e" a 1. for a E R
Note that the convex conjugate @ equal
e (b) (b + log(b + -1)-b,
-b, b, for b -1,
with the convention 0"(-1) = and g (b) co, for b < -1 We recall that the functions & and g" are respectively equivalent to a² /2 and 12/2 near zero. Finally, we recall the definition of the function
h((a) = e- (a 1), a E R.
Theorem F.12 (Girsanov's theorem). (Léonard, 2012, Theorem 2.6-2.9) Let IP E P(DT,, verifying (t) cc. Then, there exists a unique predictable non-negative process U Br, x [0,
X o0) satisfying the integrability condition
VONAEx ((U((t,,)) x)) - 11)n (dtdæ)
ER
< <0,
(61)
and IP e MP(U where tw,,, = Ulw, t, v) (x, v) for a + y. Moreover, we have that
dF (X.)ee10.r)))
dlP o d
(o)) exp (1OTIIa log (t, (dtdx) 1 Jo.T e(logU (t) (dtdx)
(
=
dR
and the KL divergence reads as
= Ro) Ep V xt)(t,)))n (dtdr) (
The proof of Theorem F.12 is given for completeness and is based on several technical lemmas, which we introduce in the following framework. Let IP E P(Drr,)) such that (X.)e(oorr)) is a CTMC with generator q [o, Tyl x X² - R, ie., Eyex 2(,,,,y) v) = 0 for any (t) [o, Ty] X, and denote px, Nx, n9, n and Nig in previous Section.
Let x R-valued predictable process on Dy, x [0, Ty) x X such that fo.,T,1xx ((xe(w, ( oo, P9-a.s. Define
zz = exp (NoAp Xolw, x) (2 / Joxxx elxa(w, x))n)())
fort e [0,Ty]
(62)
32

---

Discrete Markov Probabilistic Models
Lemma F.13. Let Pa E ((DTTy)) such that (X a CTMC with generator q [0, [y) X² IR. Assume that X R-valued predictable process on IDr, x [0. Ty) x X satisfying the integrability condition
Eps [
e(xa(w, ()) oc.
(63)
10,T,1xx
Then f1o.j xx Xs (2( x is local -m-martingale. Moreover the process (Z) REEoO,Y) defined in (62) a local pl-martingale and a positive superrrrmaaat which satisfies
dz, 7 / (Crrlurt) -1) 1 (dtdx))
Proof of Lemma F.13. By Theorem F.8, the process
M = Junax Xalws x.) x)N2 (dsdx)
local |9-maatingale. Denote Y M₁ - foo.1 Bods with 3, fx e(x, (w, (s, dz). Applying Itô's formula provided in Theorem F.9 for the jump process (Y (EEOTT) and for a function f of class (RR implies
as(r;) = U 10V8 + x)(w,,)) - 1(2))) ((()) xe(w;, x)] n (t, (1, de
+ + 3 + dMf p9.as.
where M, is given by
Mf = - [S(Y + x)( f(?-))] N2 (dsdr)
is local mPr-martingale, since the integrand is R-valued predictable process and No forms martingale under 14, Using this formula for fvy c², obtain
de U (6x% +xi(wxx) -oX7 xn) dx) dt - oxT Bidt + dM,up
Y7- B,dt - ex- Brdt + dM,xp- = dM.ap, 19..a...
This implies 2 et is local p9-martingale and, since Z is positive, we can conclude that 2 is PP-suppemarriingaee thanks to Fatou's lemma. In addition, have
d { (0 - ex (didr) = ex ( [(ox(uu)) -1) (dtdx)
i.e. dZx = 2X_ ((xx(())))) - 1)Ñ2 (dldx) and we conclude the proof of Lemma F.13.
We now define the stopping time for j,j 2 1,
of = inf {
[0,Ty]
S (o) > k or (x, $ [-j.A]]
(64)
For E PP , let us denote po. x P the law under of the process _ which is stopped at the stopping time of: Lemma F.14. Let Pa_ E P(Dr,) such that (X,) )EEooT is a CTMC with generator q : (0, Ty] x X2 + R and let x be a R- R-valued predictable process on TDr, Ty) x X satisfying the integrability condition (63). Let (7,) )ee(o,T,) be
33

---

Discrete Markov Probabilistic Models
defined in (62) and o be defined in (64). For all j. k 1, the process (Z, De(OoTTY) defined Z..² Z, is genuine p1-martingale with X (o,03)Xx and the measure Q3 defined for any measurable function F :D, - R+ by
B ((((() Ep+ Ex=(FF((XXXO PxXXX )
1 ie. O =Z (P9)))
a probability measure on Dr, which satisfies
MP (o.05jeXa).
Proof of Lemma F.14. Fix j, 2 1. We have
2,3 = exp (hannn xtanzg - Snavaxx e(xf)ano)
where x [o.o4]] x predictable since x is predictable and 1 [ooo0]] is left continuous. For simplicity. we drop the subscripts and superscripts and write X = x} and Ze 2," for the rest of the proof. From the definition of af. we obtain that [P9 a.s.,
J edx k, and (w X,) E [-j,k],
k] for any t E [0, [y.
(65)
First, we prove that (Z,) is IP--martingale. From Lemma F.13, (Z,) is local martingale. Therefore, it is enough to show that for & E Tyl.
Ren [29] < 00, for some p > 1
For p 1, we have
2 exp (p/ (D//osxx x.dNx (o
-p -D/ /Poopx e(xx)dnn) <exp (P/ kod(zz)
and
exp (p/ RodiNx
-aanxx e(pxs)dnn) exp (P/oop Zodizz ((K.p.))
for some finite deterministic constant C(k,p,t) 1) < xc. Indeed, P1-a.s., for any [0, [y], it holds that e(pxs) (o(xx) + ls 1) since X & le and p 1. It yields that PP....s., it holds
exp (oon elox.)dn")
exp (hl--)) /
10,1xxx (e(x.) k 1)dn"
(65)
/ fo.1xx 1dna
&
exp
ke + (k + ((--1)
< C(k,p,t) <0.
where the last inequality follows from the formula of na given in (60) and the fact that X is finite. This implies IP9-a.s.
2 < exp (p//oa xodNz < c(k exp
( (r/hunexxaa Radiig
elox.)ano)
(66)
On the other hand, applying Lemma F.13 for px yields that exp (p (pSosxxxxall Ending -o. elwxx)dns) is P4.
34

---

Discrete Markov Probabilistic Models
supermartingale, and get
(P/Oosx X
]
exp ( /p// Xod S e(pxx)drr) ] =1.
Epe
exp
Jo.axxx e(exx)dnf
< Epa
Plugging this estimate into (66) gives
Epp [2] & p(k,p,t) <0, for any / E [0, Ty,
which allow us to conclude that (Zz,) is martingaal (see, e.g., Zitkovic, 2015). Thereby Epa [2,] = Epa [Zo] = 1 for any E [0, Ty] and follows Q is probability measure on Br,-
Now, we show the second claim of Lemma F.14:
Lj E MP (o.o0)))))
Let 7 be finitely valued stopping time which will be specified later, and for any function f f F(X), we denote
F, Σ (f(x)) ((Xx)) f(X.-) -(x-)- f/= ++
-
for t [0,Ty]
05
Recall that by Lemma F.13, the martingale (Zx) satisfies the followings for p9-a.s..
dz, 1 10.03 (1 / [eetters)-1 - 11) (d/dæ).
We have
E
Σ
(fX.) - [( Fo = Boy [Ferr [Fo] Epp [ZArAogFEATTNO - Zo1% Fol
(67)
UE
Let us denote the two-dimensional process (It)eE(0.TT)) (I, (E,)))E((.TT))- where
= F. = J 10.01xx [f(x) ((x, [(X-)]())))] Not (dsdx) + S. [f(z) - (XXx))]"((dsd)))
=:o1 (8,
and
1 -2
-2,- Jaxxx Zo- (etr(u)z) - 1) No (dsdr). =,ā(5,z,05
Let v = (u'. x22) and apply Itô's formula (see Theorem F.9) to the process (I))EEo;Ty) using the function given by the product the coordinates, treating (A/)cE(o.Ty) as a continuous, finite variation process adapted the filtration (Ft).
35

---

Discrete Markov Probabilistic Models
F FenTRoZZaAAn - Fo Epn [inrnay Lerraot F1)
Epn
Maunnaagaa (Th + (' + (s,,,w)) _ 12 (dsdx) Fo
Eps
Jacnnnogin { + + 1 L2 (,, 12 x, w. (dsdz) Fo
+ E2n,
Epa U Voarnnynu Bu (8, wd) Fo
Vornneyya (T2 ()) u w), ni (d(dsx)) Fo
Epa
(as No is ---matinggal))
Epe U (s.2,w) + W/z. - 1) n (dddsz) Fo
where we reduce the stochastic integral w.r.t. Nig as it is a local P9-martingale, since the integrand is RR-valed predictable process and Nº forms a martingale under p9, Since Z, = Z for Lebesgue almost all s E (,tATAOfi (Mozumder, 2009, Proposition 2.1) and n is atomless in time, the calculation follows
JaLnnoejA 2,0' (,) (1 [1 ( -1) i (dsde)) Fo
Epp
- Fooo Fo = Exe
J 2,00 (,, (o
Ess
Fo
(68)
Denote G == Jo.oexxx v (s, (r, (.) n2 (dsdd))) Applying Itō's formula for the process (G,, Z,) analogously argued before, we obtain that
ZINTAO Genrnot -oonot---Gii - Zo
I Jannneeuxx Go- + 0² (3) -G
15p^
G. G,- b/-}
No (dsdx) Fo
J JaLAATACTIAx (G, u² u2 G. - G2 (s,,,, (d(dsde) Fo
+ Epp
f 10.1ATA041XX
+ Epe
Zop (8, (s, Fo
Epn |
2 (s. x, we (o. (dsddr))) Fo
(69)
as the stochastic integral w.r.t. Ng is local -mmmatiingal,, since the integrand is RR-valedd predictable process and N forms martingale under 19, Combining (67), (68) and (69) implies
36

---

Discrete Markov Probabilistic Models
Bay
E DEGEIAT
-Rapp
Gentnoz Genznay Fo)
(since Go = 0)
-Ret
[Gent|Fo]
Veammia (f(x) - f(x, (o-))//( Fo
BBy
Eey S (f(x) xxx qe 9e(x dx) Fo
Recall that the random generator c²q IT,, [0, X2 + RR defined by (,,,,, := cl((usii))) g(u, t, x. y)
(xolwa))(tta x2, y) for x, since the generator q under consideration is deterministic. Denote by no the corresponding jump kernel for w (wr))elo.Ty) DT, and (t,x) E [0, Ty} X.
e (w, dtdx) == u *x (o)q)(4, t, w, dz)dt
-. ko xo ( qe(wi_, dr)dt,
then the previous equation rewrites
- ((x,)- ( Fo
Bo² ((X)) = Bot
Egg I (d) Fo
Choosing such that the above terms meaningful, conclude that Qf MP q) and finish the proof.
Proof of Theorem F.12. This proof is adaptation of Theorem 2.6 in Léonard (2012) based on technical lemmas provided above applying on the reference measure R E MP( 77) defined the beginning of Section F. Consider |I-Il defined as
[ e(o/a)dn
l inf a 1>>0:
Ee
<1
for any Sg. where S, is the Orlicz space defined by
S Φ: Dr, [0,Ty] X R measurable s.t. Ee U e(bl)))dn 7
< <0, for any b b> )
It is well-known that it is norm called the Luxemburg norm of Sp. Furthermore, for any x E Sg, by Theorem F88, the process
Mp f Jaxxx xa(w, Nx (dsdx)
is local R-martingale. Then, define the stochastic processes (Y): 7 M.C.C - S 8x. 7 ds with 3x-7 = fx ((xx.w,x))nn (s, dr), and zx.7 7 vr By Lemma F.13, the process 2
)IE and (Z.. )>eeo.Ty) YX.
37

---

Discrete Markov Probabilistic Models
R- -isuuemaartingll,, thus 0 < E
<
1.
For E P(DT,) such that KL(P| R2)
oc. the Varaahn variational formulation of the KL implies that
KL(PIR)) sup { udlP - log / eeadt
e measurable and such that / de'ath < co).
(70)
For any X E Sg. choosing YX, 7 and noting that log T MM,"" log 1 = 0, derive
Nazpae xelw, (dtdx)
Ex
x))n x))
KI.(P)R).
Therefore, for any X Se.
Ep VOTTI
7 xdNx
x
KL
/p.T.Jix exx)dn
(71)
For any function gg. taking x = 0/ll@le in (71) implies that for any & E Sgz
Ep U N
[KL(P))) 1lllole.
(72)
Consider now the sub-space H C Sg.
D e(blø))dm 7
H f0: (o:Dr x [0,Ty] x X IR predictable and bounded s.t. Ep
<o, for any b 20
Since any @ H satisfies (63), Lemma F.13 entails (72) for all & E H. KL(PP) Rt) < co. This implies the linear mapping + Ep [fo.rrixx xx x x is continuous on H. equipped with the norm || lle. It is worth noting that (Sg. || (l forms linear subspace of Se (see Léonard, 2007, Proposition 1.11), hence the fahn-Banach extension theorem (Delatte (2022, Theorem 1)) ensures that the previously defined linear functional H can be extended to the entire space S. without loss of continuity since the Luxemburg norm llee is convex function Sg. see Rao & Ren (1991, Section 2.2). Note that the convex conjugate of the Young function e( aa) is g" ((bl). Therefore, as showed in Rao & Ren (1991, Theorem 3.1.9), the dual space of (Sp. - (le) is isomorphic to the space
Banach space (see Léonard, 2007, Proposition 1. 1.18), and
D Jo.TTyxX e ((Kl)dn
Lgr = K. DT, [0,Ty] x X + R measurable s.t. Ep
< <00
that means there exists some K E Lo such that
Ee /
od. x = Ep D K xddn 7 1x
for any & E H.
(73)
We now prove the uniqueness and predictability of K. Introduce the predictable projection of K E Lg- as KP" = Ep K ). for / E [0, Ty]. Since B is dense in Sg. is dense the subspace of all the predictable processes Sp- Then, any two functions K1, K2 Lo satisfying (73) must share the same projection, i.e., K Kς" It follows that there exists unique predictable process K in the space
DT, x (0,Ty] X + R predictable s.t. IE; DNTAE ( {'((k))dn < <00 <00) K :D,
K(P)=
{K:
38

---

Discrete Markov Probabilistic Models
which satísfies (73). Moreover, for any function Φ H.
S JULTTIa od(Nx 4
-Kñ
dd(Nx -n - Kn
10,Ty1xx
od(Nx -KK + 1)n
10.T/1xX
JocrA1ox @d(NN Un
with U = K + 1, and the equation (73) is thus equivalent to
Ep V
Ød(NN - -Un>
=0, for any @ E H
(74)
Thus, Un 4 is positive measure and U is non-negative. Furthermore, argue analogously obtain equation (74) on the interval [s, t] for 0 & < & T then choose (w(,x)) = f(x) f(w.-) to deduce
V (f(x)
(f(x)- - ((X.-))(UU (166)) (dzdz) Fs F.),
Ee (f(,)) f(X,))
Es
for any f E F(().
(75)
Define the random generator l' on DT, x [0,TH] X2 by (U (w,,t,,,,)) = U (w, ( (x, v) for y o and the convention
(W,)(,, = U(c, (x, (.)
Then / forms generator and (75) rewrites
Ep (X(,) - f(X.) Ez V (U (V)))))((xx)))a
for any f E F(X)
As result, we conclude that I' E 7) We now show the formulation of the Radon-Nikodym density dIP R.. R. When R, define the stopping time T5 as
J = ::=inf( inf (
/ (o
te 1,Tyy;
e(log (w,, & (dæds)) > k or log Ue(ws,rr) $ [-j,
[0,1xx
which coincides with the stopping time of when x log U. Denote U = 10,000 U and for simplicity, we write U Uo By conditioning w.r.t. Xo, we can assume without loss of generality that Ko Po. i.e.
d'a dR
(Xo) = 1.
Applying Lemma F.14 for P E MP(UT) and x = log U, we have
2 Iry, log U.U p E (P( log U
MP [0.r 7)
(76)
Furthermore, = 1 = Rd¹s = 1d, where 7d is the invariant distribution (X,) (X.) which combined with the equation (76) imply T is the invariant path measure, i.e.
Q R5
39

---

Discrete Markov Probabilistic Models
Now, applying first Lemma F.14 for Ri E MP(7) and X = log U yields
p Zhpg U R8:s (P U 7) (a.7
Secondly, applying Lemma F.14 with p. E MP 10.31 U 7 and x= - -log implies
MP (0.r3) (o. Φ) := ZT," log U E (o, log U
Argue before, the previous equation together with the initial condition Q =b Th 7dth yield that Q 7, Combining it with Q R² implies
@ = Q
which means that
27, lon U pr ZTy 10oo U.U o ppr5
(77)
Now observe that ZT, log U.T7
therefore, equation (77) implies pr) P Hence P ZITT 2ioRUs R i.e.
U.
dP 10.r xTyl dR
dPp (Xo)
((X) ((X))E(TTT)) = NTT doo
(1 exp (oorAATIve (100ff log U)
-ooTAATANO e(log U)dn?
Letting and j tend infinity, since = lim Tf = oo, we get
dP (X.
dlo (Xo) exp ( log UdN
- e(log U)d
(X.)a(aTTT))=
dR
d Ro
We now extend the result above to the case when IP might not be equivalent to R. The idea is to approximate IP by sequence (PP)), which satisfies P., R for all n > Denoting
R
P, 1
P
for n > 1,
(78)
have P,, R and lim KL(P)P.) 0. For simplicity, write x log U and x" log U" which well- defined P-a.s. From the variational representation given in (70) and using PP E MP combined with Lemma F. F.13, we obtain
DATIIA (x- (<=>")dN'T
KL(P)),)) > Ep
S e(x - x"))((n)))
By definition, we have
Nº = Nx -7 = Nx Un + (U J NºJ + (U u
40

---

Discrete Markov Probabilistic Models
which yields
(L(P)),) Ep
1OTTIIIX (x- X2) (U 1002/11X
( U
llog
U -1 1 un
Umn
Er
JNLIIII (x-x")
U Uloog
dn
7
10,1,1xx Un -11 --1)urdn
(UN
1o,Tyixx
Un
Since P E () we deduce that the stochastic integral (xxxxxxxx")dxXX is a local P-martingale. Therefore,
U V U" -- -U
KL(P(P,) 2 1Ez
dn
U
U
U -log
REp
-1 Udi
U
= Ee U VarzIA e(x" "lx"-x)d(Un??)
Since 10m PL) = 0, we obtain
exx" (d""-xa((Un)) -0.
lim Ep 200000
(79)
On the other hand, the fact that P. R yields
dP
(Xi)ee10,T)))= = n0.n (Xo) exp (Nor)ja
S e(x")an))
x dN
(80)
d d
To obtain the desired expression for the Radon-Nikodyn density de dR
we represent it as
dP
dP dP, dPp d
(Xt)
(X
((X ((X+)
dR
dP dP
(Xo) exp (NOT)IN X"d
Jo.7,1xxx cdx")dn" 7
dP, R
dP dPn,o
(Xo)
dlP (Xo) exp (1 X x
e(x)da
dl,
dPu
dRo -x- - - (elx") - e(x))dn
10.1,11x
exp
P.a.s.
(81)
The last part can be rewritten as follows using equation (73),

---

Discrete Markov Probabilistic Models
exp Voerina (x" -x)Nx + { 10,T/1xx (x" -x- -x 1)dn (Jazzee (x" -YdN
-X
JormIux (ox" - xx e* x)dn
/ exx- (xxx))d((n²))
exp
We first handle the second integral above using (79) and the fact that is non-negative function,
Ee
exx-xxx (xx-x")((un))
n-000 0.
This together with Markov's inequality lead to
Jarmjix exx - x")d(Un3)) 50,
(82)
and therefore, from Méliot (2025, Proposition 1.4), there is a subsequence x such that
Jo exx-x x" )d(nn) nixx, 0, P-a.s.
(83)
Furthermore, recall that p(a) = c² 3 a² 22/2, hence (79) can be used control the stochastic integral w.r.t. the P-martingale NUF as follows
Ep [Voriaa 10- -x-xx)dN++ -
Aacrnx("-~NNuNee )
VOZZA (x" (x-
Corollary F.10
Eg
< 2E VIST/wxeex elx ((xxxxx(((n)))
This, along with Markov's inequality, results in
Jamiau (x" - 5..
Combining this with (82) implies that
JasIae (x" - x)
elx x")d(Un²) 1. 0.
As consequence, Méliot (2025, Proposition 1.4) asserts that there is a subsequence (x**) such that
(x -x))N
x)N
- - e(x
)d()nn)
k000 0, IPaa.s.
helps interpreting (81) as
42

---

Discrete Markov Probabilistic Models
dP
dP
dlP nI.0 dPo
dPo (Xo)
(Xo) exp (YOTIIX xdNx SorrIux e(x)dn
(())))())))))=
dR
dlP, ma
R
exp (H
(x* xNN
-1 (e(x²*)) e(x))
dPo (Xu) exp (orr)ex XdNx JOSTJJEX e(x)dn P-a.s.
(78)
dR
Replacing log U, we arrive at our desired claim
dP (X (X.)e(o,)T)) =
dPo - (o) exp (NOTIIX log UdgU - -Jampx e(log U)dn P-a.s.
dR
dRo
Consequently, the KL divergence reads
Ro) Ee U VArIi log UdN
- e(log (logU)dn?
Applying (74) to the function & = log U, we get
KL(P)T)- = KL(Pol Ro) + Ep 1 (o,T,)xx (U- - /o.
- e(log U)dn' 7
= KL.(Pol Ra) + Fx | J1L2y/xx -(U-1) - 1oggo - U + log U + 1]dn
= =K Ra) + Eg 1 J ((U(txz))ā (dtt)rr)))
with h(a) = ca - 1) = a log a - a + for a > 0. The proof of Theorem F.12 is then finished.
In fact, we can simplify the KL expression above by replacing n (didr) = Eyex 1xx, ty 7 (X, ((x and 7 by the formula given in (59) to arrive at
RT) (T. Poo) Ep /
M(U(t,)))
Σ 1 Xi- #y 9)),
10,T,/xx
VEX
IKL(Po|Ro)) + XEp / 1o.Ty)
(X,-)))dt
F.2.2. INTERPRETING THE RIVERSEVRSSED DYNAMIC AS A CONTROL-DRIVEN PROCESS
Let d E MP(7)) be the stationary measure on the path space IDr, introduced the previous section. Then, the process R is showed be reversible, meaning R R. and corresponds to the invariant measure 7d Uniform(X). Let represset the forward probability measure on the interval [o, Tyy starting from μz and governed by the forward generator 7 given in (59). We denote the corresponding time-reversed probability measure ending at jr
Fur = LLa(((X (x))ee)),T)) represent
by F'" Law((XX (x))))(..) Let μr be the marginal density of the forward dynamic at time t [0, Ty] and denote by i4 -4//dd the corresponding relative density.
43

---

Discrete Markov Probabilistic Models
Proposition F.15. The time reversal process PH" solves the Martingale Problem MP(u ( with the control given by: for (t,z) E [y] X,
(=) ux( y) = Σ ue(2, (x))//
ify (x) for some f= I.....,,d
if = I otherwise
(84)
1
Proof of Proposition F.15. Recall that the generator of the backward process & satisfies the following equation for t E Ty) and x + y.
(x pTy- (2)
( (y,
Using the fact that the stationary distribution 7" satisfies the following balance equation for I, y E X, x +
(x) (x. = (1) (1)))((v.))) (v,
we can express the backward generator as the perturbation of the forward one as follows
(1(.1) = HT, -1y) (V, = PT, (r,-s(y))((x)) (x. = pr, pr,-((u) (x, pr, (z)))()))"(
((x)
p
Note that 7/ (2. v) = 0 for y & fur (xx); -= 1=....,, d). thus we can define the control u as: for (1,2) E [0, x X,
ur (x)) (1T))((((((2))
for l = ,, and ue(x, (x. for y $ (a, (0 (x): ,.....d}
(())
to obtain the relation
7x = 7 (x,8), for (t,z,v) E [0,Ty] x x2 and # x.
Furthermore, under the convention
u,(x, xx) - Enyto ue(I, u) (x,y)
Σ
(x, (00 (x)) for (t,z) E [0,T,] X,
x2,
d
t=1
o in fact forms a generator and satisfies & of which implies that 'p' MP(w and conclude the proof.
Proposition F.15 shows that the unique control u associated with the backward dynamic (X (Xt)eetorr)) in Girsanov's thereom F.12 is in fact Markovian. This enables expressing the Radon-Nikk ModonnNikodym density d T /d as
d'F dR ((x,)eeto,T)))
(x)) exp (Vorppo log logu, vx xx)xx
JO.TAIX e(log un (X (x=, x))dd") 7
dRo
where is explicitly given in (84).
F.2.3. EVOLUTION OF THE CONTROL IN THE REVERSED- TIME SYSTEM
This section aims to characterize the control corresponding to the backward dynamics through the Hammiton-Jacolt Jacobi-Bellman (HJB) equation. This characterization serves as the key ingredient for applying Itô's formula to analyze the evolution the time-reversed process.
44

---

Discrete Markov Probabilistic Models
Proposition F.16 (Hamiton-Jacobi-Bellme equation). The control u given in (84) admits the following formula
ue y) e vV(c)))V for (,,,,)) E [0, x x²
x xサ4.
where v(t, -lo log -1)) which satisfies the following HJB equation
{ (t, = (e (ett) - 1],,
for (t, E (0,Ty x X.
(85)
[VT,,)) 9(())= -log H (x),
Proof of Proposition F.16. Denote 2t,,z) ;= log p (xx), then the optimal control can be interpreted as
(1( y) pry--(() c V(t.))
[ e V(t,z) = v(22)))
for (t, E [0,Ty] x X² and æ #
In addition, the function V fulfills the following equation: for (t,x) (0, x X.
(V((L.))= POJTT,-((0)
E 1T,, (tyy+(()) (y.z)
(by forward Kolmogorov equation)
PT,
Eyex PT, (v) 7 (a, (x)//(()))
(by balance equation)
(T,
(y) / (xx,)) 9)
BEX (t))
V(t.0)) -1]
1].
Moreover, V also satisfies the final condition
Vr, (x) = (o() log (x) g(z), for
therefore V solves the HJB equation (85) and thus concludes the proof of Proposition F.16.
To derive the convergence bound, it is essential to interpret the evolution of the control using the HJB equation first. In fact, the control above satisfies the following martingale and monotone property due to its characterization given in Proposition F.16.
Proposition F.17. With all the notations above, u. (x t. (00) (Xx)) is Tp' -martingale for fixed & = I,... d. Consequently (x,,(x (00) (1)) (X))) is a submaarrtiee and the monotonicity follows:
E B [b(u, sn w00 (xx()))) & E [b(uu (X (1x((()))) (XMM. for 0 0
Proof of Proposition F.17. Fix E [0,Ty] and l= = I,....., d. applying Itô's formula on
(t, x)) = =u,(x (xx e, (01 (xx)) = -(t.
and note that Law( Law(X.) ='"" solves MP(u7) as well as &, = Fr- for Lebesgue almost E (0, Ty] (see Mozumder,
45

---

Discrete Markov Probabilistic Models
2009, Proposition 2.1), we obtain that the process
-1,, (((
a 1p martingale. Denote
8/ 0. X.) + (u (.)))))) for E [0.4
We aim to prove that byg = -. Indeed, by the definition of fe, 7 and the HJB equation (85), we get that
b/ = un( ux(Xx, s: (0 (x
(2, x,) a,V(s, (0) (xx))
Us (pp (8) .), (12()) (X .)) -us(x as :0 :x()((x)))) o)] sus Aus(X ((00)))
+
==1
=dus(X (000 (X.))
Σ Uol Xx. (x (x)) - Σ (1(10) 10(1) (x2())
(xx))) (xx()))
=
uo ( (0 (X x))) ux si :000 (X.)) dus (X. (x,()
(X.)
(xx) (1p))))))))))))))))))))))))))))) (X.)))) ((1)))))))))) (xa)) ,
Us (x))
- -ua (X s), (p) (X)))) (x.))
(0)) for = 1,2.... in Proposition F.22 yields Using the identity uz( (x)) = ((.
e "1
bー A
(. =0,
:)) is a FF' -mattnngale Furthermore, since h is convex, it follows that hu,, (x, (000 (xx)) is F -submartingale, which implies the desired monotonicity for 1.2,..., d and concludes the proof.
as (1p(0) )) (0) (0) (X.)) for any -,i= d. We thus conclude that u, u.,(x,,, (x0)
F.3. Connection between the transition matrix and canonical process point of view
As we see in previous sections, the time reversal process can be understood not only via the backward transition matrix but also via the process driven by the control. The transition matrix point of view provides an approximation of the score to simulate the backward process, which is very useful in practice. In parallel, the canonical process point of view gives better understanding of the evolution of the time reversal process, which allows us to show theoretical guarantee algorithm. These two points of view in fact have strong relation, which will be specified in the following Proposition.
Proposition F.18. The control u driving the backward process satisfies the following relation w.r.t. the score function
46

---

Discrete Markov Probabilistic Models
defined in (17)
u (1 (x)))(((x)) = -x), with 1, d and (t,z) E (0.Ty) X.
(86)
Proof of Proposition F.18. The result follows directly from the definition of the score function in (17) and the form of the control in (84). This identity confirms the equivalence between the transition matrix viewpoint and the canonical process formulation.
E.4. Optimal control perspective on the time-reversed process
This section presents alternative perspective deriving the HJB equation, viewing it through the lens of optimal control and leveraging the Dynamic Programming Principle. In particular, the predictable process defined in Theorem F.12 can be characterized not only via the backward generator but also as the solution to an optimal control problem involving the expression of relative entropy.
In the continuous case, Conforti et al. (2025) demonstrated that the time reversal process can be formulated as solution an optimal control problem. This characterization not only describes the dynamics of the process but also serves as powerful framework for deriving the HJB equation, which be obtained by leveraging Girsanov's theorem (Theorem F.12)
Let R be the stationary measure on the path space Dr, introduced in the previous section. Then, the process R is reversible, invariant measure yd Uniform(X) Let TTx represent the forward probability measure on the interval [0, Ty] starting from μ* and governed by the forward generator o given in (59). We denote the corresponding backward probability measure ending at μ² by T0.".
meaning R RÝ, and corresponds
Proposition F.19. The time reversal process Fur satisfies the following optimization problem
(KL(P]A) + / sdPr..). with = - log duc* arg min FEP(Dry): KL(F 10
dhd
Proof of Proposition F.19. For TP La)((X)) P(IDT,) such that KT.(P| < 0o, the Donsker- Varadhan variational formulation of the KL implies that
sup st. f fotaRcoo ( fapp- log f (ddRt
R)
Taking /((Xx) = -9(X, yields
-gddrr, - -log e ooRRR, = =- - gdPr, - - log / dyr = =- --f gdPr,
/
KL(P R
since d4p = 1. On the other hand, since I the backward process ended at f and R is reversible path probability measure on [0, [3], i.e. Ih R, we have
d ((x
du- dy =
dR
This implies
F' Tt) = kL(4h)1) = (111)))))00000)1 log du²
dzadut du = - gdpp -- --foar
47

---

Discrete Markov Probabilistic Models
Combining the previous results, we obtain that the time reversal TP"" the optimal solution to the following problem
P
KL(P) + gdPTr,
arg min : (
which is the desired conclusion.
Utilizing the expression for KT.(IP R)) given by Girsanov's Theorem F.12, Control problem.
frame the corresponding Optimal
Theorem F.20. Denote by D the set of all U Dry [0, Tyl X + [0, oo) satisfying the integrability condition
Ep
Σ
((U)(
(0.1); [0,1]: s0 (x 11/dd <00,
Jo.Tyi
t=1
which is indeed equivalent to condition (61). Then P is the law of xu" with u² is the optimal solution to
X /
NUUiX (o,y) b.y 60 x o(x9))
inf E UED
Σ
(.TTy]
(87)
t=1
s.t. Law (X
)eEto,Ty)) MP(UT) with (U (w,
t, v) (w v) o (z, for $y.
Proof of Theorem F.20. Theorem F.20 is consequence of Theorem F.12 and Proposition F.19.
F.4.1. HAMIJTON-JACOB-BBLLLN EQUATION
The goal of this section is to derive the -aaiotoonJaccoi--oo (HJB) equation as in Proposition F.16 using the optimal control viewpoint. To this purpose, we first consider the generalization of the previous control problem. Let J be the following cost
J(,,,,U) = E
Σ
A(U.(xaan aa (1.)) 10 (x )))da + a( ((
[r.Ty] t=1
Law Law((X 2, ) E MP(UT) for (z, 1,, E x [0,TH] x D.
s.t.
J =x,
Consider 2)) to be the value function of the previous cost function, i.e..
v(t,z):= := inf x(),
UED
The following Dynamic Programming Principle is the main tool to derive the HJB equation. Lemma F.21. (Touzi, 2012, Theorem 3.3) For any stopping time k. E [t, Ty), the Dynamic Programming Principle (DPP) implies
V(t, = inf
A
Σ
MUU,(Sttuu 1010 ())ds s + V(e, Stalll (t,e) ((.e)
(88)
UED
[2.dl
t=1
Proof of Lemma F.21. Refer to Touzi (2012, Section 3.2).
The expression V given in Lemma F.21 leads us to the following HJB equation, that fact coincides with the one derived in Proposition F.16, and is characterization of the optimal control the problem (87).
48

---

Discrete Markov Probabilistic Models
Proposition F.22. Assume that V is continuously differentiable time. Then, the optimal control u' to the problem (87) Markovian, ie., ue (1) in x) for E (0, Ty and admits the following formula
in (z. (x)) = ((1
for 1.........4
with V satisfies the following HJB equation
- - - - = _d ((T 9(()) = - log du
for (t, (0,T,) x x
(89)
dya (x)
Proof of Proposition F.22. The proof is an adaptation of Proposition 3.5 in Touzi (2012). First, the DPP formula (88) for E (y) and = + a with a > 0 leads to
Σ MU.a 10 (xt2 Mds + V(t + a, Stall) - v(t,)) 20, (1,)
E
1=1
for any admissible control U E DD Using Itô's formula the process XT. with the law Fo E MP(U we get
U
(( (1,) "000 (x Mds + [ JpAtol (s (U, (U. ydsss > 0.
[12+0]
Using the formula of of and multiplying the both hand sides by 1 and pushing O, we arrive at
d
h(U,(z, (x))) (t, + A
((1,p10(x)) -
(((ao))-v((())) v(1,z))ui (l( 20, 0.
for any E D. Taking the infimum w.r.t. U, we get
VtV + inf UED
Σ (0 + ( (()) - xt),)) (1) (x)) > 0, for (t, E [0, (y, x X.
We prove next the equality by contradiction. Assume that there exists (lo, x0) E [0,Ty] x X such that
(,V + inf UED Σ
h(Uro (2o, (xoo)) + [V ((0
(zo, 60 (zo)) 0.
Denote (2o)) = V(oo, (xo)) V(lo, mo). The previous inequality implies that there exists E > 0 such that
0, (to, + A inf
(to, 20, (x0 > 5 0.
(90)
UED
Take & > 0 small enough such that
A
Σ
AV+ - (l, (000 (xx))
(91)
t=1
and define the function f & V as
1(1,x) = V((,z) - E [|t tol2 [z))
for (t, E [0, X.
49

---

Discrete Markov Probabilistic Models
It is clear that
z00 = (too,z)).
2ef = 0, (to and f(to. - V(to, = - for + zo.
Therefore,
0, Io) + inf VED
h(U (xx))) +f(to, 0 (zo)) f(to: zo)]Ut (0)) (2o))
=3,V(lo, + A inf UED
(((Uto(10, so (201)) + V(lo, (x0)) - V(lo, [ Ulo (vo: so (xo))
=t,V(to.zo) + X inf UED
[h(U) + (AV E)UT (to, 2o (x()
The minimum above is attained at U such that U(t,, To, e (- To, (40,
(00, (2n))
thus
@ + A inf
M(U (ro: ( (zol)) + [f (zo)) ((to, 2o) (zo, (0 (xo))
UED
3,V xo) +
(V++5 + (AV -)e (000
0,V mo) +
(1 e AV AV+5) to, (0 (2oo)
1=1
ato vo) +
(1 c AV (tu (0) + (e- -AVVee)(to 2o, (10
>0
where the last inequality relies on (91) and (90) with U = -V Therefore, we obtain
d
0,f mo) + X inf
[(Ur (000 + Lf(t, (zo)) f(to. zo) (10))) > 0.
UED t=1
From the continuity in time of the Hamiltonian, the previous inequality yields that
0 (t, + inf
(() 0, - (ft)) (20)
UED
for (t) E (to 7. +r) {5o)
(92)
for some <<< 1. Defining the stopping time n² as
" = inf { inf
(to, Tyl: Sto. + 2o n (to + r),
for arbitrary control U, we have
f(x", x
f(to +r, +r x0
if
Ty = D0 Xho + D2 R²=
if
50

---

Discrete Markov Probabilistic Models
This implies that
f(k x - V(n
-Er² E((N -tol 2 +
if
Fto = Xlo + 30 KU-
nll
-r2
Note that for any s [tu, J, not only Xio.ao.U 20 thus
Xto.2a. (ka.0)
Tv- Therefore,
(aU,(Xtoom ttol :p(0 (x + V(Ee, ) [t0.0)
I
M(,,
10
d
E
A
M(U,(2a ( (xo))) + f(n x Ex?
xl
1=1
s(n" x fllo, (lo,200
[lla Er²
(ta
Using ItO's formula to compute the difference f(x XtoeooiU) f-foi f(to, vo), and relies on the fact that V Vito, (tto,00). the calculation follows
5010 (Ftoooo)))))) + Vin (xocroll)) (too.oo0 (10,8)
E
a-
ke
1=1
E > [toney]
drf(5,20) + + (1
1=1
( (zo)) - [(s, (xo)) do + V(lo, gr²
(92) V(to, 20) + gr²
Since the above control U is arbitrary, the previous inequality is indeed contradiction to DPP formula (88).
Consequently, can deduce the following HJB equation satisfied by the value function for (t, [0,T;) x X.
0, (L,, + Ainfved Ete [M(UT(z, + (t, (l,))))))))))))))))))))))))))))) -V())))) (()) = 0,
(93)
v(T, = g(x).
Proceeding as before, we minimize (93) and obtain the optimal control
ui (X L2,a" (0.t) p000 (X):z.")) = ui ( (0))) (x)="") = ut (z, -(03)--000
for = I....,d, d,
that is Markovian. Replacing the formulation of u" into (93) boils down to
- (( ((T,,))= gxx) = log 2 (x)
= Ad
-
for (t, E (0, x X,
which in fact coincides with the equation in Proposition F.16 and concludes the proof of Theorem F.22.
F.5. Convergence of DMPMs
Based on the perspective of the canonical process, the backward evolution can be described as a control-driven dynamic. These tools enable us to establish the error bounds presented in Theorem 2.3 and Theorem 2.4.
51

---

Discrete Markov Probabilistic Models
1.5.1. PROOF THEOREM 2.3
We first prove the curvature-dimension inequality satisfied by our forward dynamics, which is associated with the stationary distribution 7d Uni. This serves the key estimate for deriving the entropy decay results later.
Lemma F.23 (Curvature-dimenson) inequality). The forward dynamic described above satisfies curvature-dimension inequality CD( o0), i.e.
T2()) S 2AT()) for any function f
where D is the carré du champ operator and 22 is the iterated carré du champ operator.
Proof of Lemma F.23. Recall the formulations Tf and 2 for functions f and g, which are typically defined as follows:
1 (d())) f(())) - (F and r(f)))=((f)) -
g(f.g) 2 1 (1((()222(2
T2(
where o is the forward generator defined in (14). These quantities capture the interaction between the functions f and g under the generator of and play crucial role in establishing results related to purvature-dimensin inequalities and entropy decay. We now compute explicitly (z) for x E X as
= (
d
Σ
(P(6))) - -(s)) ((())- 22(x))
Σ (z))
2
8=1
1 Σ
- -({)
Regarding the iterated carré du champ T2(f), the first term can be calculated
Σ
(Z))
(x)) (x)))
x
Σ
(z)) - 2)
2
2 t=1
Y=1
2 d
d
Σ
(2))) (=)) (())))))) (H(D(0(z)) -f(o))
(94)
2
To simplify the second term of 22, note that
2(f.g)()= - 1(79)-
d
= (10 ((())))))))())))))))))))))))))))
1=1
x Σ [((0) (x)) (o(5) (x))
Applying this to g = 5 yields
52

---

Discrete Markov Probabilistic Models
d 5(0) (1)) 1 (1)) -(x)) - Σ -1000))))))000((((000000
((),7))()) - A Σ
1=1 -
i=1
x
- f(x) s(0(0))))) (x))
(10))) (x))) + (0)
(95)
Plugging (94) and (95) into I'2 yields
= 1 17T1())
X²
Σ
(z)))-
- -((0))))))((((())))))---))))))) ((a)))))((())
(or))s((sa) + (f(x) - (x))) - 2 (1(00-1(00000)) (x)) (s()((())) -
12 d
d
(((000(00000)) - (x) - (z) + f(x)] 2
2²
(x) (x)) (z)) f(5)²
d (z)) - ((o)] = (z) for any x E X.
X2
Σ
Thus the desired inequality holds and we conclude the proof.
We are now prepared to analyze the key distinguishing result of this paper.
Proof of Theorem 2.3. We begin by establishing bound on the "distance" between the backward path measure in continuous time, Trr", associated with the controlled process (Xx, (x)))o)..))) and the path measure F corresponding to the simulated backward process (x; (eejo,y) generated in Algorithm 3. For brevity, we denote the backward path measure 1p"" by IP throughout the remainder of the paper. By taking the stationary forward path measure Tł E MP 7) as the reference in Girsanov's Theorem F.12, we derive the Radon-Nikodyn density of To E MP(u 7)) with respect to R, where the control u is specified in (84), as follows
TP
= aF.
(X.) exp (Nur)ii log u, (X,, N (dtdæ) - - -S e(log u, (x,,,x))i (dterr)
((x))e)0.T7))
d.
dRo
With a partition 0 = to <... <tk = Ty for K > 1 of [yl associated with the sequence of step-size 1K
<tx=
Tk+1
1++1 4. the previous expression rewrites
53

---

Discrete Markov Probabilistic Models
dF dR
((x))1(00T))) = dP. (o) exp
K-1
(
Σ
log (x x) (dtdr)
dRo
k=
-Saatariiex o(log ue (X,,,, x)) (dtdx)
d PP 0
(o) exp
Σ
log Vogui(X.o (X N (dlde)
d dRo
K=O
+
uX (n)
| [
e(log 2)) (dtdx)
d 0
K-1
(
(Xo) exp Σ
log ue (X,, Nx ? (dfdx)
d
d
x
Σ
(u - log ur (10 (x.-) ()db
t=l
A I
(u log u 1)(X,, (x(0 (Xd-))dtt
pm1
d
K-1
(
(o) exp
Σ
log ue (Xt-, x))
x) Nix (d(dx)
dRo
1=
(u log u + 1)(X,, p (x.))t
1=1
as X,_ X₁ for Lebesgue almost all & E [0, Ty). Applying Girsanov's theorem F.12 once more the path measure
F. E MP 7)) associated with the process (X;)) generated by Algorithm 3, we obtain the following expression:
a
d (Xo)
K-1
(1 log ui (X.,,x)N N (dtdæ)
aR (XI)ET))))))
Σ
exp
dRo
h=
- e(log uff' x)), (didx)
d F dRo
( log x)) (dtdz)
(1)) 1x)exp exp Σ
log üg () (dtdo)
/ / e(log of x))n (didx)
(led 1xxx
a dFg
K-1 Σ
(
(Xo)
exp
log ig (X,,, Nue (didx)
dR
k=
+
/
Σ (v log uf of. + +)((X,,,,,)) (X,
Since XX=X, for Lebesgue almost all E [0, Ty] and using the fact that as" (X,, (x,,,00(Xx)) ull (X1,, (010(x1,))) for any E [4,,441)) I,..., d and (X.)eeju,yy)- the calculation follows
54

---

Discrete Markov Probabilistic Models
dF+
((x, (Xe))T))TT)) = aPo (x) exp
R-1
( log ui xx,,x))N% (dtdx)
Σ
dR
dRo
1=
+1 /
(ue(Xei
(X+)) (X))) log Uiy (Xt, 1 ((() uht (Xt,, (01000(0) 1)dtt
[2zde+1)
8=1
Combining two Radon-Nikodym densities d 1p /aR and a a Ri, deduce that
ai% (Xx))e).Tz))
K-1
(nnneesnDi (log uh (X,,,,) - log of (X,,, Nx (dtdx)
(Xo) exp
Σ
p.
a
Ue uo( (p()) (Xt)) log U (X,, :p(() (Xi))
+1
Ui (Xt.) (p(() (X,.))
E=1
(((x),((((X,))) + uhi (X1z أ (X..)) dt
This leads to the following expression of the KL divergence
K-
M (log usl (oguu(Xee,,1 - log ui (X,_, x))
K = KL(RT,bT
N Now (didx)
+
E
k=0
usl ux(xe, e, (0() (x.)) uel ue(Ste (00 (xxe)) log
+t
uti (X (0ll) p01((xxx) (xxx))
mn((Xx,,pp (x)))) + ulf (x 10 (xx (xxx)) dt
Note that To E MP ), thus N is a F -mrtinggale, which in turn allow us to reduce the first integral above. Hence can simplify the expression for the KT, divergence as follows
ux es (lt)) (010 (x,)) log Ue ux es 1000 (Xx)))
k 1 KL(TT,,1 +
Σ EE 7 k=
Σ t=1
u1 (X tn (o(0) (> (X
pl0) (x)( + 21 (X (X (x dt
For brevity, we denote un (x(xx (xx) of throughout the remainder of the proof. We rewrite KL
PP +) as
K-1
KL k
KL(UT,178) +
Σ
BE
Σ
0- o) dl uc log of ul log uie uf + uie
8¹
0=
55

---

Discrete Markov Probabilistic Models
We separate this expression into three terms to control:
KT. KT.(PIF*
KI(UT,b79)
+
P
un log ui,
ut log uis o0 uie uha dl
(astet))
F1
F2
K --1
+ A
BF
(u, log of uf u/ log u/ + ule dt
(96)
k=0
We begin by observing that the uniform distribution 7d is the invariant measure of the forward process, which satisfies the curvature-dimensin condition CD(2A, o0) (see Lemma F.23). As consequence, satisfies a logarithmic Sobolev inequality by Bakry al. (2014, Theorem 5.10). This, in turn, implies exponential decay of entropy over time by Bakry al. (2014, Theorem 5.12), and thus we obtain:
KT(uT,h1")) < - (T.T
(97)
Next, we bound E2 using the tower property, the martingale property established in Proposition F.17, and the approximation assumption in Assumption 2.1,
K-
E2
E
Tie log u/, -Ey [u]]Fu] log uie
uhs + ule of
Jem0
Rmml
1-1
f U
Proposition F.17
Σ Bs
auf log uh, - uuf log uhn
or uhe + uiu oz dt
k=0
{=1
K-
(1++1 - 15)
uie log ge
uio + uex
8r,6)
Wie
--1
0- -h
=
(te+1 - 1B
Uee
k=0
where I((a- = a log a + 1 for > and (Fo)eejo.ry) denotes the right-continuous and complete natural filtration generated by the process (Xx (e)eeo,, Using Assumption 2.1, we can now bound the term Eg as
K-1 E2 < (tx41 - tx) = c(tx - to) = cT,
(98)
k=0
since Σk=0 (tx+1 tx) is telescoping sum. It remains to control Ez. To do so, we leverage the monotonicity of the function l established in Proposition 1.17,
56

---

Discrete Markov Probabilistic Models
K-
a
E3 =
F
Σ
E (((u))(Fr.] - n(uh)))) de
t=1
BB [ [Fa]
- n((ufa)) dt
1=1
K-
d
Σ h h(ulu)) )
(tx+1 - tx)
h
- EF
Define r = max(t++1 - tb: k = O.... K - 1}. the calculation follows
K
d
Mulaa) ))
Es E T
E
h(ubrn))
- E
Σ
k=0
P=1
P=1
Ep
h(uh;)
F
n((u))
(99)
since is neg-negative. Here, the Fisher-like information functional Sy of the data distribution js" is defined as 3ya(1²)) == ES Ei h(ulz)) Combining (97), (98) and (99), we arrive at
F <e- GNTNTRKT(U' Ar + AcT,
KT.
(100)
Finally, noting that μ = Law(Xx (x)),, we obtain the relation
(T.(x"]Taw((X x7,1)= KT.(Law(XX & [T)) (
(eeoo,))))) ((e))o))))))) KT TTr),
<
where the inequality is known as Data processing inequality for KL divergence (Nutz, 2021, Lemma 1.6). Combining this with (100), we conclude that
Law (X²,)) e <L + (x + AeTr,
and successfully provide theoretical guarantee for our generative models.
F.5.2. PROOF OF THEOREM 2.4
We demonstrate Theorem 2.4 through the following result:
Lemma F24. Denoting yt EF EZ (Xx,
(00 (x.1) then it holds for t E [0,Ty),
d
V1 2 T -
(101)
Proof of Lemma F.24. Recall the definition of h(aa a log a + 1 for a > 0, and the connection between the optimal control u, and the score function 8t, as provided by Proposition F.18, is given by
(0 = =1 (x) for = 1...,, d and (t, E (0,T,) x X,
with the score function admitting conditional expectation expression as given in (18),
57

---

Discrete Markov Probabilistic Models
-
4aT, - (X T-
X2y²
X - x ]
(x) E
with a₁ =
1 ++ -Ty-t
1 T,,-t
Using the above formulation of the score function, we estimate as follows
yv E 5
Σ
log(1 ( of (x,)
X (1 xx(x,) + {((x))
E
(since loga E <a- 1)
E
d
-0
4ar, (
X -1
X2)2
E
E
X ry-t = x
+ cry--
1 /
1=1
2
d
20T,,
Acr, -1
T--1 X202
E
E
X - =
+ orry-t
1 -
--a 2
-2
t=1
27
d
200r,-1
40T,- (ery-e(X/_ (8
24
8612
E
+ at
1 1- -07
t=1
Expanding the last quantity and noting that (X obtain that
X2)2 -xx)²
(8 -x6)** since (Xt Xb6 E =1, we
4a -
16a7 - - (X -2-1 (x X1)²
-1 1 -
Vo <
E
aT,-1)
(1 + aT, (1),-1)(1 -
E=1
1
407
16ag 1
X T5-1
X x22
E
(1 OT, -1,-1))
02 -1)
{=1
40 -t
16 1
-iB
E
(X (x -t- X6)2
(1 + OT, -1)
2 (1
x12-2) }2
Note that
(x T
x232 = P
{ Ty
# xx) = = arr
Thus the upper bound of ys
58

---

Discrete Markov Probabilistic Models
d
40
80 - ciTy -t)
y/ <
Σ
+
(1 CTyy -1)
(1 , )2
t=1
4da7
-
1+ (1 acT--1)
(1+ -1)
4da7
d
g4(Ty-t) - 2
for / E Ty)
1 a 01,-1
Tj -
where the last estimate follows from the elementary inequality e > + for all E RR. Therefore, the bound in (101) holds for all E y).
Proof of Theorem 2.4. We follow the same strategy in the proof of Theorem 2.3, the only difference being the way handle the following term in (99)
K-1 E3
1)
K-1
Σ k=0
(te+1 tx)
E
h(
h
E F
Σ
h(urz)
Σ
Th+1 (yiz41 Yee)
k=
Following precisely the argument structure in the proof of Theorem 3 from Conforti et al. (2025), and fixing Ty, a, and c, we choose the sequence step-size as
Ty - tN-1:
k = N 1,,
ca
1 ko ko + k 1
kn + ki < ko + ki + 2/
7k+1
(102)
c(Ty tk)
C.
0 < k 11,
and set the number of iterations = ku + k1 + 122 + 1, with
ko max (k 3 0:
4 > 1}. hi = max {A > 0: Ty - 1x + 20 and K2 = max {k > 0: Ty - -ootk 2 0}
(103)
is shown Conforti al. (2025) that
Ko | (T, 1)J, kn = -looooaa/(T; - (k, (bo)))/ogg(1111 c]] S log(1/a)/c,
(104)
K Ko ki = by + S 1/c and Tk+1 = o(1 - c)* -Ko (T, - tk.)) for E (ho...., ko + k1 - 1)
Using (102) and the monotonicity of yt established in Proposition F.17, we can bound E3 as
59

---

Discrete Markov Probabilistic Models
K- 1
E3 <
7o+1 (Utzy1 Ver)
k=0
=K
yl (To [k+1)
ko
-Tk
Σ ycee (Tx -b+1) +
Σ
Ucu (Tk - Tx+1)
k=1
k=
No bo+the ke 4
Σ
Deu (Th Tk+1) + yono (TK-1 TK)
Ko-ki- -1
S Viko
(e c(T, - [ND)]
+
Σ k=
Vee
(1)
Cyinotes
(T
tko +ki - a)
Vix TK-1
(3)
(4)
We now bound (1) -(2) -33 (4) one-by-one. We start with
Lemma F.24
cd (103)
(1) ybkp c(Ts twa)) & Cytto
cd.
T tko
Next, we bound the second term
Lemma F.24 kot
to -1
(2)
yt Th
Σ
Tj L
Ed Σ
Tk+1
k= #1
k=
k=
to tkt
c(1 - c)k -
-1 -(' (kk)
(104) 2d
Σ
c(1 kk
Ko Ro, - -kka))
k=ky-1
kp to -1
05//2
dd
Σ
S dd S cdd (ollog(1/a)
1-c
Recall that T - 1kothi11 & 1. As a result, we have
Lemma F.24
od
cd
(3) : :Cttog (T₁ - -1 a)
(T, bhoth =
(Tş
tkotk
T, tkitk
T,
thotki Thitki
(102) ad eg1/2
1-c S cd.
Finally, for the last term, we have by definition of L VT, /d,
(4) y/ hx = Vr, ca cadl.
Plugging all the bounds of (1) (2) -(3) (4) into E3 gives
Fg S ed[l + (/o(1/)) + aT.)
60

---

Discrete Markov Probabilistic Models
Moreover, choosing L/L yields the following bound on the sampling error
KL(j"|Law X xx))) - -LNKKL((" Acd[1 + log(L)] AeT,
and this concludes the proof of Theorem 2.4.
F.5.3. PROOF OF COROLLARY 2.5
Proof of Corollary 2.5. Applying Theorem 2.4 with c, T chosen in (32) implies
kL(u
S + elog
Therefore we obtain the approximation error Ō(e log (KL(4t((L) In addition, the number of iterations is given by
(104)
T - log(1/a)
+ Ty + log(L)
K = ko + h1 + K
ko
h1
(32) Ad[1 + (lgg)))lgg((LL(()))))))))))))
log(L))
6 Allg(()
di + log
Alog(L)]
which grows logarithmically rather than linearly with respect to the discrete Fisher information S (x²) We thus conclude that this step-size sequence offers improved performance compared to the constant step-size.
F.6. Convergence of DMPMs with early stopping strategy
1. PROOF OF THEOREM 2.6
Proof of Theorem 2.6. Applying the proof of Theorem 2.4 with the target distribution H4, in place of μr" leads to the following analogous result:
KL(p,ILaaw X -n)) & -- -X(T444))) KL(phh") + ded(1 + log(L)] + De - 11)
(105)
Recall that the forward dynamic satisfies the curvature- curvature-dimension condition CD(2A, oo) (see Lemma F.23) and consequently the logarithm Sobolev inequality holds (Bakry et al., 2014, Theorem 5.10):
< - Uy log My 41 gd gd
(106)
As computed in Lemma F.23, we have
E [n log
My
My pol
(x) log (n (x) - log Mn
nd (z)) 7x)))
gd 7d
go
zEX 1=1
My (x((Kn)
AE
log
(107)
My (x(e
61

---

Discrete Markov Probabilistic Models
On the other hand, the discrete Fisher information of My is given by
lo (X,))
+lom + (o)2
(1a) = E
e
log (111)))))9))))
E
h
e
E
My (x,)
Mn (n(()(0) (X
log (n((o(0((
(n(((0 +1)
E
(xy(X,)
(x,))
(x,)
My (1)( (x)) log Mn ((((""(())))
pn (x)()((())) 1n(2))
(x)
-ext=1
My (n(l((((x))
Bn (x)()((0))))) (x)) log
Mg(
(nn(:) log
Mnn (x)(o((((x))
rex
E
log
(
(107)
E
Hy god
log
Hy +
May (y(())())
(
Plugging it into (106) implics that the discrete Fisher information dominates the KL divergence as
1 (L(um)1)) & 7 (r(())))
To complete the proof, remains to bound the discrete Fisher information. To this end, we employ the elementary inequality log a & a for 0, and proceed using the same reasoning as Lemma F.24, detailed below,
1n (x(()((0(x,)))))
(x((0(0((x))) (x(p)()(Xx))) +1)
(1a)) E
log
Men (xx))
Mx(x)))
(x((xn)
Mn (xx))
(1(()(0((xx)))
-1) po( 1 1
E
My (Xx))
My (X))
(x)(Xn)
(1 X x)
E
-1
My My (X,)
E
Σ
1 (x x)))²
x Ty - (T - n1)
d
d
It follows that
$ d and L= d d Bra(Hnn) Sn
kL(unhd)
17
62

---

Discrete Markov Probabilistic Models
Combined with (105), this leads to the desired conclusion:
(L, (X;, 2 tc + Aed[1 + log(n + Ac(T, 11)
F.6.2. PROOF OF PROPOSITION 2.7
Proof of Proposition 2.7. Recall that the total variation distance between Ma and μ for 17 E (0, max {Ty. })) is defined as
11 - 1 11 Σ
-200))--00000 (x)
mex
By the triangle inequality, we obtain
1, 1 1| [2((2) - (x) (x) (x)
where the transition probability p,, is defined in (15). The two terms above are non-negative as
Un(z)=
Σ (1)7 > n (I),, ZEX
and the transition probability B2 x) & 1 for any X. This together with the formula of p,, in (15) yield
(1 + 1 2An 2
I| n² 11v Σ
(x)(x) (x) (x)
xEX
1 1
-20 2Am
2 2
2 + _e
To simplify this upper bound, we apply the exponential inequality ea > a + e 2An - and note that Auy > 0:
1 ( (-(--2 11) d 22 2(1 -nn)a
[m - 1= < 2-
and thus the proof is complete.
F.6.3. PROOF OF COROLLARY 2.8
Proof of Corollary 2.8. We observe the following by applying the triangle inequality and Pinsker's inequality,
l| Law 8 -, - < 11 pollTV + l1,s, -Law X 7n
1| - 22KL(H, (n))
Then Theorem 2.6 and Proposition 2.7 together imply
|| - Law Law x $ (1 21) v dn- 42(T)-9) / Aedd( + log(11-)) + v Ye - 11)
(108)
The choices of and T, in (35) lead to
(1 >n) e and -o -MM(T-N) =22 and Aod(1 + log(1-1)
(109)
63

---

Discrete Markov Probabilistic Models
Substituting (109) into (108) gives the desired upper bound
l1 Law ( -0 Set Ve((Ts 11)
with the number of iterations
K Ty 17 + log((1 (35) Ad[1 + log(on [log (d/ l
é²
d[1 + log(1) |log d n)²") + Alog(1
2
d|1 + log(1 ) [logg) d/e2))))))))))) + (A + log(n
(110)
Finally, the term log 17 can be bounded from above by Bernoulli's incquality (1 (1-e) c) < 1 for E (0, and > 1,
log(n loo (1-(1
A (1 ejild
Ad log
Plugging it into (110) concludes the proof of Corollary 2.8.
64


Reviews:
[{"review_id": "vSMxrV8SRw", "reviewer": "Reviewer_5ek8", "summary": "This paper introduces the Discrete Markov Probabilistic Model (DMPM), a uniform noising/denoising algorithm for discrete data generation. The authors establish theoretical convergence bounds under minimal assumptions and validate the effectiveness of their method empirically on both low-dimensional Bernoulli datasets and a relatively high-dimensional binary MNIST data. By bridging rigorous theoretical foundations with practical performance, this work makes a valuable contribution in the emerging area of discrete generative modeling.\n\n### update after rebuttal\nThe reviewer thanks the authors for the detailed response and for positively answering the raised concerns. Overall, the reviewer thinks that the theoretical results in this paper adds value to the better understanding of discrete diffusion models. Although experiments are not the main focus of this paper, the submitted version had a wrong experiment as acknowledged by the authors at the end of the rebuttal below. Besides, the paper makes a claim against the standard practice in large-scale experiments, which is \"absorbing kernels perform better than uniform\". However, there is not enough evidence to prove or disprove this claim. Given the strength of the paper in theoretical analysis, the reviewer recommends accepting the paper.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive feedback, especially regarding the strength of our theoretical contributions. Due to space constraints, we address only the most critical concerns, but we welcome further discussion if any important points remain unaddressed.\n\n> Additional large-scale experiments or high-dimensional evaluations are necessary [...]\n\nWe acknowledge that our experiments are limited, and we agree that more extensive large-scale and high-dimensional evaluations are necessary to fully support the use of uniform noising kernels in comparison to masked ones. Nevertheless, as the reviewer noted, the core contributions of our paper are theoretical.\n\nOur main objective is to derive convergence guarantees for discrete generative models that match those known for continuous diffusion models. As emphasized in our paper, there is a notable lack of results concerning discrete diffusion models. The closest related work, upon which ours significantly improves (as detailed in our response to Rev. fUbX), has only recently been accepted to ICLR [1].\n\nIn pursuing our goal, we obtained a representation of the score as a conditional expectation (Prop 1.1 and 1.2), which is the foundation of our methodology.\n\nWhile limited, we believe our numerical experiments add value by showing the practical potential of our approach. That said, we agree that strong conclusions should not be drawn from these preliminary results, especially in large-scale or high-dimensional scenarios. To address this, we will revise the conclusion to clarify that our findings are meant to motivate future empirical work rather than provide definitive evidence.\n\n[1] Ren et al, ICLR 2025\n\n > Lines 99-103 [...] The notion of conditional expectation of [...]   is the key contribution in prior works, such as D3PM  or MDLM).\n\nFrom our understanding, prior works—including those mentioned by the reviewer— aim to estimate the generator associated with the backward dynamics of the backward process  relying on estimating the conditional distributions  $p_{0|t}$ of $X_0$ given $X_t$ for $t \\in [0,T_f]$.\n\nIn contrast, we first demonstrate that estimating the generator of the time-reversed process is equivalent to estimating the discrete score function introduced. Second, we show that (1) this score function can be expressed as a conditional expectation, and (2) it is associated with a discrete denoising structure.\n\nTherefore estimating the backward generator reduces to solving either a regression or a classification problem—tasks that are often more tractable than learning full conditional distributions. While prior work seeks to model an entire conditional distribution, we focus on estimate a function that solves a regression or classification task.\n\nWe regret any confusion caused by the original formulation and will revise the paper to include this discussion in order to clarify our claims.\n\n> Theorem 2 in [2] [...] Isn’t there a tight characterization of this error?\n\nThe third term $\\epsilon T_f$ has the same meaning and significance of the corresponding term in Theorem 2 of [2], appearing as such. Indeed, it accounts for the score approximation error that we do not investigate in our submission similarly to [2].\n\n[2] Chen et al, ICLR 22\n\n > The transition probabilities [...] can be seen in [...] (Chapter 2, Liggett)...\n\nAs stated in the paper, these computations are well known, and we thank the referee for pointing out the reference in Liggett’s book, which we will include in the revised version. As the referee suggests, we will emphasize this point more clearly early in the paper.\n\n> The regression loss used in Equation (15) is quite similar to the DFM loss...\n\nFirst, we would like to emphasize the following points based on our understanding:\n- (1) The SUBS parameterization is applicable only to absorbing kernels;\n- (2) The approach in [3] focuses on estimating conditional probabilities $p_{s|t}$, which is fundamentally different from our methodology, as previously discussed.\n\nConcerning the DFM loss, we were not able to find a similar result as ours in [4]. It seems to us they use a flow matching construction with a conditional rate matrix built ad-hoc (Section 3.2). This seems fundamentally different from the way we derive our reverse process (see (4)). \n\n[3] Sahoo S. et al, 2024, Neurips\n[4] Campbell et al 2022, Neurips\n\n > What is the relation between Assumption 2.2 and the irreducibility property of CTMC?\n\nAss. 2.2 only states that $\\mu^\\star$ has full support and does not impose any conditions on the CTMC considered in our analysis.\n\n> Table 1: DMPM (flip) seems inconsistent\n\nWe thank the reviewer for spotting this, indeed we loaded the wrong model checkpoint for the evaluation run at 500 steps, here is the result of a new run:\n\n**Table 1: FID$\\downarrow$ and F$_1^{dc}\\uparrow$ for DMPM methods at 500 reverse steps.**\n\n| |FID|F$_1^{dc}$|\n|---|---|---|\n|flip|6.98|0.94|\n|denoise|2.52|1.00|", "claims_and_evidence": "The paper provides strong theoretical results supported by rigorous proofs; however, the empirical evidence presented appears somewhat limited. Specifically, the claim that uniform noising kernels offer provable theoretical guarantees and superior performance compared to masked approaches like MD4 remains inconclusive. The main concern is that uniform noising kernels typically perform poorly in high-dimensional scenarios compared to absorbing kernels. Given this context, additional large-scale experiments or high-dimensional evaluations are necessary to convincingly support the claim that uniform noising kernels are practically superior to masked methods like MD4 or MDLM.", "methods_and_evaluation_criteria": "The evaluation is currently done at a relatively smaller scale (toy dataset and MNIST). Large-scale evaluations are essential for conclusive evaluation of the proposed claims.", "theoretical_claims": "Theorem 2 (Chen et al. https://openreview.net/pdf?id=zyLVMgsZ0U_) has a similar form as that of Theorem 2.3 (also Theorem 2.5) in this paper. While the first term in the upper bound seems unavoidable, the second term can be avoided as shown in Theorem 2.5. The reviewer is wondering about the dependence on $\\epsilon$ and $T_f$ in the third term, which seems like a coarse discretization error as compared to Chen et al. Is this the optimal characterization of the score approximation in the full trajectory? Intuitively, if the approximation error is of $O(\\epsilon)$ and then we take $T_f$ denoising steps, then the total accumulated error would be of $O(\\epsilon T_f)$. Isn’t there a tight characterization of this error?", "experimental_designs_or_analyses": "Yes, the conducted experiments look okay to me. But large-scale experiments are missing for a thorough evaluation.", "relation_to_broader_scientific_literature": "The choice of transition kernel is quite ambiguous because there exists a mixed set of papers that claim absorbing kernels are better than uniform noising kernels or vice-versa. Indeed, a proper theoretical understanding of any of these two commonly used kernels or new approaches is a valuable contribution to the community.", "essential_references_not_discussed": "Some essential references have not been included. Please see the weaknesses for details.", "other_strengths_and_weaknesses": "### Strengths\nThe choice of transition kernel is quite ambiguous because there exists a mixed set of papers that claim absorbing kernels are better than uniform noising kernels or vice-versa. Indeed, a proper theoretical understanding of any of these two commonly used kernels or new approaches is a valuable contribution to the community. \n\n### Weaknesses\n\n1. Line 25 (right col): “In this paper, we introduce Discrete Markov Probabilistic Models (DMPMs), a new class of generative models for discrete data that bridges these gaps.” This is not entirely new and dates back to Sohl-Dickstein et al. 2025 and popularized by Austin et al. 2021 with many other recent follow-up works. \n\n2. The notation in Line 66 for $|d\\mu/dR-d\\nu/R|dR$ seems squeezed in one line. It could be better presented as $|\\frac{d\\mu}{dR} - \\frac{d\\nu}{dR}|dR$.\n\n3. Lines 99-103: “We derive closed-form expressions for the backward transition rates, which involve conditional expectations over the forward process. This enables, for the first time, an efficient training procedure based on regression in the discrete setting.” What is new here? What is done for the first time? The notion of conditional expectation of $X^{rev}_T$ given $X^{rev}_0$ is the key contribution in prior works, such as D3PM (Austin et al. 2021) or MDLM (Sahoo et al. 2024). \n\n3. The transition probabilities derived in Equation (2) and Appendix B.1 can be seen in the introduction to CTMC (Chapter 2, Liggett). Again, the originality and innovation of the analysis is limited in my opinion.The authors are encouraged to highlight (maybe informally) the original theoretical contributions early on in the paper for the ease of assessing the major contributions.  \n\n4. The key contribution of the paper is in Equation (6) with a more generalized version in Proposition 1.1, where the discrete equivalent of score is written as an affine transformation of $X^{fwd}_0$ and $X^{fwd}_t$. A slightly modified version of this result has previously appeared in DFM (Campbell et al. 2024). \n\n5. The regression loss used in Equation (15) is quite similar to the DFM loss or other discrete diffusion losses as in MDLM. The reviewer is finding it difficult to understand what this theoretical result is prescribing here. Again, the loss in Line 225 is similar to the subs-parameterization introduced in MDLM (Sahoo et al. 2024). The authors are encouraged to clarify these similarities and highlight the innovations of this paper. \n\n6. What is the relation between Assumption 2.2 and the irreducibility property of CTMC? It’d be better to connect this assumption with CTMC for better understanding and consistency with prior discussion. \n\n7. Theorem 2 (Chen et al. https://openreview.net/pdf?id=zyLVMgsZ0U_) has a similar form as that of Theorem 2.3 (also Theorem 2.5) in this paper. While the first term in the upper bound seems unavoidable, the second term can be avoided as shown in Theorem 2.5. The reviewer is wondering about the dependence on $\\epsilon$ and $T_f$ in the third term, which seems like a coarse discretization error as compared to Chen et al. Is this the optimal characterization of the score approximation in the full trajectory? Intuitively, if the approximation error is of $O(\\epsilon)$ and then we take $T_f$ denoising steps, then the total accumulated error would be of $O(\\epsilon T_f)$. Isn’t there a tight characterization of this error?\n\n8. The authors are encouraged to write some implications of Corollary 2.7 at the end of Section 2. The transition from Section 2 to Section 3 seems abrupt. \n\n9. Table 1: While other methods show a consistent behavior, DMPM (flip) seems inconsistent as the number of reverse steps increases. The authors are encouraged to check the numerical simulations of this sampler or provide a better justification for this inconsistent behavior. \n\n10. Experiments on MNIST are not quite high-dimensional. The paper would significantly benefit from even higher dimensional modeling, especially because uniform noising is known to perform suboptimally compared to absorbing diffusion in higher dimension. \n\n11. How would the analysis change for absorbing kernels since that has been very successful in large-scale experiments (see MDLM and other follow up works).", "other_comments_or_suggestions": "Please see weaknesses.", "questions_for_authors": "Please see weaknesses.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nVHixbhMTW", "reviewer": "Reviewer_fUbX", "summary": "Score-based diffusion models are becoming one of the most promising non-adversarial and easy-to-implement data distribution reconstruction techniques. The idea is to define a forward noise process that gradually degrades the training data until it is transformed into a simple distribution that is easy to sample from. The model learns to reverse this process by learning the log-gradient of the noisy marginal distribution, known as the score. While most noise removal models to date have dealt with continuous state spaces, in recent years, the benefits of noise removal frameworks have been highlighted for problems involving discrete data, such as text, segmentation maps, categorical features, discrete latent spaces, and direct 8-bit image representations, and research in this area has been developing very actively.\n\nThis paper presents theoretical and practical investigations of the case where the state transition probability follows the mechanism of Poisson clocks with state bits for a {0,1}^d state space. The model set up by the authors succeeds in obtaining a closed-form expression using score-based conditional probabilities of forward processes, whereas many diffusion models originally suffer from the difficulty of handling the representation of backward processes. As a result, the authors have succeeded in theoretically guaranteeing that the proposed discrete diffusion model has a tighter fitting bound than conventional models. Along with their theoretical results, the authors have also quantitatively evaluated the effectiveness of their proposed method using artificial data and MNIST binary images to demonstrate its practical performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments, which will help improve the presentation of our contributions. We hope that we have addressed all of their questions in the responses below. Given their positive feedback—particularly their appreciation of the \"very impressive\" theoretical contributions—we would kindly ask the reviewer to consider raising their score, if they feel it is appropriate.\n\n> I wanted to know whether the breakthrough [...] briefly outline Appendix F (Proof of Theoretical Results)\n  \nWe thank the reviewer for their remark, which will help us clarify the key contributions of our paper. To this end, we provide a brief sketch of the proof for **Theorem 2.3**, which we will expand upon and include in the revised version of the paper.\n\nThe first step in the proof is to decompose the relative entropy  \nbetween the backward process and our generative algorithm into three terms:\n$$\n\\mathrm{KL}(\\overleftarrow{P} \\| P^*) \\leq \\mathrm{KL}(\\mu_{T_f} \\| \\gamma^d) + II + III.\n$$\n\n- **The first term** on the right-hand side arises from the fact that the generative process does not start from the marginal at time $ T_f $, but rather from the stationary distribution $ \\gamma^d $. Using standard arguments for the convergence of random walks on $ \\lbrace 0,1\\rbrace^d $, this term is exponentially small in $ T_f $.\n\n- **The second term** $ II $ corresponds to the score approximation error. By **Assumption 2.1**, we can bound it by $ T_f \\varepsilon $.\n\n- **The third term**, $ III $, corresponds to the time discretization error of the generative process. It is given by\n$$\n\\sum_k \\mathbb{E} [ \\int_{[t_k, t_{k+1}]} \\sum_{\\ell} u^*_{t_k}(\\ell) \\cdot h(u^*_{t}(\\ell)/u^*_{t_k}(\\ell)) dt ],\n$$\nwhere $u_t^*(\\ell) = 1 - s_t^{\\ell}(\\overleftarrow{X}_{t})$, and $(\\overleftarrow{X}_t)_t$ denotes the time-reversed process.\n\nTo bound this term, we rely critically on **Proposition F.11**, which serves as the main technical tool in our analysis. Specifically, the proposition shows that:\n\n1. The process $ (\\sum_{\\ell} u^*_t( \\ell) )_t$ is a **martingale**, and  \n2. The process $ (\\sum_{\\ell} h(u^*_t(\\ell)))_t $ is a **submartingale**.\n\nThanks to these two properties, along with **Assumption 2.2** and an application of Jensen’s inequality, we are able to bound the third term $ III $.\n\n\n> does the fact that we have made a stronger assumption on the state transition matrix than before contribute to this concise argument? \n\nThe reviewer is correct in noting that the arguments we developed—and summarized in our previous response—crucially rely on using the random walk on {$0,1$}$^d$ as the noising process. Nevertheless, we view our work as a foundational step toward extending the framework to broader classes of discrete generative models. \n\nIn fact, as part of our future work, we aim to formalize our reasoning in a more general setting that could encompass a wide family of discrete models, including masked diffusion processes.\n\n > My main concern [...] is a much stronger situation than the assumptions made in previous papers.[...]\n\n We thank the reviewer for this comment, which helps to clarify the implications of our work.\n\nFirst, as this appears to be the reviewer’s most critical concern, we acknowledge that—unlike most previous works—both the state space and the noising process we consider are fixed. These choices are indeed crucial for establishing our theoretical results (as detailed further above) under minimal assumptions on the data distribution. We will emphasize on this point in the revised version of the paper. \n\nHowever, we would like to make two points in response. First, although working on the hypercube may initially appear restrictive, we note that any discrete space can, in principle, be embedded into the hypercube via binary encoding. This means that our algorithm can, in theory, be applied to any discrete data structures. \n\nSecond, we view the theoretical analysis presented in this paper as a first important step to demonstrate that convergence guarantees for a general class of discrete score-based generative models can be achieved under minimal assumptions on the data distribution.\nAs we emphasized in our first response, we are confident that the techniques developed here have the potential to extend to other discrete structures as well. However, since the exact scope of this generalization is not yet fully understood, we refrain from making definitive claims at this stage. \n\n>  In particular, the description of the paper's position in relation to the latest methods [...] is limited to high-level, abstract explanations.\n\nWe will follow the reviewer’s suggestion and, in particular, include a comparison table in the camera-ready version of our paper. We also plan to add a detailed discussion of the assumptions made in previous works—specifically those concerning the data distribution, as well as the density and score of the noising process—which our approach is able to relax.", "claims_and_evidence": "This paper argues that imposing the condition that the state transition probability follows the mechanism of Poisson clocks on the state bits on the state space of the hypercube {0,1}^d for the discrete diffusion model can resolve the issues that the conventional discrete diffusion model has had (limitations on convergence, increased computational cost for high dimensions, and the need for extremely strong assumptions in theoretical analysis).\nSection 1 describes the discrete diffusion process assumed by the authors. Section 2 evaluates the usefulness of this model theoretically in the form of a bound on the convergence. Section 3 empirically and experimentally verifies this.", "methods_and_evaluation_criteria": "My comment on this term is merged into Claims part.", "theoretical_claims": "I find the theoretical contribution of this paper very impressive. I would like to ask the authors a question to properly understand its value. I am trying to understand this paper by contrasting it with the theoretical work of literature [Campbell+, NeurIPS2022] and [Ren+, ICLR2025] (which seems to be same as the reference arXiv2410.03601 cited in this paper) as important examples. For eacmple, Reference [Ren+, ICLR2025] seems to consider state transition matrices in the general discrete state space as state transitions in discrete diffusion processes (Section 2 and Appendix B). As a result, since the state transition matrix of a Markov chain is combinatorial in dimension and large in size, it seems that, for example, in its mixing time analysis, the spectral gap (the order of the inverse of the mixing time) is evaluated as in the standard MCMC procedure for mixing time analysis. On the other hand, this paper, very interestingly, seems to achieve avoiding any mixing time analysis focusing on the eigenvalues of this kind of state transition matrix. In fact, the proof in Appendix F.4 shows a very concise argument for state transitions, where only a reference to self-transitions for an arbitrary time interval\\eta is sufficient. So, my question is, does the fact that we have made a stronger assumption on the state transition matrix than before contribute to this concise argument? As I understand it, the assumption seems to be placed that the state transition probabilities for high-dimensional binary data are represented by the direct product of independent binary state transitions in each dimension, as shown in Equation 9. Is this understanding (i.e., that it restricts the state transition dynamics more than previous studies) correct?", "experimental_designs_or_analyses": "The authors compare the proposed method with the latest discrete diffusion process for artificial data (Bernoulli simulation) and MNIST (the original 28x28 is upsampled to 32x32). While the Hellinger distance and KL divergence between distributions are generally used as quantitative comparison criteria, this paper uses the sliced wasserstein distance for evaluation because it has a theory that can handle high-dimensional data that previous studies could not handle.\n\nI think this paper has produced some impressive results in terms of theoretical contributions. However, the theoretical results in Section 2 only give a bound on the closeness between the data and the model distribution, so it would certainly be very interesting from a practitioner's perspective to see how it behaves on practical data. I think the authors' experimental results (albeit not on a large and diverse set of settings) give the reader some intuitive insight into the effectiveness of the proposed method.", "relation_to_broader_scientific_literature": "With the spectacular success of continuous state diffusion processes, discrete state diffusion processes are expected to play an increasingly important role in a wide range of applications, including text and biological information. I think this paper provides some very important insights into this development.\n\nOn the other hand, this paper seems to make the strong assumption that the state space of the discrete diffusion model is a hypercube on {0,1}^d, so it seems non-trivial whether this approach can be applied straightforwardly to natural language or genetic information.", "essential_references_not_discussed": "This paper refers to a wealth of literature on the discrete diffusion process, which has been the subject of particularly active research in recent years.\n(I checked the list of references, for example, which cites several important papers [Campbell+, NeurIPS2022], and confirmed that this paper cites them appropriately.)", "other_strengths_and_weaknesses": "[Strengths]\n\n- This paper insightfully discovers a special class of discrete diffusion processes in which the backward process can be expressed in a closed-form, easy-to-handle form.\n\n- The authors theoretically guarantee the importance of this discovery in the form of a bound on the closeness of the data distribution and sample distribution. This is a very impressive result that scales more naturally to higher dimensions than conventional discrete diffusion processes.\n\n- The authors demonstrate the practical effectiveness of the proposed method not only with theoretical guarantees, but also with medium-sized data.\n\n[Weaknesses]\n\n- My main concern is that the class of discrete diffusion processes considered in this paper (discrete states on the hypercube, with state transition probabilities being the direct product of each dimension) is a much stronger situation than the assumptions made in previous papers. My main concern is that the class of discrete diffusion processes considered in this paper (discrete states on the hypercube, with state transition probabilities being the Cartesian product of each dimension) is a much stronger situation than the assumptions made in previous papers. I think that setting very strong assumptions in order to achieve a breakthrough in theoretical analysis is very meaningful in itself. However, because this paper does not discuss this in depth, it is somewhat unclear where it stands in relation to recent developments in discrete diffusion processes. In particular, the description of the paper's position in relation to the latest methods (Section 0 and Appendix A) is limited to high-level, abstract explanations, so a very deep prior knowledge of the field is required to correctly understand the paper's true value.", "other_comments_or_suggestions": "Line 581: ’’masked’’ -> ``masked’’ would be better. \n\nI do not know why it is necessary to have \\propto_{I} in equation 10. Is this a typo? I can certainly see why \\propto is needed in equation 9.\n\n\nThe current draft of this paper seems to be a rather esoteric explanation aimed at experts in discrete diffusion processes or those who are very familiar with the latest developments in them. As a result, newcomers to the topic or general readers interested in the surrounding fields may not find it easy to properly understand the true value of this paper. In order to better convey the value of this paper to a more diverse audience, we would like to make the following recommendations.\n\n> addressing the issues raised in prior work. (Page 1, right column)\n> However, many of these methods still lack rigorous error bounds or scale poorly in high dimensions. (Page 7, left column)\n> However, their results rely on strong assumptions in contrast to our results. Besides, our bounds are simpler and better, in particular with respect to the time horizon. (Appendix A)\n\nThe high-level sketched commentary to these existing studies is no doubt very intuitive and meaningful. However, the current draft does not specify what model assumptions individual previous studies use and what theoretical results they have, and readers will have to individually check the original papers themselves. To be honest, I cannot write down in a positive way what improvements this paper has from some of the previous studies. Therefore, my request is that the authors compile the “model assumptions” and “theoretical results (error bounds)” for each literature in the form of a table so that we can see at a glance the value of this paper when compared to existing studies. In fact, the authors' investigation of the previous studies is so deep and comprehensive that it would be of great value to summarize the results of the previous studies as a unified and improved paper on them.", "questions_for_authors": "I have no additional questions.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "swKcKUUtER", "reviewer": "Reviewer_ymZ8", "summary": "This paper introduces Discrete Markov Probabilistic Models (DMPMs), a novel framework for discrete data generation based on continuous-time Markov chains (CTMCs). The forward noising process follows a Poissonian clock that flips bits randomly, while the reverse process reconstructs the data via an estimated discrete score function.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their very positive feedback, and for finding our paper an interesting contribution to discrete diffusion models from both theoretical and methodological perspectives.\n\n> I wonder if the DMPM can be generalized to systems where each particle has more than two potential states. Can you modify the Poission clock to design a proper forward process? And can the backward process and convergence result be derived with similar approaches in this paper?\n\n\nWe thank the reviewer for the opportunity to address this question. \n\nFirst, it is entirely possible to stay within the hypercube setting for any discrete data by using binary encoding. For instance, colored images can be encoded in 8-bits RGB pixels. Then each image is encoded in {$0, 1$}$^{3 \\times 8 \\times 64 \\times 64}$, if using images of size $64 \\times 64$, for instance. The same approach can be adopted for particles with more than two possible states. \n\nSecond, we believe it should be possible to extend our study to state-spaces like {$0, \\cdots, N$}$^d$, defining the uniform random walk with unit increment as the noising process, and that the backward process and convergence results would be derived very similarly.\n\nHowever, we emphasize that our paper's philosophy is to stay within the binary hypercube, and benefit from various optimizations enabled by such a setting, both theoretically and methodologically. For instance, this yields our regression objective, with the ${L}_2$ loss term (eq. 15), and our discrete denoiser structure, leading to the cross-entropy loss term (eq. 17).\n\n> Assumption 2.2 seems a bit too restrictive [...]. Is this assumption technical or essential to the proof of the convergence?\n\nWe thank the reviewer for the opportunity to clarify this point. We wish to reassure them as we relax Assumption 2.2 soon after introducing it. \n\nInitially, it is used in Theorem 2.3 to derive our simplest convergence bound, which involves computing a Fisher divergence. However, we subsequently employ an early-stopping argument (as detailed from Theorem 2.5 onward) to circumvent its necessity in practice.\n\nThis mirrors what happens in continuous diffusion models, where the data may lie on a lower-dimensional manifold without admitting a density against the Lebesgue measure in the full ambient space. There, too, the same line of arguments involving early stopping are used. \n\nIn practice, the learned model can still assign zero probability to impossible states. For example, on MNIST, we observe that the learned model faithfully recreates handwritten digits, and it is safe to assume that it assigns negligible or zero probability to meaningless states (such as a completely white image). Hence, the assumption does not pose a practical limitation either.\n\n\nWe hope we have successfully addressed the reviewer's questions, and we would like to thank them again for their positive feedback.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I briefly looked at the proofs, and they appear correct based on my reading, but I did not dig into all the details.", "experimental_designs_or_analyses": "The design of experiments is well-structured, with appropriate comparisons to MD4 and DFM.", "relation_to_broader_scientific_literature": "This work builds on continuous-time discrete diffusion models and avoids unstable density ratio estimation.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths: The paper provides strong theoretical guarantees for convergence and avoids density ratio estimation, improving numerical stability.\n\nWeaknesses: Some assumptions might be too restrictive, see questions below.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. The state space is {0,1}$^d$, and so I believe the proposed algorithm will have wide applications in physics. Then I wonder if the DMPM can be generalized to systems where each particle has more than two potential states. Can you modify the Poission clock to design a proper forward process? And can the backward process and convergence result be derived with similar approaches in this paper?\n\n2. Assumption 2.2 seems a bit too restrictive. For example, in a quantum system, two fermions cannot occupy the same state and so for such a system, $\\mu^*((0, 0)) = 0$. Is this assumption technical or essential to the proof of the convergence?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ay8tfzj96H", "reviewer": "Reviewer_9yNo", "summary": "The authors propose the Discrete Markov Probabilistic Model (DMPM), a novel algorithm for generative modeling on the binary data space (bits). The generative model is based on a continuous-time Markov Chain (CTMC) framework with forward processes, which “noisses” the data, and backward processes, which “denoises” the data. The forward process is constructed as a homogeneous Poissonian process that flips the data bits and converges to uniform bits distribution at infinite time. The backward process is modeled as a reverse of the forward process, i.e., via a time-inhomogeneous Markov jump process, which is defined as a discrete analog of the score function. \n\nDuring the training process, a discrete analog of the score function is learned by a neural network. The authors propose three loss functions and their linear combinations. Then, if the score function is properly learned, one can sample from the backward process to generate the data.\n\nThe authors analyze DMPM algorithm consistency by deriving bounds for KL and TV between initial data distribution and the resulting distribution of backward generation processes.\n\nThe proposed algorithm is being compared with state-of-the-art discrete state space Markov chain generative models, MD4 [1] and DFM [2]. The experiments on two datasets were shown: synthetic small dimensional Bernoulli distribution data and black-white MNIST dataset.\n\n## Update after rebuttal\nThe authors mostly addressed my concerns. Since the method is focused on working with the binary data, I think that additional demonstration of its superiority on a real, naturally binary dataset would significantly strengthen the work. As well as the better text clarity to simplify understanding for the wider community.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful remarks and the opportunity to clarify the significance of our theoretical results. Our primary aim is to establish convergence guarantees for discrete generative models, analogous to those in continuous diffusion. This led us to a discrete score function with two key formulations (Propositions 1.1 and 1.2), from which our methodology naturally follows—culminating in strong convergence results, arguably our chief contribution.\n\nAs emphasized in our paper, there is a notable lack of results concerning discrete diffusion models. The closest related work, which improves upon ours in several respects (as detailed in our response to Reviewer fUbX), has only recently been accepted to ICLR [1].\n\nWhile we include experiments to illustrate the method’s potential, we agree with the reviewer that they should be viewed as preliminary—particularly for large-scale or high-dimensional data. We will revise the paper’s conclusion to emphasize that these findings are intended to motivate and guide future empirical studies, not to be a conclusive benchmark. \n\n[1] Ren et al, ICLR 2025\n\n\n> [no] widely recognized large-scale binary datasets...\n\nWe emphasize the hypercube setting’s relevance. First, many real-world large-scale datasets use binary data (e.g., millions of presence/absence edges in amazon products or research papers see [2]), enabling applications like link repair, synthetic-data generation for privacy, or also molecule design. Second, any discrete dataset can be binarized (e.g., 8-bit pixel encoding), and recent developments such as Differentiable Logic Gates Networks [3] show how bit-based methods can excel with neural networks, with the right engineering. We belive our framework provides a strong foundation for bit-based generative models.\n\n[2] Hu et al. 2020, Open Graph Benchmark, Neurips\n\n[3] Petersen et al. 2022, Neurips\n\n> [...] particular case of discrete state space CTMCs...\n\nOur method indeed fits within the class of discrete-state CTMCs. Its novelty stems from exploiting the hypercube in a more specialized way than the general framework in [4]. We can introduce efficient optimization strategies, mirroring approaches like MDLM with the SUBS parameterization or MD4, which leverage the structure of the absorbing kernel.\n\nLike SEDD [5], we parameterize a ratio of density $\\mu_t(y) / \\mu_t(x)$ rather than a reverse density $p_{0 |t}$, which is easier since it is a general value rather than a proper distribution. Furthermore, our objective function is expressed in continuous time, contrary to the loss in [4] which must be extended from discrete time and approximated.\n\nContrary to SEDD, our backward process is characterized by a conditional expectation we exploit in a regression problem using an ${L}_2$ loss term. The discrete denoiser structure is also exploit with a cross-entropy loss term. In contrast, SEDD only derives our entropic regularization loss term (see [eq. (10), 5] and our eq. (16)).\n\n[4] Campbell et al. 2022, Neurips\n\n[5] Lou et al. 2024, ICML\n\n> the paper lacks insufficient hyperparameters testing...\n\nWe first underline the symmetric choice of $T_f$ and $\\lambda$, because of time reparameterization. Consider a time-dependent rate $\\lambda_t$, with $Q_t = \\lambda_t Q$, then $P_t^{\\lambda} = \\exp(Q\\int_0^t \\lambda_s  ds) = P_{\\int_0^t \\lambda_s ds}$. In practice, we fix $\\lambda = 1$ and vary $T_f$, leaving more sophisticated noise schedules to future work.\n\nWe did an initial grid search for $\\lambda, T_f$, validating $T_f = 3$. We thought the results in Figure 1 were convincing. As suggested, we will include an expanded search on MNIST together with various plots in the camera-ready version, like convergence speed to uniform distribution (e.g., on MNIST, we can see the sliced Wasserstein distance between $p_{\\text{uniform}}$ and $p_t$ plateau after $t \\approx 2.5$).\n\n> The FID metric...\n\nThe reviewer makes a fair point, but we note that FID has been successfully used for MNIST (e.g., [6]) and is reliable in our experiments. In addition to FID we report our $F_1^{dc}$ metric, see Appendix D.3. It relies on local geometry to evaluate generative quality/diversity. We remain open to other metrics as recommended, we are confident we will still observe improvements.\n\n[6] Xu et al. 2023, Normalizing flow neural networks by JKO scheme, Neurips\n\n> Beneficial to compare with [...] SEDD uniform\n\nWe train SEDD Uniform with the same settings as the other models. In response to concerns about FID, we report the $F_1^{dc}$ metric. Again, we see clear improvements:\n\n**Table 1: $F_1^{\\text{dc}}\\uparrow$ for different methods**\n\n|steps|10|25|50|100|200|500|\n|-|-|-|-|-|-|-|\n|flip|0.64|0.92|0.93|0.93|0.93|0.92|\n|denoise|0.13|0.67|0.87|0.96|1.00|1.00|\n|SEDD|0.61|0.82|0.88|0.92|0.92|0.92|\n\nWe hope that the previous discussion has satisfied the reviewer. If this is the case, we kindly ask them to consider raising their score, if they feel it is appropriate.", "claims_and_evidence": "The authors argue that the DMPM model matches or outperforms other state-of-the-art Markov chain discrete generative models. However, it seems that the experimental evidence is insufficient to draw such a conclusion.\n\nThe MNIST dataset is too simple and too low-dimensional to judge the generative model performance. Other models (MD4 and DFM) are mainly validated on the text data or much more complex image datasets such as CIFAR-10 or ImageNet 64x64, hence experiments presented in the paper are insufficient. \n\nThere do not appear to be widely recognized large-scale binary datasets that clearly necessitate the advanced CTMC-based approach. Hence, the need for such a powerful model for generative modeling on binary data is not obvious.\n\nTheoretical claims are supported by the derivations in the Appendix.", "methods_and_evaluation_criteria": "As mentioned in the previous section, the datasets chosen for empirical evaluation suit the task solved but seems to be too simple.\n\nThe FID metric for MNIST is somewhat questionable since the Inception network (whose features are used to compute FID) was trained on ImageNet rather than on synthetic or binary data.\n\nCompetitor methods are suitable and are indeed state-of-the-art.", "theoretical_claims": "The derivations in Sections 1.1 and 1.2 have been checked through following the extended derivations in the appendix.", "experimental_designs_or_analyses": "Other than the experimental problems that were already presented in the upper sections I think the paper lacks insufficient hyperparameters testing. \n\n- Time horizon $T_f$ is tested only in the synthetic Bernoulli distribution experiment. In my opinion, more testing regarding time horizon $T_f$ is needed. One can just analyze the forward process resulting distribution and its closeness with uniform distribution without training a diffusion model.\n- I have not found any analysis regarding forward process jump rate $\\lambda$ and its impact on forward process convergence and performance of learned generative models.\n- The visualization of the forward process with dependence on time horizon $T_f$ and jump rate $\\lambda$ would be beneficial for the paper\n- DMPM is the model that has uniform distribution as the resulting distribution of the forward process. Other tested competitors do have delta distribution as the resulting distribution of the forward process. It would be beneficial to compare with other state-of-the-art markov chain discrete generative models that have uniform distribution as the resulting distribution of the forward process, such as SEDD Uniform [4].", "relation_to_broader_scientific_literature": "The authors discuss related literature in a sufficient way.\n\nOverall the proposed method can be viewed as a particular case of discrete state space CTMC [3, 4] generative model with uniform forward process resulting distribution. In that sense paper doesn't deliver that much of a novelty. In my opinion, there is hardly a need for such a powerful model for binary data.\n\nSection 2 provides most of the theoretical novelty for the paper but in my opinion these theoretical results do not deliver impact sufficient  for the publication of the paper.", "essential_references_not_discussed": "Most of the essential literature is discussed with the exception of the MDLM [5] model.", "other_strengths_and_weaknesses": "The paper could be written in a more comprehensive/clear way. Notation is overloaded, and mathematics is sometimes hard to understand. It seems that the Poissonian processes framework could be delivered in a more simple and clear way.\n\nIn addition, some parts are generally hard to understand. For example, lines 133-144 are hard to follow even after taking into account similar derivations in the Appendix. \n\nIt seems that there is a lot of content in the appendix, and it may be beneficial to move some of it to the main text.", "other_comments_or_suggestions": "[1] Shi, J., Han, K., Wang, Z., Doucet, A., & Titsias, M. K. (2024). Simplified and Generalized Masked Diffusion for Discrete Data. arXiv preprint arXiv:2406.04329.\n\n[2] Gat, I., Remez, T., Shaul, N., Kreuk, F., Chen, R. T., Synnaeve, G., ... & Lipman, Y. (2025). Discrete flow matching. Advances in Neural Information Processing Systems, 37, 133345-133385.\n\n[3] Campbell, A., Benton, J., De Bortoli, V., Rainforth, T., Deligiannidis, G., & Doucet, A. (2022). A continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 35, 28266-28279.\n\n[4] Lou, A., Meng, C., & Ermon, S. Discrete Diffusion Modeling by Estimating the Ratios of the Data Distribution. In Forty-first International Conference on Machine Learning. \n\n[5] Sahoo, S. S., Arriola, M., Gokaslan, A., Marroquin, E. M., Rush, A. M., Schiff, Y., ... & Kuleshov, V. Simple and Effective Masked Diffusion Language Models. In ICML 2024 Workshop on Efficient and Accessible Foundation Models for Biological Discovery.", "questions_for_authors": "- It would be great if authors could address the limitations I mentioned in the “Experimental Designs Or Analyses” section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: **Summary.**

The topic of this work is discrete space generative modeling. Specifically, the authors introduce the new class of generative models, the so-called Discrete Markov Probabilistic Models (henceforth DMPMs).

They construct the forward and derive the backward processes (continuous time MCs on the hypercube), which is amenable to efficient training (overcoming a limitation of previous methods).

They obtain theoretical convergence guarantees for DMPMs.

They demonstrate the performance of their approach by experiments (MNIST) against state-of-the-art discrete generative models.

**Strengths.**

* The proposed framework of DMPMs is new.
* Theoretical error guarantees.

**Weaknesses.**

* Performance compared to masked approaches (e.g. MD4, MDLM) is not convincing (5ek8).
* The scale of the experiments (MNIST) is not large enough (5ek8, 9yNo).
* The technical novelty was deemed limited by some (5ek8, 9yNo) and the difference between elements taken from prior work and contributions should be better emphasized (refer to the comments of 5ek8).
* There should be a clearer comparison of the assumptions made in this submission and in prior work (fUbX).
* The clarity of the manuscript could be improved (9yNo).

**Discussion and reviewer consensus.**

There was originally a disparity in the reviewers’ opinion but after the author response, the reviewers were unanimously in agreement that the paper could be (weakly) accepted.

**Additional remarks.**

There was a concern that the state space of the proposed discrete diffusion model is restricted to the hypercube (fUbX, ymZ8, 9yNo). The authors partially address this concern by pointing out that arbitrary discrete data can be handled through binary encoding.

**Overall evaluation.**

I recommend this paper for acceptance if there is room in the program.
Decision: Accept (poster)