# Stochastic root finding with Mathematica

**URL:** <https://community.wolfram.com/t/stochastic-root-finding-with-mathematica/2755>\
**Category:** Questions\
**Tags:** mathematica, numerical-computation, statistics-and-probability\
**Created:** [July 24, 2014, 4:15am UTC](https://community.wolfram.com/t/stochastic-root-finding-with-mathematica/2755 "2014-07-24T04:15:27Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/szhorvat/32/3531_2.png) [@szhorvat](https://community.wolfram.com/u/szhorvat)\
**Post date:** [July 24, 2014, 4:15am UTC](https://community.wolfram.com/t/stochastic-root-finding-with-mathematica/2755/1 "2014-07-24T04:15:27Z")

</div>

Are there any existing **tools or packages for stochastic root finding with Mathematica** , preferably in more than one dimension?

The classical root finding problem seeks to approximate x so that f(x) = 0, while minimizing the number of times f needs to be evaluated. For example, Newton’s method does this.

The stochastic root finding problem differs in that we cannot compute f(x) directly. We can only compute f(x) + \eta where \eta is a noise term with mean zero. A real-world example would be when f(x) is computed with some Monte Carlo method.

As a toy example, here’s a small Monte Carlo integrator that computes \int\_0^x \sin^2 t \; dt:

```
f[x_] := Sin[x]^2
n = 1000;

fun[x_?NumericQ] :=
 With[{count = Round[n x]},
  N@Total@UnitStep[f@RandomReal[x, count] - RandomReal[1, count]]/n
 ]

```

* * *

Two classes of methods I found are probabilistic bisection (only works in 1D) and the Robbins-Monro method. Robbins-Monro is related to Newton’s method, but it’s highly non-trivial as creating a usable iteration scheme involves making lots of choices, all of which can significantly impact the performance of the method. I am still researching the topic and would be interested in discussing with people who have had to solve similar problems in the past.

---

<div class="post-metadata">

**Author:** ![danl](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/danl/32/41267_2.png) [@danl](https://community.wolfram.com/u/danl)\
**Post date:** [July 24, 2014, 11:13pm UTC](https://community.wolfram.com/t/stochastic-root-finding-with-mathematica/2755/2 "2014-07-24T23:13:37Z")

</div>

I’d try NMinimize[f[x,…]^2, x,…] to see if that gives anything useful. Probably would go with Method-\>“DifferentialEvolution” as the first method to try.

---

<div class="post-metadata">

**Author:** ![szhorvat](https://yyz1.discourse-cdn.com/wolfram/user_avatar/community.wolfram.com/szhorvat/32/3531_2.png) [@szhorvat](https://community.wolfram.com/u/szhorvat)\
**Post date:** [July 25, 2014, 3:31pm UTC](https://community.wolfram.com/t/stochastic-root-finding-with-mathematica/2755/3 "2014-07-25T15:31:43Z")

</div>

It appears that `NMinimize` uses `BlockRandom` with a fixed seed, so any stochastic function passed to `NMinimize` will always produce exactly the same result. I can work around this, just observing how `NMinimize` works. Example:

```
In[20]:= f[x_?NumericQ] := (Sow@RandomReal[]; x^2)

In[21]:= Last@Reap@NMinimize[f[x], x] == Last@Reap@NMinimize[f[x], x]
Out[21]= True

```