動的計画法、モジュラ計算、再帰の関数

最近コードフオースのの問題を解くために三つのテーマがある苦しい所を見ています。 A dynamic programming approach mapping the number of bits set in a number to its transforms to 1, the computation of a quotient mod m, and the ability to obtain recursive behavior without exhausting the stack are concerns. 再帰の数が多くてスタック空間が足りない心配があるがもっと効果的なアルゴリズムを考えられません。それ以外、モジュラに関わる割る処分がちょっと手数になる。The modular division operation requires the modular multiplicative inverse, which can be output by the extended Euclidean algorithm. This algorithm outputs gcd(a,b), which in this case will be the divisor k and the modular operand m. However, it also outputs x and y such that ax+by=gcd. As k and m are relatively prime, this simplifies to kx+ym = 1. Then, taking both sides mod m yields kx mod m + ym mod m = 1 (mod m). bm mod m is trivially 0. Thus, the equation is simply kx=1 mod m, so, given x from the algorithm, the modular multiplicative inverse of k is known. Then, to find (a/k)%m, take (a*x)%m.
参照
以下のサイトの説明に詳細が書かれています。
https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
https://www.geeksforgeeks.org/modular-division/
The intuition behind the algorithm is a pair of recurrence relations and induction.
デバッグ用のログからのユークリッド計算の例を貼り付けます。calling exteuc on 8, 1000000007
extEuc end, retV 1, a 8, b 1000000007, x 125000001, y -1, rdr 0, quot 7
exteuc outputs jmodinv 125000001
calling exteuc on 9, 1000000007
extEuc end, retV 1, a 9, b 1000000007, x 111111112, y -1, rdr 0, quot 8
exteuc outputs jmodinv 111111112
もう一つの難しいところがあった。001の場合に一ビットがありますが変換の数がゼロだからこのケースを変換一の合計から引くのが必要です。

クレジット・デフォルト・スワップの値

最近ブリゴ氏とアルフォンセィの論文
を読んでいるけどよく分からない。the author's discuss a Poisson process for defaults and then bring up a variable "uppercase gamma", which seems to represent the number of defaults up to t. However, exp(-(G(u)-G(t))) seems to be used as both the probability and discount factor, and accounts for cases where the default time tai occurs after u.

確率微分方程式とオプション値計算

最近確立過程とSDEを学びながら停止時間と到達時間の計算式を見ています。難しい所は複数ありますが特に偏微分方程式の作り方とコロモゴロフの前向きと後ろ向き方程式の使い方が問題点だった。それ以外はPx,0(tau>T)=x/sqrt(2*pi*T)はよく分からない。N(0) = 1/2 and N'(0) = 1/sqrt(2pi). Here, though, it would seem that the derivative element of N'(0) is not the time derivative but the position derivative. In addition, there seems to be no relationship between the N(0), N'(0), and Px,t(tau>T)=1-2N(-x/sqrt(T-t)). Actually, though, the argument inside the normal CDF goes to 0 as T->infinity. たぶん微分に間違いが入っている。N'(0) = 1/sqrt(2*pi*T). Thus, the x/sqrt(2*pi*T) value is likely the one term Taylor series about x.

フーリエ変換でオプションの値を表す

最近香港の研究者に書かれたオプションの値計算に関する論文を読んでいます。難しいところはパーセバルの理論、characteristic function, とconvolution. コールオプションの値段はフーリエ変換を元にして書く事は分かりました。  V(S,t)=(1/2pi)exp(-r(T-t))E[INTEGRAL(i*mu-INF to i*mu+INF)(exp(-izx)F(z)dz)], F(z)がオプション値のフーリエ変換です。しかしi*muの役割をよく分からない。次に特性関数の計算式を使うV(S,t)=(1/2pi)exp(-r(T-t))INTEGRAL(i*mu-INF to i*mu+INF)(exp(izx)phi(-z)F(z)dz) なぜ期待値が確率分布ではなくて特性関数を含むがちょっと分かりにくいです。The first expression is obtained via Fourier inversion, but the second is obtained from a questionable application of the Parseval relation. 期待値は確率分布とオプション値のベクトル内積ですが特性関数をフーリエ変換積分の中に入っている事を分からない。The negative sign of z and the extra exponential are difficult to comprehend (it was thought that the Fourier transforms of the probability distribution and the option price would be combined as-is). 残っている問題は方程式21.9のK/(z^2−iz)因数、その上のV計算式の1/2piが欠いている、方程式21.10になぜ積分がなくなる事。