NetLogo Models Library:
Sample Models/Mathematics/Probability/ProbLab/Unverified

Note: This model is unverified. It has not yet been tested and polished as thoroughly as our other models.

(back to the library)

Partition Permutation Distribution

If you download the NetLogo application, this model is included. You can also Try running it in NetLogo Web

WHAT IS IT?

Partition Permutation Distribution is a model built around the idea of a partition function. This function relates between an integer, e.g., 4, and the number of different ways you can break this integer up into groups of integers, where order does not matter. For instance, 4 can be broken up in 5 ways:

(1) 4; (2) 3 + 1; (3) 2 + 2; (4) 2 + 1 + 1; and (5) 1 + 1 + 1 + 1.

Notice that in the above example, the number '1' appeared more often than the number '4.' Why is that? To address this question, this model allows you to repeatedly find partitions of a number and look at the distribution of integers in the partitions.

This model is a part of the ProbLab curriculum. The ProbLab Curriculum is currently under development at the CCL. For more information about the ProbLab Curriculum please refer to http://ccl.northwestern.edu/curriculum/ProbLab/.

HOW IT WORKS

In this model, you choose a target-total, for instance 20, and the code randomly generates addends of the total and adds them to the running-total. These addends are represented in the view, too, as colorful lines that each are as long as the addend it represents. For instance, an addend of 13 will be 13 "patches" long ("patches" are the NetLogo square areas that make up the grid of the view). When the running-total reaches the total, there's been a 'success.' Unlike the actual partition function, this model will not return a value. Moreover, in this model, there is no explicit attempt to exhaust all the partitions. Instead, the randomized procedure keeps adding up the totals randomly. Over many such brute-force addings, a graph shape emerges, and the same shape emerges both for constant totals over many runs and for different totals. The question is why this shape emerges and what this shape means in terms of partitions. So this model uses partitions as an engaging riddle to explore the idea of distribution.

Note: The shape of the graph does not correspond to a simple distribution of all possible permutations, nor to a simple scaling up of such a distribution, such as we would expect the model to create through repetition of previously created partitions. That is, it is not the case that the model chooses randomly from the set of all possible partition permutations of some total. There are two conditions for running this model, depending on the setting of the slider 'diminishing-sample-space?' The following comment refers to the case that the switch is set to 'On.'

The model chooses a first addend out of a space of the whole total, a second addend out of the space of the remainder of the total, and so on. So, the greater addends are "over represented." For instance, for a total of '5,' there is only a single partition with a single addend - the partition "[5]" that includes only '5' as an addend, whereas there are numerous partitions that do not include '5.' So you might expect that '5' would occur very rarely as compared to, say, '1.' However, due to the rationale of the model, '5' actually occurs much more often. Involved here are some subtleties and possible confusions as to what we mean by 'often' -- what our unit of analysis is: Are we counting per addend or per total? Each time a total has been obtained and the model begins creating a new total, there is a 1-out-of-5 chance that the first addend will be '5.' Another way to think of this is that you might expect the partition [5] to occur as often as the partition [1 1 1 1 1], but actually the partition [1 1 1 1 1] occurs 1/ 3125 as often as the partition [5], because we have to get a '1' AND a '1' AND a '1' AND a '1' AND a '1,' whereas for [5], all we have to get is a '5.' Understanding these subtleties may help you develop a more nuanced understanding of statistics experiments.

HOW TO USE IT

When you open the model, numerical and Boolean values will already be set for an easy start, as following: To begin, you can slow down the model with the 'adjust-speed' slider that is on the top-left corner of the view. TARGET-TOTAL is set at 20. Press GO and watch the RUNNING-TOTAL and ADDEND monitors. The addend will be a random number between 1 and 20. Immediately, this addend, say 7, will move over to the running-total, and now there will be a new addend. This new addend will be a random value between 1 and 13 (because the default setting of the switch 'DIMINISHING-SAMPLE-SPACE?' is set so that addends are chosen from the difference remaining up to the total). Say the second addend is 2. So now the running-total becomes 9. The third addend could be 5, so we'd get 14, and so on. Let us say that this run gave us the addends 7 + 2 + 5 + 1 + 4 for a total of 20. The histogram grows one notch up for each of these addends.

