Learn to solve statistical problems more accurately and efficiently by improving C#'s System.Random class.

Become a C# Programmer

We face several problems in programming that deal with uncertainity, statistics, and probabilities. System.Random class in C# doesn't provide a great approach to solving these problems, since it leads to unexpected, buggy outcomes. 
This module provides us with different approaches to improve the System.Random class. We'll be provided with several 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/definitions), we showed how we could use a simple interface to implement concepts like *"normal distribution"* or *"standard uniform distribution"*. For the next lessons, we’ll leave continuous distributions aside and consider only **discrete distributions**. That is, we have some probability distribution where there are only a small, fixed number of outcomes. Flip a coin, roll three dice and add them together, that sort of thing. You can read up on its definition in the [appendix](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/definitions#discrete-distribution) chapter.

---

## Discrete Distribution
Since we assume the number of possible outcomes of a discrete distribution is small. Therefore, we can enumerate them; the set of possible outcomes is, oddly enough, called the **support** of the distribution.

Some elements might be more likely than others; the ones that happen more often we say have more **weight** than the ones that happen less often. We want to be able to describe the weight of each member of a distribution easily. Also, we do not want to get off in the weeds of representing weights as doubles because double arithmetic has many pitfalls. For the first part of this course, we are going to assume that we can weight the members of a distribution by an integer. When we return to continuous distributions, we will consider the pros and cons of double weights further.

```
public interface IDiscreteDistribution<T> : IDistribution<T>
{
  IEnumerable<T> Support();
  int Weight(T t);
}
```

We are going to require that the weight function accept any value of type `T`. If the value is not in the support, the weight is zero, and if the value is in the support, the weight is a positive integer. We are going to further assume that the support and weights are small enough that the total weight fits into an integer.

