{"action":"created","issue":{"url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/145","repository_url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl","labels_url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/145/labels{/name}","comments_url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/145/comments","events_url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/145/events","html_url":"https://github.com/QuantEcon/QuantEcon.jl/issues/145","id":179942217,"number":145,"title":"Loss of significance in Rouwenhorst AR(1) approximation?","user":{"login":"MaximilianJHuber","id":6653641,"avatar_url":"https://avatars.githubusercontent.com/u/6653641?v=3","gravatar_id":"","url":"https://api.github.com/users/MaximilianJHuber","html_url":"https://github.com/MaximilianJHuber","followers_url":"https://api.github.com/users/MaximilianJHuber/followers","following_url":"https://api.github.com/users/MaximilianJHuber/following{/other_user}","gists_url":"https://api.github.com/users/MaximilianJHuber/gists{/gist_id}","starred_url":"https://api.github.com/users/MaximilianJHuber/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MaximilianJHuber/subscriptions","organizations_url":"https://api.github.com/users/MaximilianJHuber/orgs","repos_url":"https://api.github.com/users/MaximilianJHuber/repos","events_url":"https://api.github.com/users/MaximilianJHuber/events{/privacy}","received_events_url":"https://api.github.com/users/MaximilianJHuber/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":2,"created_at":"2016-09-29T03:06:59Z","updated_at":"2016-09-29T12:49:45Z","closed_at":null,"body":"Hi,\r\n\r\nJarda Borovicka gave a problem set containing [Finite state Markov-chain approximations to highly persistent processes](http://www.sciencedirect.com/science/article/pii/S1094202510000128). The authors proof an alternative (polynomial) construction of Rouwenhorst's method in Appendix A. \r\n\r\nI implemented this method and found a performance increase,\r\n`@time rouwenhorst(21,0.99,(1-0.95^2)^(1/2));`\r\n0.000286 seconds (1.25 k allocations: 405.000 KB)\r\n\r\n`@time alternative_rouwenhorst(21,0.99,(1-0.95^2)^(1/2));`\r\n0.000042 seconds (12 allocations: 4.063 KB)\r\n\r\nbut more importantly significant numerical differences. I guess there is a lot of cancellation going on in the recursive implementation in the QuantEcon package. I would suggest a switch to the polynomial construction below, but there is one issue remaining:\r\n\r\nI find that with higher grid sizes, the rows of the transition matrix do not add up to one (and thus I cannot create a QuantEcon-MarkovChain object):\r\n\r\n`(p,s) = alternative_rouwenhorst(21,0.99,(1/0.95^2)^(1/2))`\r\n`[sum(p[i,:]) for i in 1:21]`\r\nAny[0.9999999999999999,1.0,0.9999999999999999,1.0,0.9999999999999999,1.0,1.0,1.0,1.0,1.0,1.0000000000000002,1.0000000000000002,0.9999999999999999,0.9999999999999565,0.999999999994664,0.999999999470605,0.9999999579541284,0.9999973881686884,0.9998775997510598,0.9959209147866287,1.0]\r\n\r\nI would highly appreciate a second pair of eyes on my code!\r\n\r\n```\r\nfunction alternative_rouwenhorst(N::Integer, ρ::Real, σ::Real, μ::Real=0.0)\r\n    p = (1+ρ)/2\r\n    q = p\r\n    Ψ = (N-1)^(1/2)*σ/((1-ρ^2)^(1/2))\r\n    m = μ/(1-ρ)\r\n    \r\n    states = collect(linspace(m-Ψ,m+Ψ,N))\r\n    P = zeros(Float64,N,N)\r\n    \r\n    #for all calculations see http://dx.doi.org/10.1016/j.red.2010.02.002 page 711\r\n    \r\n    for j in 1:N #top and bottom row\r\n        P[1,j] = binomial(N-1,j-1)*p^(N-j)*(1-p)^(j-1)\r\n        P[N,j] = binomial(N-1,j-1)*(1-q)^(N-j)*q^(j-1)\r\n    end\r\n    \r\n    for i in 2:(N-1) #rows in the middle\r\n        P[i,1] = (1-q)^(i-1)*p^(N-1) #first column\r\n        for j in 2:N #other columns\r\n            P[i,j] = (1-q)*P[i-1,j] + q*P[i-1,j-1]\r\n        end\r\n    end\r\n    \r\n    return (P, states)\r\nend\r\n"},"comment":{"url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/comments/250456398","html_url":"https://github.com/QuantEcon/QuantEcon.jl/issues/145#issuecomment-250456398","issue_url":"https://api.github.com/repos/QuantEcon/QuantEcon.jl/issues/145","id":250456398,"user":{"login":"MaximilianJHuber","id":6653641,"avatar_url":"https://avatars.githubusercontent.com/u/6653641?v=3","gravatar_id":"","url":"https://api.github.com/users/MaximilianJHuber","html_url":"https://github.com/MaximilianJHuber","followers_url":"https://api.github.com/users/MaximilianJHuber/followers","following_url":"https://api.github.com/users/MaximilianJHuber/following{/other_user}","gists_url":"https://api.github.com/users/MaximilianJHuber/gists{/gist_id}","starred_url":"https://api.github.com/users/MaximilianJHuber/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/MaximilianJHuber/subscriptions","organizations_url":"https://api.github.com/users/MaximilianJHuber/orgs","repos_url":"https://api.github.com/users/MaximilianJHuber/repos","events_url":"https://api.github.com/users/MaximilianJHuber/events{/privacy}","received_events_url":"https://api.github.com/users/MaximilianJHuber/received_events","type":"User","site_admin":false},"created_at":"2016-09-29T12:49:44Z","updated_at":"2016-09-29T12:49:44Z","body":"You were spot on! Now the results are numerically identical, but the performance gain is gone of course. I will try to get the runtime down, but otherwise the issue is closed."}}
{"actor":{"display_login":"MaximilianJHuber"}}