Switches: WAIT-AT-FULL? If it is set to 'On,' the experiment will wait briefly each time the target-total has been achieved. DIMINISHING-SAMPLE-SPACE? -- if 'On,' addends will be selected from a sample space that is the size of the remaining difference to the target-total. For example, if the running total of the current adding-up is at 16 and our target-total is 20, then the next addend will be selected from the range 1-thru-4. However, if the switch is set to 'Off,' then the range will always be the target-total, 20.

Sliders: TARGET-TOTAL -- sets the total towards which the program will be adding up the randomly generated values NUM-SUCCESSES -- sets how many times the program will sum up to the target-total you have set

Monitors: RUNNING-TOTAL -- shows how far towards the target-total the adding has gone ADDEND -- shows the current value that has just been generated and added to the running-total SUCCESSES-SO-FAR -- shows how many times the total has been reached. Once this is equal to the NUM-SUCCESSES slider value, the program stops. MEAN #ADDENDS PER TOTAL -- shows how many acceptable addends it took, on average, to fill the target-total that you set, over all the trials PREVIOUS LIST OF INCLUDED ADDENDS -- shows the last completed series of addends up to the target total

Buttons: SETUP -- initialize variables GO -- run the model under your chosen settings. It will run through as many 'num-successes' as you have set. ADD-ONCE -- A single addend is added to the running-total and the histogram is updated. Use this to run the program step by step.

Plots: ADDENDS -- plots the addends as they are randomly selected #ADDENDS PER TOTAL -- plots the number of addends it takes to complete each target-total

THINGS TO NOTICE

When 'diminishing-sample-space?' is set to 'Off,' the addends get smaller as you get closer to the total.

The histogram columns get smaller as you move from left to right.

When 'diminishing-sample-space?' is set to 'Off,' the 'mean addends per total' value converges to the value of 'target-total.' Why is this so? Also, the 'Addends Per Total' distribution slopes down to the right. What can you say of that?

When 'diminishing-sample-space?' is set to 'On,' the 'mean addends per total' value converges to some value. Can you say anything about this value in relation to other settings in the model? Also, the 'Addends Per Total' distribution is normal. Why is that?

THINGS TO TRY

Set the target-total to .5. Run the model over many num-successes, 'diminishing-sample-space?' set to 'On,' and with a high target-total. The 2-column will be 1/2 the height of the 1-column. The 3-column will be 1/3 the height of the 1-column. The 4-column will be 1/4 the height of the 1-column. The 5-column will be 1/5 the height of the 1-column. etc. So we get a '1/n' function. Why is this? Does is work for other target-total values?

Another way to express this relation between the columns is as follows. Say we look at Column 'i.' The relation between the height of Column i and the column immediately to its left (Column 'i - 1') is (i - 1) / i . For instance, the relation between the heights of Column 9 and Column 8 is that Column 9 is 8/9 as tall as Column 8.

Set target-total to 2 and 'diminishing-sample-space?' to 'On.' Set 'num-successes' to 10,000 and run the model until it stops. Compare the value of 'Successes So Far' to the y-value of the 1-Column in the "Addends" plot. You will see that these values are very similar. So over many runs, we expect that the '1' will occur as many times as we have had runs. (See ProbLab model 'Expected Value' for an explanation of how to make predictions of expected values.) This is true for other target-totals -- we chose 2 so as to make this work fast.