> If we divide the weight function by the total weight (as a double) then we have the **[probability mass function](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/definitions#probability-mass-function-pmf)** of the discrete distribution.

Recall that we identified that System.Random.Next has a confusing interface because it is easy to think you are generating numbers from, say, 1 to 6, but actually, are generating numbers from 1 to 5. Let’s make a better interface for this operation using our interface as follows:

```C#
using SCU = StandardContinuousUniform;
public sealed class StandardDiscreteUniform : IDiscreteDistribution<int>
{
  public static StandardDiscreteUniform Distribution(int min, int max)
  {
    if (min > max)
      throw new ArgumentException();
    return new StandardDiscreteUniform(min, max);
  }

  public int Min { get; }
  public int Max { get; }
  private StandardDiscreteUniform(int min, int max)
  {
    this.Min = min;
    this.Max = max;
  }

  public IEnumerable<int> Support() => Enumerable.Range(Min, 1 + Max – Min);
  public int Sample() => (int)((SCU.Distribution.Sample() * (1.0 + Max – Min)) + Min);
  public int Weight(int i) => (Min <= i && i <= Max) ? 1 : 0;
  public override string ToString() => $”StandardDiscreteUniform[{Min}, {Max}]”;
}

```
Finally, we can now do things like `10d6` (`D&D` notation for *"sum ten six-sided die rolls"*) in a natural, fluent style. I would far prefer:

```C#
SDU.Distribution(1, 6).Samples().Take(10).Sum()
```
to
```C#
random.Next(1, 7) + random.Next(1, 7) + random.Next(1, 7) + ...
```

or the equivalent loop we typically see.

### Reasons for Using Lower Bound Inclusive and UpperBound Exclusive
A common defense of "lower bound inclusive, upper bound exclusive" is that it is natural for programmers in C-family languages. It is easier to think of an array or list as indexed from $0$ (inclusive) to the array length (exclusive). We would want to code things like:

```
myArray[Random.Next(0, myArray.Length)]
```
and not get confused and have to say `myArray.Length-1`.  

Well, our answer to that (germane) critique is: once again, we’re reasoning at the wrong level. If we want a probability distribution drawn from elements of an array, then don’t mess around with array indexing and choosing the right random number and so on. That is writing code at the level of the mechanisms, not the business domain. Instead, make an object that represents a distribution of elements chosen from a given array and sample from it!

But we are getting ahead of ourselves; we’ll get to that in an upcoming lesson.

## Discrete Distribution Histogram
Previously we made a little "histogram string" helper extension method that is useful for quickly displaying results in a debugger or console. Let’s do the same for discrete distributions. Moreover, to make sure that we are getting the expected results, we are going to implement it by sampling rather than basing it on the support and the corresponding weights:

```C#
public static string Histogram<T>(this IDiscreteDistribution<T> d) 
  => d.Samples().DiscreteHistogram();
```
```
public static string DiscreteHistogram<T>(this IEnumerable<T> d)
{
  const int sampleCount = 100000;
  const int width = 40;
  var dict = d.Take(sampleCount)
    .GroupBy(x => x)
    .ToDictionary(g => g.Key, g => g.Count());
  int labelMax = dict.Keys
  .Select(x => x.ToString().Length)
  .Max();

  Func<T, string> ToLabel = t =>
    t.ToString().PadLeft(labelMax);

  var sup = dict.Keys.OrderBy(ToLabel).ToList();
  int max = dict.Values.Max();
  double scale = max < width ? 1.0 : ((double)width) / max;

  Func<T, string> Bar = t =>
    new string('*', (int)(dict[t] * scale));

  return sup.Select(s => $"{ToLabel(s)}|{Bar(s)}").NewlineSeparated();
}
```

Let’s try this and roll `1d10`:

```C#
StandardDiscreteUniform.Distribution(1, 10).Histogram();
```

The histogram appears as we’d expect:

```C#
 1|***************************************
 2|***************************************
 3|***************************************
 4|**************************************
 5|***************************************
 6|****************************************
 7|**************************************
 8|***************************************
 9|***************************************
10|**************************************
```

Of course, sometimes we will want to see the weights directly:

```C#
public static string ShowWeights<T>(this IDiscreteDistribution<T> d)
{
  int labelMax = d.Support()
    .Select(x => x.ToString().Length)
    .Max();

  Func<T, string> ToLabel = t =>
    t.ToString().PadLeft(labelMax);

  return d.Support()
    .Select(s => $"{ToLabel(s)}:{d.Weight(s)}")
    .NewlineSeparated();
}
```

We seem to be doing pretty well here. Our implementations of each probability distribution are short and sweet, and each one provides a stone in the foundation for building more complex distributions.

## Implementation
Let's have a look at the complete code for this lesson:

In the [previous lesson](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/definitions), we showed how we could use a simple interface to implement concepts like *"normal distribution"* or *"standard uniform distribution"*. For the next lessons, we’ll leave continuous distributions aside and consider only **discrete distributions**. That is, we have some probability distribution where there are only a small, fixed number of outcomes. Flip a coin, roll three dice and add them together, that sort of thing. You can read up on its definition in the [appendix](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/definitions#discrete-distribution) chapter.

---

# Discrete Distribution
Since we assume the number of possible outcomes of a discrete distribution is small. Therefore, we can enumerate them; the set of possible outcomes is, oddly enough, called the **support** of the distribution.

Some elements might be more likely than others; the ones that happen more often we say have more **weight** than the ones that happen less often. We want to be able to describe the weight of each member of a distribution easily. Also, we do not want to get off in the weeds of representing weights as doubles because double arithmetic has many pitfalls. For the first part of this course, we are going to assume that we can weight the members of a distribution by an integer. When we return to continuous distributions, we will consider the pros and cons of double weights further.

```
public interface IDiscreteDistribution<T> : IDistribution<T>
{
  IEnumerable<T> Support();
  int Weight(T t);
}
```

We are going to require that the weight function accept any value of type `T`. If the value is not in the support, the weight is zero, and if the value is in the support, the weight is a positive integer. We are going to further assume that the support and weights are small enough that the total weight fits into an integer.

> If we divide the weight function by the total weight (as a double) then we have the **[probability mass function](https://www.educative.io/courses/fixing-random-techniques-in-c-sharp/definitions#probability-mass-function-pmf)** of the discrete distribution.

Recall that we identified that System.Random.Next has a confusing interface because it is easy to think you are generating numbers from, say, 1 to 6, but actually, are generating numbers from 1 to 5. Let’s make a better interface for this operation using our interface as follows:

```C#
using SCU = StandardContinuousUniform;
public sealed class StandardDiscreteUniform : IDiscreteDistribution<int>
{
  public static StandardDiscreteUniform Distribution(int min, int max)
  {
    if (min > max)
      throw new ArgumentException();
    return new StandardDiscreteUniform(min, max);
  }

  public int Min { get; }
  public int Max { get; }
  private StandardDiscreteUniform(int min, int max)
  {
    this.Min = min;
    this.Max = max;
  }

  public IEnumerable<int> Support() => Enumerable.Range(Min, 1 + Max – Min);
  public int Sample() => (int)((SCU.Distribution.Sample() * (1.0 + Max – Min)) + Min);
  public int Weight(int i) => (Min <= i && i <= Max) ? 1 : 0;
  public override string ToString() => $”StandardDiscreteUniform[{Min}, {Max}]”;
}

```
Finally, we can now do things like `10d6` (`D&D` notation for *"sum ten six-sided die rolls"*) in a natural, fluent style. I would far prefer:

```C#
SDU.Distribution(1, 6).Samples().Take(10).Sum()
```
to
```C#
random.Next(1, 7) + random.Next(1, 7) + random.Next(1, 7) + ...
```

or the equivalent loop we typically see.

## Reasons for Using Lower Bound Inclusive and UpperBound Exclusive
A common defense of "lower bound inclusive, upper bound exclusive" is that it is natural for programmers in C-family languages. It is easier to think of an array or list as indexed from $0$ (inclusive) to the array length (exclusive). We would want to code things like:

```
myArray[Random.Next(0, myArray.Length)]
```
and not get confused and have to say `myArray.Length-1`.  

Well, our answer to that (germane) critique is: once again, we’re reasoning at the wrong level. If we want a probability distribution drawn from elements of an array, then don’t mess around with array indexing and choosing the right random number and so on. That is writing code at the level of the mechanisms, not the business domain. Instead, make an object that represents a distribution of elements chosen from a given array and sample from it!

But we are getting ahead of ourselves; we’ll get to that in an upcoming lesson.

# Discrete Distribution Histogram
Previously we made a little "histogram string" helper extension method that is useful for quickly displaying results in a debugger or console. Let’s do the same for discrete distributions. Moreover, to make sure that we are getting the expected results, we are going to implement it by sampling rather than basing it on the support and the corresponding weights:

```C#
public static string Histogram<T>(this IDiscreteDistribution<T> d) 
  => d.Samples().DiscreteHistogram();
```
```
public static string DiscreteHistogram<T>(this IEnumerable<T> d)
{
  const int sampleCount = 100000;
  const int width = 40;
  var dict = d.Take(sampleCount)
    .GroupBy(x => x)
    .ToDictionary(g => g.Key, g => g.Count());
  int labelMax = dict.Keys
  .Select(x => x.ToString().Length)
  .Max();

  Func<T, string> ToLabel = t =>
    t.ToString().PadLeft(labelMax);

  var sup = dict.Keys.OrderBy(ToLabel).ToList();
  int max = dict.Values.Max();
  double scale = max < width ? 1.0 : ((double)width) / max;

  Func<T, string> Bar = t =>
    new string('*', (int)(dict[t] * scale));

  return sup.Select(s => $"{ToLabel(s)}|{Bar(s)}").NewlineSeparated();
}
```

Let’s try this and roll `1d10`:

```C#
StandardDiscreteUniform.Distribution(1, 10).Histogram();
```

The histogram appears as we’d expect:

```C#
 1|***************************************
 2|***************************************
 3|***************************************
 4|**************************************
 5|***************************************
 6|****************************************
 7|**************************************
 8|***************************************
 9|***************************************
10|**************************************
```

Of course, sometimes we will want to see the weights directly:

```C#
public static string ShowWeights<T>(this IDiscreteDistribution<T> d)
{
  int labelMax = d.Support()
    .Select(x => x.ToString().Length)
    .Max();

  Func<T, string> ToLabel = t =>
    t.ToString().PadLeft(labelMax);

  return d.Support()
    .Select(s => $"{ToLabel(s)}:{d.Weight(s)}")
    .NewlineSeparated();
}
```

We seem to be doing pretty well here. Our implementations of each probability distribution are short and sweet, and each one provides a stone in the foundation for building more complex distributions.

# Implementation
Let's have a look at the complete code for this lesson:

In this lesson, we will introduce discrete distributions.

Introduction to System.Random in C#

Introduction to Fixing Random

Fixing Random - Discrete Distribution

Fixing Random - Continuous Distribution

Appendix

Conclusion

Introduction to Discrete Distributions

Discrete Distribution