{"paper_id":"2311.12330","title":"A General Framework for Importance Sampling with Markov Random Walks","authors":["Cheng-Der Fuh","Yanwei Jia","Steven Kou"],"paper_date":"2023-11-21","paper_type":"methodological","paper_url":"https://arxiv.org/pdf/2311.12330v2","page_url":"https://thequant.space/flowcharts/a-general-framework-for-importance-sampling-with-markov-rand/","scores":{"empirical_rigor":4,"math_complexity":8.5,"quadrant":"Lab Rats"},"proposes":{"status":"available","statement":"The paper proposes a general importance sampling framework that twists the observable and latent processes separately using a duo‑exponential tilting family and a link function to directly minimize estimator variance.","quote":"We propose a general importance sampling framework that twists the observable and latent processes separately using a link function that directly minimizes the estimator's variance.","summary":"Although stochastic models driven by latent Markov processes are widely used, the classical importance sampling methods based on the exponential tilting for these models suffers from the difficulties in computing the eigenvalues and associated eigenfunctions and the plausibility of the indirect…","strategy":null},"assumptions":{"status":"available","items":[{"assumption":"The latent process follows a Markov process that may have a finite or continuous state space.","type":"model","stated":"explicit","quote":"If the latent Markov process has a ﬁnite state space, one needs to ﬁnd the eigenvalue of a (non-negative) matrix. However, it becomes a functional eigenvalue problem in an inﬁnite-dimensional space when the underlying latent Markov process has a continuous general state space.","support":"full"},{"assumption":"The link function is chosen within the locally asymptotically normal (LAN) family.","type":"statistical","stated":"explicit","quote":"An optimal choice of the link function is chosen within the locally asymptotically normal family.","support":"full"},{"assumption":"The problem of interest depends only on the observed process Sn (e.g., overflow or bankruptcy events).","type":"model","stated":"explicit","quote":"In most applications, the problem of interest depends only on the observed process (random walk) Sn, e.g., the events Sn ą B (a ﬁxed-time event) or τb ă T (a ﬁrst-passage-time event), where τb “ inftn ě 0 : Sn ą bu.","support":"full"},{"assumption":"The underlying Markov random walk can be represented as Sn = Xn + additive part, with Xn governing the evolution.","type":"model","stated":"explicit","quote":"Although Xn may not explicitly relate to the objective, it still governs the evolution of the quantities of interest. Thus, we call Xn a “latent process” and Sn the “observed process” because it is directly relevant to the quantity of interest.","support":"full"},{"assumption":"The Poisson equation (14) used to construct the link function is solvable and provides a tractable approximation to eigenfunction problems.","type":"statistical","stated":"implied","quote":"Fuh et al.: Importance Sampling with Markov Random Walks 12 Here is a brief road map: (i) We construct a link function in Theorem 2 that achieves the optimal asymptotic variance reduction under the asymptotic normal regime. This link function is based on the solution of the Poisson equation (14), which is much easier to solve than the eigenvalues-eigenfunctions problem (4).","support":"full"}]},"datasets":{"status":"available","items":[{"name":"VAR‑GARCH model for three institutions","provider":null,"kind":"synthetic","access":"unknown","period":null,"universe":"three financial institutions","quote":"Fuh et al.: Importance Sampling with Markov Random Walks 29 We consider a VAR-GARCH model for the return of three institutions. For simplicity, we assume the initial condition is y0 “ 0 and H1 “ W. $ & % yt “ µ ` ρyt´1 ` zt, zt “ H 1 2 t ǫt, Ht`1 “ W ` A d ztzJ t ` B d Ht, (24) where ǫt is the standard normally distributed innovation.","support":"full"},{"name":"Heston stochastic volatility model","provider":null,"kind":"synthetic","access":"unknown","period":null,"universe":null,"quote":"Estimation of PαpST ą bq, where pSt,Xtq follows Heston’s stochastic volatility model. T “ 1 12. Discretization is taken as Euler-Maruyama scheme with ∆t “ 1 120.","support":"full"},{"name":"Tandem queue model","provider":null,"kind":"synthetic","access":"unknown","period":null,"universe":null,"quote":"5.4. Illustrative example (II): Tandem queue Consider a tandem queue model with d stations, with service rates µi and arrival rate µ0 ą 0. We are interested in the probability that the total number of jobs reaches a threshold K before the queue Fuh et al.: Importance Sampling with Markov Random Walks 22 is empty, a well-known example analyzed by Glasserman and Kou (1995) and many others.","support":"full"}],"known":[],"sample":{"start":null,"end":null,"market":null,"asset_class":null,"frequency":null},"data_resolution":"synthetic"},"transaction_costs":{"status":"not_applicable","modeled":"n/a","headline_net_of_costs":null,"detail":null,"quote":null,"source":"front_matter","rule":"R3","candidates":{"front_matter":"n/a","evidence_card":"n/a","evidence_card_quoted":false},"meaning":"the paper reports no trading or execution result"},"results":{"status":"available","evaluation_type":"none","findings":[{"finding":"The proposed estimator achieves logarithmic efficiency.","kind":"theoretical","quote":"We show the logarithmic efficiency of the proposed estimator.","support":"full"},{"finding":"The algorithm (Duo‑V) outperforms competing importance sampling methods in efficiency ratio across probabilities from 10⁻² to 10⁻⁵.","kind":"performance","quote":"The proposed algorithm seems to outperform the others in terms of the eﬃciency ratio, with the probability being around 10´2 „ 10´5.","support":"full"},{"finding":"Variance reduction ratios for Duo‑V reach up to 60.13 with modest computational time, surpassing LD‑ and MD‑based exponential tilting methods.","kind":"performance","quote":"3.44 time consumption ratio 1.03 1.61 1.33 1.08 eﬃciency ratio 1.69 1.79 2.43 3.31 Fouque and Tullie (2002) sd reduction ratio 4.78 8.46 12.71 18.78 time consumption ratio 9.67 36.12 38.49 39.45 eﬃciency ratio 1.54 1.41 2.05 2.99 Duo-CE sd reduction ratio 4.21 10.96 24.70 60.11 time consumption ratio 1.18 2.27 2.91 3.28 eﬃciency ratio 3.88 7.27 14.48 33.20 Duo-V sd reduction ratio 4.33 11.33 24.72 60.13 time","support":"full"},{"finding":"The link function based on the Poisson equation is easier to compute than eigenvalue‑eigenfunction problems while preserving asymptotic optimality.","kind":"theoretical","quote":"Fuh et al.: Importance Sampling with Markov Random Walks 12 Here is a brief road map: (i) We construct a link function in Theorem 2 that achieves the optimal asymptotic variance reduction under the asymptotic normal regime. This link function is based on the solution of the Poisson equation (14), which is much easier to solve than the eigenvalues-eigenfunctions problem (4).","support":"full"}],"reported_performance":null,"out_of_sample":{"method":"none","headline_out_of_sample":null}},"independent_evidence":{"status":"none_found","supports":[],"contradicts":[],"qualifies":[],"compared_with":17,"citations":{"cited_by_in_corpus":0,"by_independent_authors":0,"how_cited":{"used_as_baseline":0,"uses_method_or_data":0,"extends":0,"discusses_findings":0,"mentions":0,"unclassified":0},"independent_papers":[],"scope":"Citations between papers in this corpus only; citations from outside it are not counted."}},"implementation":{"status":"available","public":false,"code_url":null,"note":"No repository presented by the authors as their own was found in the paper. Absence here is not proof that no code exists."},"replication":{"status":"none_found","card":null,"note":"No replication of this paper has been run by thequant.space yet."},"extraction":{"text_source":"fulltext","model":"openai/gpt-oss-120b","version":2,"extracted_at":"2026-11-14T20:00:19Z"},"provenance":{"claims":"Everything here is what the authors state in the paper. Nothing was re-run or reproduced by the platform.","quotes":"Assumptions, datasets, cost detail and findings were extracted by a language model. Every quote is verbatim paper text. Where an item has `support`, \"full\" means every figure in it appears in the quoted sentences and \"partial\" means a figure is stated elsewhere in the paper; items with a figure found nowhere in the paper were discarded.","datasets_known":"datasets.known lists well-known vendors and public datasets by a stable id, found by a dictionary over the full text where the sentence says the data is used; it is independent of the model and covers only names in the dictionary.","flags":"transaction_costs.modeled, results.evaluation_type and results.out_of_sample.method are platform classifications (structured-decision models); see https://thequant.space/score-guide/#penalty-flags","comparisons":"supports / contradicts / qualifies are a language model's reading of two papers' quoted findings, restricted to closely related papers that share no author. They are pointers to read, not verified replications, and coverage is partial.","implementation":"code_url is a repository the paper itself presents as its own (rule-scored, ambiguous cases judged by a model), checked for liveness when it was recorded."},"docs":"https://thequant.space/agents/"}