Gain insights into tackling uncertainty in C# programming. Delve into improving System.Random class with powerful techniques for efficient problem-solving and fewer bugs. Discover new language uses.

csharp.tar.gz

ep10

ep11

ep12

ep13

ep14

ep15

ep16

ep17

bonus01

ep18

ep20

ep21

ep22

ep24

ep23

ep25

ep26

ep27

ep28

ep29

ep30

ep31

ep32

ep33

ep34

ep36

ep37

ep38

There are a lot of problems we face in programming that deal with uncertainty, statistics, and probabilities. Unfortunately, the majority of the general-purpose languages that we use on a daily basis don’t provide a great approach to solving them.

This is particularly the case in C# with the System.Random class. The implementations of this class have been pretty poor for some time. System.Random in C# regularly leads to unexpected, buggy outcomes.

If you’re a C# fan who’s looking for new ways to use the language, then this course is for you. It proposes different approaches to improving the System.Random class, providing a number of powerful techniques that solve problems more efficiently and with fewer lines of code.

Fixing Random: Techniques in C#

In the [previous lesson](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/what-is-the-average-value-as-the-number-of-samples-increases), we showed why our naïve implementation of computing the expected value could be fatally flawed: there could be a "black swan" region where the "profit" function `f` is different enough to make a big difference in the average, but the region is just small enough to be missed sometimes when we’re sampling from our distribution `p`

It looks so harmless. [Photo credits](https://en.wikipedia.org/wiki/File:Black_swan_jan09.jpg).

---

# Continuous Distribution as Special Kind of Discrete Distribution

The obvious solution is to work harder, not smarter: do more random samples when we’re taking the average! But doesn’t it seem to be a little wasteful to be running ten thousand samples to get $9990$ results that are mostly redundant and $10$ results that are incredibly relevant outliers?

Perhaps we can be smarter.

We know how to compute the expected value in a discrete non-uniform distribution of doubles: multiply each value by its weight, sum those, and divide by the total weight. But we should think for a moment about why that works.

If we have an unfair two-sided die — a coin — stamped with value $1.23$ on one side, and $-5.87$ on the other, and $1.23$ is twice as likely as $-5.87$, then that is the same as a fair three-sided die — whatever that looks like — with $1.23$ on two sides and $-5.87$ on the other. One-third of the time we get the first $1.23$, one-third of the time we get the second $1.23$, and one-third of the time we get $-5.87$, so the expected value is :

$\frac{1.23}{3} + \frac{1.23}{3} - \frac{5.87}{3}$,

and that’s equivalent to 
$(2 \times 1.23 - 5.87) \div 3$.

This justifies our algorithm.

Can we use this insight to get a better estimate of the expected value in the continuous case? *What if we thought about our continuous distribution as just a special kind of discrete distribution?*

> In the presentation of discrete distributions we made in this course, we had integer weights. But that doesn’t make any difference in the computation of expected value; we can still multiply values by weights, take the sum, and divide by the total weight.

Our original PDF — that shifted, truncated bell curve — has support from $0.0$ to $1.0$. Let’s suppose that instead, we have an unfair $1000-sided$ die, by dividing up the range into $1000$ slices of size $0.001$ each.

* The *weight* of each side of our unfair die is the probability of rolling that side.
  * Since we have a normalized PDF, the probability is the area of that slice. 
  * Since the slices are very thin, we can ignore the fact that the top of the shape is not "level"; let’s treat it as a rectangle.
  * The width is $0.001$; the height is the value of the PDF at that point.
  * That gives us enough information to compute the area.
* Since we have a normalized PDF, the *total weight* that we have to divide through is $1.0$, so we can ignore it. Dividing by $1.0$ is an identity.
* The *value* on each side of the die is the value of our profit function at that point.

Now we have enough information to estimate the expected value using our technique for discrete distributions.

> Had we made our discrete distributions take double weights instead of integer weights, at this point, we could implement a "discretize this distribution into $1000$ buckets" operation that turns weighted continuous distributions into weighted discrete distributions.

However, we don’t regret making the simplifying choice to go with integer weights early in this series; we’re immediately going to refactor this code away anyways, so turning it into a discrete distribution would have been a distraction.

Let’s write the code:

```C#
 public static double ExpectedValue(
    this IWeightedDistribution<double> p,
    Func<double, double> f) =>
  // Let’s make a 1000 sided die:
  Enumerable.Range(0, 1000)
  // … from 0.0 to 1.0:
  .Select(i => ((double)i) / 1000)
  // The value on the “face of the die” is f(x)
  // The weight of that face is the probability
// of choosing this slot
  .Select(x => f(x) * p.Weight(x) / 1000)
  .Sum();
  // No need to divide by the total weight since it is 1.0.
```
And if we run that:
```C#
Console.WriteLine($"{p.ExpectedValue(f):0.###}");
```
we get
```C#
0.113
```
which is a close approximation of the true expected value of this profit function over this distribution. Total success, finally!

Or, maybe not.

This answer is correct, so that’s good, but we haven’t solved the problem in general.

## The Modifications
The obvious problem with this implementation is: it only works on normalized distributions whose support is between $0.0$ and $1.0$. Also, it assumes that $1000$ is a magic number that always works. It would be nice if this worked on non-normalized distributions over any range with any number of buckets.

Fortunately, we can solve these problems by making our implementation only slightly more complicated:

```C#
public static double ExpectedValue(
  this IWeightedDistribution<double> p,
  Func<double, double> f,
  double start = 0.0,
  double end = 1.0,
  int buckets = 1000)
{
  double sum = 0.0;
  double total = 0.0;
  for (int i = 0; i < buckets; i += 1)
  {
    double x = start + (end – start) * i / buckets;
    double w = p.Weight(x) / buckets;
    sum += f(x) * w;
    total += w;
  }
  return sum / total;
}
```

That works, but take a closer look at what this is doing. We’re computing two sums, sum and total, in precisely the same manner. Let’s make this a bit more elegant by extracting out the summation into its method:

```C#
public static double Area(
    Func<double, double> f,
    double start = 0.0,
    double end = 1.0,
    int buckets = 1000) =>
  Enumerable.Range(0, buckets)
    .Select(i => start + (end – start) * i / buckets)
    .Select(x => f(x) / buckets)
    .Sum();
public static double ExpectedValue(
    this IWeightedDistribution<double> p,
    Func<double, double> f,
    double start = 0.0,
    double end = 1.0,
    int buckets = 1000) =>
  Area(x => f(x) * p.Weight(x), start, end, buckets) /
    Area(p.Weight, start, end, buckets);
```

As often happens, by making code more elegant, we gain insights into the meaning of the code. That first function should look familiar, and we’ve renamed it for a reason. The first helper function computes an approximation of the area under a curve; the second one computes the expected value as the quotient of two areas. 

## Normalized Distribution

It might be easier to understand it with a graph; here we’ve graphed the distribution `p.Weight(x)` as the blue line and the profit times the distribution `f(x) * p.Weight(x)`as the orange line:

In this lesson, we will try to find a better estimate of the expected value in the continuous case.

Better Estimation of the Expected Value

Introduction to System.Random in C#

Introduction to Fixing Random

Fixing Random - Discrete Distribution

Fixing Random - Continuous Distribution

Conclusion

Appendix

Better Estimation of the Expected Value

Continuous Distribution as Special Kind of Discrete Distribution