Now look at the 'mean #addends per total' you received. It should be very near to 1.5. This is related to our finding, above, that the 2-Column is 1/2 (.5) as tall as the 1-Column and to our expectation to get as many '1's as we have had successes. These ideas combined suggest that we should get .5 as many '2's as we have had successes. So the 1-Column and the 2-Column together are 1.5 as large as the number of successes. This means that there are about 1.5 addends in each total. For the case of a target-total of '3,' we'd need to add '1 + 1/2 + 1/3.' So we'd expect a mean of 1.833 addends per toal. Try this, too!

EXTENDING THE MODEL

Add a monitor that shows the minimum, average, and maximum number of partitions in every run (the number of items is the length of the-short-list). Add plots for these values. What shape do you expect this distribution to have? Will the values change per target-total?

Note that currently we are using this logic:

     set addend ( 1 + random temp-sample-space )

This means that the model chooses addends with an eye to how much space is left up to the total (temp-sample-space is the difference between the running total and the target total). If we removed this, and only asked for "random total", how would the model change, if at all? How would the above extensions change, if at all?

NETLOGO FEATURES

Note that in the above line of code, we set the addend to "1 +...etc." This is due to the nature of the 'random' reporter. The command 'random 3' returns numbers between 0 and 2, and will never return the number 3. So by adding 1, we get the values we actually want. You will come across this often in NetLogo, such as when working with lists. For example, if we had a list named "friends" ["pat" "bob" "joe" "kate"], the 3th value, 'joe,' is called "item 2 friends."

PEDAGOGICAL NOTE

This model is related to other models in the ProbLab suite. Like other models, it looks at the evolution of a distribution that reflects procedures that have random elements. However, unlike other models, the distribution here is never bell-shaped. The greatest learning gain expected to come from working with this model is in comparing it to other models in ProbLab. This comparison should in particular revolve around an articulation, possibly in general terms, of what precisely about this model makes a bell-shaped distribution unlikely.

This model is related in an interesting way to 9-Block Stalagmite. In that model, the distribution of permutations reflects the sample space of all possible permutations. But in this model, the distribution does not reflect the sample space directly (see introduction, above).

Also, the model is related to the Attempts-Until-Success histogram in Prob Graph Basic and to the Distances to Whites histogram in Shuffle Board. Actually, those two histograms behave similar, whereas the histogram in this model behaves differently. Understanding this difference may sensitize you to "graph families." Just because all these graphs decrease monotonously, it does not necessarily mean that they describe the same or related functions.

CREDITS AND REFERENCES

This model is a part of the ProbLab curriculum. The ProbLab Curriculum is currently under development at Northwestern's Center for Connected Learning and Computer-Based Modeling. . For more information about the ProbLab Curriculum please refer to http://ccl.northwestern.edu/curriculum/ProbLab/.

HOW TO CITE

If you mention this model or the NetLogo software in a publication, we ask that you include the citations below.

For the model itself:

• Abrahamson, D. and Wilensky, U. (2004). NetLogo Partition Permutation Distribution model. http://ccl.northwestern.edu/netlogo/models/PartitionPermutationDistribution. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

Please cite the NetLogo software as:

• Wilensky, U. (1999). NetLogo. http://ccl.northwestern.edu/netlogo/. Center for Connected Learning and Computer-Based Modeling, Northwestern University, Evanston, IL.

COPYRIGHT AND LICENSE

Copyright 2004 Uri Wilensky.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License. To view a copy of this license, visit https://creativecommons.org/licenses/by-nc-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Commercial licenses are also available. To inquire about commercial licenses, please contact Uri Wilensky at uri@northwestern.edu.

This model was created as part of the projects: PARTICIPATORY SIMULATIONS: NETWORK-BASED DESIGN FOR SYSTEMS LEARNING IN CLASSROOMS and/or INTEGRATED SIMULATION AND MODELING ENVIRONMENT. The project gratefully acknowledges the support of the National Science Foundation (REPP & ROLE programs) -- grant numbers REC #9814682 and REC-0126227.

(back to the NetLogo Models Library)