0 Research application/design study Matthew Hull, Vivian Pednekar, Hannah
Murray, Nimisha Roy, Emmanuel Tung, Susanta Routray, Connor Guerin, Justin
Chen, Zijie J. Wang, Seongmin Lee, Mahdi Roozbahani, and Duen Horng Chau are
with Georgia Institute of Technology. Email: {matthewhull $|$ vpednekar3 $|$
hmurray9 $|$ nroy9 $|$ tunge $|$ sroutray $|$ cguerin6 $|$ chen3001 $|$ jayw
$|$ seongmin $|$ mahdir $|$<EMAIL_ADDRESS>.

#  : Automatic Grading of D3 Visualizations

Matthew Hull  Vivian Pednekar  Hannah Murray  Nimisha Roy
Emmanuel Tung  Susanta Routray  Connor Guerin  Justin Chen
Zijie J. Wang  Seongmin Lee  Mahdi Roozbahani  and Duen Horng Chau

###### Abstract

Manually grading D3 data visualizations is a challenging endeavor, and is
especially difficult for large classes with hundreds of students. Grading an
interactive visualization requires a combination of interactive, quantitative,
and qualitative evaluation that are conventionally done manually and are
difficult to scale up as the visualization complexity, data size, and number
of students increase. We present , a first-of-its kind automatic grading
method for D3 visualizations that scalably and precisely evaluates the data
bindings, visual encodings, interactions, and design specifications used in a
visualization. Our method enhances students’ learning experience, enabling
them to submit their code frequently and receive rapid feedback to better
inform iteration and improvement to their code and visualization design. We
have successfully deployed our method and auto-graded D3 submissions from more
than 4000 students in a visualization course at Georgia Tech, and received
positive feedback for expanding its adoption.

###### keywords:

Automatic grading, D3 visualization, large class, Selenium, Gradescope grading
platform

Our auto-grading workflow for D3 visualizations (1) first renders student’s
plot in a web browser and automatically interacts with it (e.g., hover,
click); (2) extracts gradable elements (e.g., data points, visual encodings,
plot dimensions) from the plot’s backing code; (3) generates a student-
specific solution and compares it with student’s plot to identify issues; and
(4) provides feedback to help student improve their design.

##  1 Introduction

Fig. 1:  flexibly evaluates students’ design variations. Here, we show two
example student designs (on the leftmost) that use different plot sizes,
fonts, mark types, colors, axis formats, and bar chart orientations. handles
these different design variations by evaluating their underlying HTML
structures.  When a visualization is rendered,  the HTML structure is
extracted, and  a tailored student-specific solution is generated for
comparison with the student submission.

D3 [12] is in wide use and remains a highly popular choice in data
visualization courses [1, 3, 4, 2, 5, 6] due to its immense flexibility and
foundational stature in the visualization community[29].

Manually grading D3 [12] visualizations is a challenging endeavor, and is
especially difficult for large classes with hundreds of students. Even for a
“simpler” interactive bar plot visualization, manually grading it usually
requires a combination of interactive, quantitative, and qualitative
evaluation, with tasks such as verifying the correctness of data bindings and
visual encodings, testing interactive elements and actions work as intended
(e.g., whether tool-tip displays upon mouse-hover), and determining if a
visualization’s overall layout and spacing is appropriate. However, such
“simple” evaluation tasks quickly become daunting as the visualization
complexity and data size increase. For a large class with hundreds or a
thousand students, such manual grading becomes extremely tedious [31]. When
evaluating visualizations on a large scale, it is impractical to exhaustively
evaluate and interact with all plotted data. Furthermore, manual grading
presents the logistic challenge of requiring congruence between student and
grader environments. This necessitates the recreation of the student’s
environment or in some cases, modification of student code by the grader to
run the visualization, resulting in a cumbersome grading process, especially
for large classes with many students. To address the common challenges in
grading D3 visualizations, we contribute:

  * •

, the first-of-its-kind automatic grading approach for D3 visualizations that
scalably and precisely evaluates the data bindings, visual encodings,
interactions, and design specifications used in a visualization (Fig. :
Automatic Grading of D3 Visualizations). Our method avoids a rigid “one-size-
fits-all” approach to grading, by offering a novel flexible way that provides
students with tailored feedback while supporting their design freedom in
developing visualizations (Fig. 1), accepting variations in size, font, mark
type, color, axis format, orientation and more, provided that students’
designs follow the same high-level structures, so that “gradable” elements may
be extracted for grading (Sec. 5.3). Our approach utilizes Selenium’s [44]
browser automation package to compose rich interaction sequences, known as
Action Chains[45], that facilitate the evaluation of common user interaction
(Sec. 5.4). As a result, our auto-grader can efficiently and automatically
interact with and grade interactions and “hidden” visualization elements that
display after a complex sequence of interactions (Fig. 3). Without our
approach, such grading would need to be tediously performed for every
student’s submission. To promote easy adoption of our auto-grading approach by
visualization instructors, we have open-sourced it on GitHub at
https://github.com/poloclub/visgrader, which has included the auto-grader
source code, a series of Jupyter Notebooks that explain how we extract and
grade elements, an example visualization that demonstrates how auto-grading is
applied, and a 30-second summary video that provides a high-level overview of
the approach and its impacts111 video: https://youtu.be/XnTfiAiYLNM.

  * •

Large Scale D3 Auto-Grading. has been used to grade more than 72,000
submissions from more than 4,000 students for four semesters222Fall 2021,
Spring 2022, Fall 2022, Spring 2023 in Georgia Tech’s CSE 6242 Data and Visual
Analytics333https://poloclub.github.io/#cse6242 course[6]. Each recent
semester sees an average of 1,100 students from both undergraduate and
graduate programs in both on-campus and online offerings and received positive
feedback from both students and instructors. Our auto-grading approach has
enhanced students’ learning in multiple ways, enabling them to receive instant
feedback to improve their work, learn best coding practices, and reduce
configuration errors. Our approach has also benefited the instructional staff,
such as reducing teaching assistant (TA) grading hours and allowing more time
to provide qualitative feedback (Sec. 7).

##  2 Background and Related Work

Automated testing tools[18] for software have been in widespread use for many
years and derivatives of this methodology have been incorporated into
automated grading or “auto-grading” of introductory programming
assignments[21, 48] in Computer Science courses.

###  2.1 Auto-grading Student Programs

Typical auto-graders can check for syntax errors[38] and can generate feedback
[17] that students can access in an effort to improve their implementation and
achieve a higher score. There exists evidence that automated adaptive
feedback[9] can assist in developing stronger programming competencies in
large environments. These approaches generally are well-suited toward problems
of evaluating a program’s ability to successfully execute or its output value
and we refer to these as “value/output checking” auto-graders. An example
might be a student writing a simple calculator program in an introductory
programming class would implement a set of functions e.g., add(x,y) or
subtract(x,y) and the corresponding auto-grader would then call add(3, 4) or
subtract(10,9) and check the result. A more sophisticated auto-grader might
check the output of a machine learning model, e.g., a student could implement
a Decision Tree model that the auto-grader will supply some unseen data to
ensure its accuracy falls within a certain range.

However, a D3 visualization is decidedly different from a classic computer
program in the way that it is intended more for data communication and
interaction, requiring a different approach for evaluation. Furthermore, even
students implementing the same visualization (e.g., a bar chart) may create a
great variety of different designs that use different colors, plot sizes, axis
formats, and more. A trivial “value-checker” auto-grader cannot evaluate a
submission fairly if it expects only a single color or size. If an auto-grader
simply checked the x,y coordinates of a plotted datum, it would exist at
different positions due to the plot size specified by the student. Similarly,
comparing pixels of rasterized visualizations would lack flexibility for
accommodating minor deviations when the submission does not precisely match.

###  2.2 Auto-grading Complex Visualization

To the best of our knowledge, we have not seen any work to date that can auto-
grade a D3 visualization. Thus, we discuss related methods for finding and
correcting mistakes, and extracting and identifying the underlying structure
of a D3 visualization, a critical component for developing automated grading
methods.

####  2.2.1 Correcting Mistakes in a Visualization

Currently, there are some tools and frameworks that can automatically generate
or evaluate visualizations that are built for Vega-Lite[39], a declarative
visualization framework built on D3. McNutt et al. [32] adapt metamorphic
software testing methods[43, 40] to surface potential perceptual misreadings
in a Vega-Lite visualization. In their work, they devise methods to verify
that the visualization output is consistent against a range of inputs, e.g.,
shuffling the input data for a visualization and validating that the plotted
data does not change. LitVis [49] is an IDE plugin that provides live feedback
to better align a visualization design against specification schemas. Draco
[35] is a visualization constraint representation system that can be used to
auto-complete design guidelines[36] and support the creation of automated
visualization tools. Chen et al. created VizLinter [13], a tool that extends
and refines Draco’s constraint system to detect errors in existing
visualizations and can suggest fixes or correct errors. While Chen et al.
suggest a potential use for VizLinter in educational settings, they do not
discuss any uses of their tool in real-world visualization education
scenarios.

Hopkins, et al. released VisuaLint [23], another linter for Vega-Lite
visualizations that can display in-situ errors within a visualization to aid
developers in quickly discovering mistakes. They also discuss a possibility of
incorporating their tool for educational purposes but do not give concrete
examples of this. LitVis, VizLinter, and VisuaLint are limited to static
analysis of visualizations and do not incorporate functionality that will
analyze or evaluate the interactivity in a visualization.

However, D3 visualizations can incorporate rich interaction, including drag-
and-drop, hover, filtering, etc. For this reason, these linters are not
sufficient for observing and grading the changes that occur to a visualization
when the user interacts and explores. Additionally, we do not find any tools
that find mistakes or suggest corrections to D3 visualizations. One reason for
this may be due to D3’s lower level API that does not retain the same
declarative characteristics that higher level tools offer, e.g., Vega-Lite,
and requires deconstruction of the underlying components in order to analyze
them.

####  2.2.2 Analyzing a D3 Visualization’s Structure

Harper and Agrawala have produced work on deconstructing D3 visualizations so
that they may be re-styled [22]. Their approach entails traversing the
Document Object Model (DOM) subtree of the visualization and recovering the
data, marks, and internal mappings of a D3 visualization. They test for linear
mappings between data and marks through use of linear regression or
categorical mappings if linear data do not exist. Hoque and Agrawala extend
this approach with a search engine[24] that leverages the deconstruction
methods so that a user may search for the visual style of a D3 visualization.
The search engine tool is limited to only capturing linear mappings, such as
marks encoded linearly on an axis and cannot capture complex layout
generation, such as a node-link diagram using force-directed layout.

In our Data and Visual Analytics course[6], we expose students to a variety of
visualization categories and therefore require a grading approach that has the
capability to generalize beyond visualizations that use only linear vertical
and horizontal axes.

Our auto-grading approach is inspired by Harper and Agrawala’s D3
deconstruction methods [22]. We further extend these methods and extract the
components of many different types of visualizations, including those without
pure horizontal and vertical axis layout, such as a visualization of geo-
spatial data, a node-link diagram, or those that non-linear scaling, e.g.,
logarithmic or square-root scales. Since D3 visualizations are browser-based
[12], we leverage the cross-browser compatible Selenium WebDriver[44] software
package for automated browser testing and adapt it to interact with
visualizations, as a real user would. This gap analysis motivates our the
development of our auto-grader design and we present the respective design
goals in the the next section.

##  3 Design Challenges

Our goal is to build an auto-grader that scalably and precisely evaluates many
types of D3 visualizations. Based upon our 10 years of experience teaching and
grading D3 visualizations and our survey of related work in Section 2, we
identify four design challenges (C1 \- C4).

  1. C1.

Increased Iterations of Detailed Feedback. While D3 is highly expressive in
terms of what can be built, there is a steep learning curve for new D3
developers. [33] Students may face implementation challenges[10] and need
multiple rounds of feedback as they work to complete their D3 visualization
implementation. We find that they regularly engage the instructor staff on the
class forum and during office hours to ask questions or request feedback while
they develop their visualization. There are limits to what feedback can be
given since we do not have the resources to fairly or accurately “pre-grade” a
submission. We need a systematic approach to frequently give students feedback
on their progress and information on their submission grade that will decrease
confusion and set clear expectations [42, 20].

  2. C2.

Scaling to Large Class Sizes. Our Data and Visual Analytics course has been
simultaneously offered to on-campus undergraduate and graduate students, as
well as to graduate students in two Online Master of Science degree programs
in Computer Science444https://omscs.gatech.edu and
Analytics555https://pe.gatech.edu/degrees/analytics at Georgia Institute of
Technology. As a result, we have increased enrollment from a few hundred
students in the course’s earlier offerings to more than 1,100 students in each
recent semester [8]. At such a large scale, even a “simple” manual evaluating
task taking only, say, 5 minutes to complete results in almost a hundred hours
of total grading time [31]. Thus, we need a new, scalable approach to evaluate
students’ deliverables while offering the same depth and quality of
instruction.

  3. C3.

Accepting Variations in Visualization Designs. When we design a visualization
assignment, the instructions include required data, visualization type,
structure, and interactive features. We do not attempt an exhaustive
description or expect that students will submit an implementation that exactly
matches the examples we provide. This challenge requires implementing an auto-
grader that is far more robust than the “value/output-checking” auto-
graders[17, 38] by accounting for variations between student submissions.

  4. C4.

Grading Interactivity. D3 visualizations may be designed to incorporate a
myriad of interactive features, ranging from simple actions such as hover and
click, to more complex actions such as filtering a dataset, drag-and-drop, or
displaying a subplot that is dynamically generated upon user selection. Thus,
our course has a key goal of teaching the design and development of richly
interactive visualizations and to provide feedback and evaluation of those
implementations. However, existing techniques that detect mistakes were
designed for static visualization components [13, 23] and manually grading
every student’s submission requires extensive time and is error prone [31]. We
need to develop a new automated approach that evaluates interactive features
in a visualization that is scalable, being able to execute quickly for the
large number of student submissions (C2) and provide them with instant
feedback.

Fig. 2: The Gradescope interface allows students to rapidly improve their D3
implementation by quickly giving feedback on four categories of test cases
that evaluate the visualization based on an assignment rubric: (1) advisory on
layout and required components; (2) mark appearance; (3) scale and data
positioning; and (4) interactivity. Additionally, students may download a
screenshot of their visualization to understand what the grader “sees” during
grading. Fig. 3: Selenium Action Chains enable browser automation for complex
tasks. uses Action Chains to interact with a visualization by composing user-
driven events, e.g.,  Moving the mouse across the visualization or  hovering
over a data point. Each interactive event drives a change in the DOM that is
captured by our auto-grader.

##  4 : Automatic D3 Grading

Based on the identified design challenges (Sec. 3), we distill the following
key design goals (G1-G4) for , an auto-grading method for D3 visualizations
used in large scale instructional settings.

  1. G1.

Rapid and frequent feedback interface. We use the Gradescope online assessment
platform [19] to host our D3 auto-graders. This popular platform is used by
over 2,600 universities for grading a variety of assignments: programming,
quizzes, worksheets, and exams. Gradescope enables the instructional staff to
configure programming assignments that allow students to submit their answers
for an unlimited number of times during the assignment window (Fig. 2),
affording students with an opportunity to incrementally improve their design
over time through several iterations of submission and viewing feedback
(C1)[42], e.g., a point score and textual description describing instances
where they did not meet the assignment rubric. (Sec. 5.1)

  2. G2.

Distributed auto-grading for thousands of students. Our goal is to scale
instruction by further leveraging the capability of the Gradescope platform to
support larger classes (C2) for D3 assignments, thereby requiring fewer TAs to
support and grade student submissions (Sec. 5.2) and allocating more TAs
toward higher quality student interaction. (Sec. 7.1.2)

  3. G3.

Logic that preserves design flexibility. Our goal is to avoid enforcing a
single rigid solution that reduces the student’s design autonomy. Instead, we
encourage students to make their own design choices when building a D3
visualization with respect to colors, layout, chart size, visual encodings,
etc., and flexibly grade (C3) the student’s implementation in a manner that
does not penalize a submission that does not exactly match the example
solution design(s). (Sec. 5.3)

  4. G4.

Evaluation of interactive visualizations. Our goal is to develop an auto-
grader that evaluates rich interactivity and functions as a real user would
(C4). To accomplish this, the auto-grader must incorporate two high level
functionalities (Sec. 5.4):

     * •

Perform complex interactions, such as hovering over or clicking on a an
element, drag-drop, filtering, scrolling, etc.

     * •

Measure how the interaction effects the visualization, e.g., changes to the
fill color, x/y position of an element.

##  5 Auto-grading Method

In this section, we outline the implementation and function of and demonstrate
how it meets the four design goals (G1 \- G4).

###  5.1 Student Feedback and Test Cases

####  5.1.1 Student Submission Workflow

For a D3 assignment, students upload visualization source code files to
Gradescope and can generally view feedback on their submission within 30
seconds. Gradescope hosts the auto-grader and runs by rendering the
visualization in a “headless” version of Google Chrome’s web browser and
scores the submission each time the student uploads a new version. The final
grade is based on their highest scoring submission in an effort to encourage
students to continue to improve their work without any imposed limit on
submission frequency or running time limits. When the auto-grader scores a
student submission, it runs a suite of test cases that correspond to the
rubric requirements and returns the total number of points earned along with
textual feedback regarding which test cases passed or failed (Fig. 2) The
auto-grader also captures an image of the visualization rendering and offers
it to the student for download. This screenshot allows the student to evaluate
how their visualization is “seen” by the auto-grader and could aid in critical
error capture, e.g., a blank screenshot indicates that a critical error
prevented the visualization from being rendered at all.

####  5.1.2 Test Case Categories

In general, we use 4 categories of test cases for grading:

  1. 1.

Advisory on Layout and Required Components (Fig. 2.1). Advisory test cases are
used to detect the visualization layout by extracting the dimensions,
transformations, and margins as well as detecting the required components.
Layout detection test cases form the assumptions that uses for subsequent
testing for axis scaling and data positioning. Required component test cases
will alert the student if an element is missing, e.g., a missing x-axis.

  2. 2.

Mark Appearance (Fig. 2.2). Mark appearance test cases grade any required data
sorting, sizing, and colors. A data sorting test might evaluate if the bars in
a bar chart are ordered by height, while a sizing test might check if the bars
all contain a constant width. A color test could be used to ensure that all
data for a certain grouping value are colored correctly (e.g., same color for
all points on a scatterplot).

  3. 3.

Scale and Data Positioning (Fig. 2.3). Scale and data positioning test cases
use the assumptions gathered in an advisory test case to grade the domain and
range of axes and check that data are positioning correctly for an expected
scaling function.

  4. 4.

Interactivity (Fig. 2.4). Interactivity test cases perform interaction that
results in a change to the DOM and then grade the result. This category is
frequently implemented as a composition of interactivity testing and a
subsequent mark appearance or scale and data positioning test.

###  5.2 Large Scale Auto-Grading Workflow

We discuss our workflow for large-scale auto-grading and how this approach can
be adopted for use in online and in-person offerings of a course, since most
of the work for a D3 assignment is done outside of the classroom instructional
periods.

####  5.2.1 Easy Adoption

’s architecture makes it easy for someone to adopt and implement their own D3
auto-grader, since the majority of the implementation involves writing unit
tests, a typical skill for most computer science educators. Many of the test
cases may be re-used with small modifications, thereby reducing the overhead
on instructors writing test cases for a new visualization. e.g., layout and
required component test cases (Sec. 5.1.2.1) may be re-used since the specific
required elements and layout information are abstracted into a rubric
configuration YAML file (Sec. 6.3). Mark appearance test cases (Sec. 5.1.2.2)
can be re-used with small modifications between similar designs, such as
grading appearance of  elements contained in (Fig. 4.1–3). In a similar
manner, the axis scale test cases (5.1.2.3) for the line chart shown in (Fig.
4.2) were used as a template for the line chart shown in (Fig. 4.3) On
average, we write 28 test cases per visualization using Python to capture the
results and use Gradescope’s API for score tabulation and formatting feedback.

####  5.2.2 Distributed Grading

can be widely distributed and easily maintained using Gradescope’s integration
with Docker. Each auto-grader is “containerized” and distributed as a Docker
image and referenced by Gradescope from Dockerhub. When an auto-grader needs
revision, the modified source code is packaged by re-building the Docker image
and pushing the new version to DockerHub. Gradescope presents per-assignment
dashboards for the instructor staff to see how many students have submitted
and how many times the student has submitted on a particular question. In more
difficult troubleshooting scenarios, the instructor can view specific error
messages that are hidden from student’s view to avoid divulging the solution
or specific test case implementations. Instructors can also establish a bash
terminal session into the student’s auto-grader session if needed. At the
close of the submission period, the final grading can be exported from
Gradescope system into a variety of supported Learning Management Systems
(LMS), such as: Blackboard [11], Brightspace (D2L)[15], Canvas[27],
Moodle[34], and Sakai[41]. This enables instructors to securely push grades
directly to the LMS and prevents any errors that might occur when scoring by
hand.

####  5.2.3 Parity between Development and Grading Environments

The auto-grader also helps prevent critical discrepancies that can exist
between the student development environment and the grading environment that
can affect the accurate scoring of a student submission. We ensure this by
taking several steps to ensure that the student is developing their
visualization using the same web browser version, libraries, and file
structure that the auto-grader will use. We also provide assignment templates
that contain the same file directory structure that mirrors what the auto-
grader will use with respect to the location of any data files and the
D3-library references. These measures assist in curtailing auto-grader
tampering and reduce stress for the students as they are only required to
submit the HTML, JavaScript, and CSS source files that they have edited.

###  5.3 Flexibly Grading Student Design

We describe how flexibly grades a student’s design by capturing key attributes
of a student’s submission such as the chart size, layout, colors, and visual
encodings (Fig. 1.2) and evaluates the design with respect to the rubric. One
of our key contributions is the novel use of adapting such existing browser-
automation for visualization auto-grading, which has not been done before.
Such adaptation goes beyond conventional ways of developing test cases for
websites. For example, the test cases need to be carefully designed to allow
for a great variety and combinations of student design choices, which is not
typical for conventional test suites where test developers are able to pre-
determine and control elements they wish to test for (e.g., position or
scaling of a UI element derived from a requirement specification.) We also
extend our test cases beyond basic fault detection to provide useful feedback
that guides student improvement.

####  5.3.1 Capturing Elements

To initiate element capture, Harper and Agrawala’s deconstruction method [22]
requires that the user click on the visualization and the subsequent event is
captured through JavaScript code injection and initiates a crawl of the DOM
sub-tree to find the respective chart elements. Instead of intercepting a
user’s click event, we differ from this approach by specifying a structure
requirement following a predictable pattern convention found in many example
D3 visualizations. We explicitly state in the assignment requirements (Sec.
6.3) which elements should contain certain  attributes or be placed within a
grouping element, the same approach that is used in this example from the
official D3 documentation,666https://observablehq.com/@d3/histogram#Histogram
all of the  elements that represent bars in a bar chart are placed under one
element. For each D3 visualization, we present the students with a required
chart structure and element ids that they must adopt in their implementation
(Fig. 1.2). For a bar chart, a student would group all of the  elements
representing bars in a group tag with an id of “bars” .

During auto-grading, we use Selenium WebDriver’s API[45] to locate and extract
the HTML elements using this structure. The Selenium WebDriver API stores all
of the attributes and properties of the captured element as an object that can
be queried during testing. D3 visualization are typically comprised of
scalable vector graphics (SVG) elements and can be mixed with HTML. As a
result, we can write a unit test that tests any SVG or HTML attribute, e.g.,
fill color, stroke color, x,y position, CSS classes.

####  5.3.2 Capturing Scales, Axes

During auto-grading, it is necessary to know if a datum is plotted correctly
for a given scale type. For example, if the visualization contains linearly
scaled data, we need to know that datum’s position is also scaled linearly.
The same also applies for non-linear displays of data, such as when a
logarithmic scale is used. Other visual encodings independent of Cartesian
coordinate space could also be employed in a visualization, such as using a
quantile scale to generate color gradations for a data mark. Since D3 offers
such a wide variety of scale types and methods for displaying chart axes, we
need to evaluate both the scale domain and range, in order to evaluate how a
mark should appear in a visualization.

The student’s choice for a D3 scale function call is not known to us, and we
do not attempt to find it (i.e., we do not listen for API calls, use regex or
parse JavaScript code). For flexibly grading a scale used in a visualization,
we must account for different design choices. For example, a test case that
checks for missing data points in a line chart (Fig. 1.1, design 2) would
first identify the domain and range of the horizontal scale that the student
uses (“year”). Then we match the range of our solution’s scale with the
student’s, so that the test case can compute the expected positions of all
data points (in student 2’s visualization) to check for missing ones. In our
auto-graded D3 assignments, we specify which scale type that must be used but
do not mandate any size dimensions or colors (Sec. 6.3). Instead, we might
instruct the student to: “use a linear scale with a domain of values that are
represented in the provided data”, or “use a quantile scale to generate the
color scheme based on the average rating”.

###  5.4 Performing and Grading Visualization Interaction

Auto-grader flexibility is also extended to the interactive elements in a
visualization and meets our goal of designing interactive data visualizations
and promoting exploration of the presented data.

We observe that interaction events within a browser-based visualization result
in changes to the DOM. If a student is building a visualization that
implements a JavaScript function that intercepts a mouseover event and changes
the fill color of some target element, then we can analyze the DOM structure
and query the fill color of the target element before and after the mouseover
event occurred to test if the interaction is correct. The Selenium WebDriver
API allows specification of user-actions that interact with a website in a
natural way, supporting all interactions that a human user may perform. The
same mouseover event is accomplished in Selenium by calling move_to_element(),
a function that moves the mouse over a target element. Following the
mouseover, we query the css attributes of a target element by calling
value_of_css_property(’fill’) without enforcing a specific color (Fig. 3-A2).
In a similar way, we can replicate click events by calling click() after
moving the mouse over the desired element (Fig. 3-A3). Some other interaction
types include: hover, click, drag-and-drop, filtering, displaying pop-overs,
hidden elements, sub-charts, and tool-tips. Some interactions can only be
accomplished by following a specific sequence of events. We use Selenium’s
Action Chains [45] API to compose sequences of interactions for arbitrary
events, enabling the composition of rich interaction sequences that can be
used to thoroughly interact with a visualization. Fig. 3 A1-A7 demonstrates a
chain of events that are composed and used to evaluate that hovering over an
object changes the fill color of an element, clicking on the element pins the
node, dragging and dropping a node to a new position, and double-clicking un-
pins the node. Beneath each action, we show the modifications to the element
attribute that can be used for comparison in a unit test.

##  6 Large Scale D3 Auto-Grading Deployment

###  6.1 Scale and Student Experience

is the result of iterative design and development over two years by the
instructional staff of Georgia Tech’s CSE 6242 Data and Visual
Analytics777https://poloclub.github.io/#cse6242. We presented our initial
ideas for auto-grading a simple “warm-up” D3 exercise as a two-page non-
archival research poster [26]. Following the success of this deployment, we
scaled our auto-graders to cover an entire homework assignment consisting of
four D3 visualizations from different visualization categories. Now, auto-
grades the entire D3 assignment consisting of four visualizations covering a
variety of aspects of data processing, chart types, scale types, and
interaction styles where students complete their work and have it graded
entirely automatically using the Gradescope platform (Fig. 2)[19], without
requiring any manual grading by the instructional staff. Currently, we have
deployed our auto-grader for 4 semesters in Georgia Tech’s CSE 6242: Data and
Visual Analaytics course that has been offered for 10 years and was recently
expanded with an online offering at the Master’s level. To date, more than
4,000 students have used .

Fig. 4: Example D3 Visualizations that students implement our auto-graded
assignments.

###  6.2 Visualization Categories and Interaction

Before the homework assignment is released, the students complete an
introductory auto-graded D3 assignment consisting of a bar plot that
introduces them to the D3 library and gives them practice with auto-graded
assignments. The introductory assignment does not require interaction or
require any data pre-processing. Following this, the students receive a D3
homework assignment consisting of four visualizations, each covering a variety
of aspects of data processing, chart types, scale types, interaction styles.
The following visualization types are used:

  * •

Node-link diagram with “node-pinning” interactivity (Fig. 4.1). Nodes
represent board games, and edges represent similarities between board games.
Dragging a node “pins” (“freezes”) its position so that it will not be
modified by the graph layout algorithm; double-clicking a pinned node unpins
(unfreezes) its position, so it moves freely again.

  * •

Line charts exploring different mark types and axis scales (Fig. 4.2). Lines
and marks represent temporal patterns in the BoardGameGeek data to compare how
the number of ratings grew. Symbols show board game ratings for a specific
point in time.

  * •

Line chart displaying sub-chart when user hovers over mark (Fig. 4.3) Average
board game ratings are displayed using an interactive frequency polygon line
chart. A dynamically generated bar chart appears when the user hovers on a
rating-count datum.

  * •

Choropleth Map (Fig. 4.4) A Choropleth maps is used to examine the popularity
of different board games across the world. Selecting a different game from the
drop-down menu causes the map to be re-colored. A pop-over tooltip menu
displays detailed information when the user hovers over a country.

Our objective is to allow the student practice with building visualizations
that allow the user to explore the data. To meet this goal, the Force-Directed
Graph, Line Chart, and Choropleth visualizations require the implementation of
several user interactions, such as hover, click, drag-and-drop, and filtering
using a drop-down menu.

###  6.3 Visualization Course Assignment Requirements

The D3 homework assignment instructions are issued in a document that
specifies rubrics that describe each visualization and a DOM structure that
specifies the sequence and structure of required elements (Fig. 1.2).

Rubric items specify how the data should be displayed, or describe an
interaction. For example, in one of our assignments where we ask students to
create an interactive line chart (Fig. 4.3), we provide the following rubric
items (paraphrased for brevity):

  * •

“Create a line chart. Summarize the data by displaying the count of board
games by rating for each year.”

  * •

“All axes should be automatically adjusted based on the data. Do not hard-code
any values. Use a linear scale.”

  * •

“Create a horizontal bar chart, so that when hovering over a circle, that bar
chart will be shown below the line chart.”

  * •

“The circle in the line chart should change to a larger size during mouseover
to emphasize that it is the selected point and return to original size on
mouseout.”

The Document Object Model (DOM) structure is a lightweight, minimal
specification that the visualization must adopt so that the auto grader can
locate the gradable elements (Fig. 1.2). The structure is non-invasive, e.g.,
often times only adding an  attribute to an svg element is adequate. This
requirement does not restrict the student design choices or prevent them from
adding additional elements. The auto-grader developers encode the required DOM
element structure in a rubric configuration file written in YAML. e.g., The
required  groupings could be specified as elements, such as g: [‘‘lines’’,
‘‘circles’’, ‘‘legend’’], signifying that the visualization requires a minimum
of 3 group elements with the listed  values. When the auto-grader runs on the
submission, the rubric configuration is referenced and we provide preliminary
information to the student within Gradescope describing whether or not the
required elements have been found in addition to the layout information
(discussed in Sec. 5.3.2). These advisory tests serve to assist the student in
detecting critical implementation errors that would prevent the auto-grader
from executing correctly and help the student align the structure of their
submission. After verifying the structure and required elements, the remaining
tests verify the rubric requirements and awards points for each test case that
is passed. We discuss the impact of this strategy in the next section.

##  7 Impact, Lessons Learned, and Limitations

###  7.1 Student Impact

####  7.1.1 Receiving Instant Feedback to Improve Their Learning

As a result of using Gradescope for submissions, students have a greatly
simplified and transparent workflow as they complete work on their assignment.
Students are able to see their scores immediately instead of waiting for the
grading session to end. This helped curtail a long-standing frustration that
students often had when waiting for their scores or believing that they would
have a higher score. Both Sherman et al.[42] and Gramoli et al.[20] also noted
that students leverage instant feedback to improve their score on auto-graded
programming assignments.

One example of improved learning is evidenced by the quantity of student
questions on Ed Discussion[7], the course’s discussion forum. We compared the
number of questions between the Fall 2020, the last semester before was
deployed and the most recent semester of Spring 2023 for the online section of
the course. Our experience in teaching this class over the years show that
students are more likely to post assignment questions when they need
clarification or assistance with an implementation while assignments that are
considered less difficult consistently have lower question counts. After
releasing for the assignment described in (Sec. 6.2), we observed that the
number of questions decreased from 1,965 posts to 1,356 posts (-31.0%) for a
nearly equivalent enrollment size: 920 in Fall 2020 and 926 in Spring 2023
(online sections), leading us to conclude that there is some reduction in
confusion and improved learning experience.

  * •

Node Link Diagram with “node-pinning interactivity” (Fig. 4.1), we observed a
decrease from 360 posts to 260 posts (-27.8%)

  * •

Line charts exploring different mark types and axis scales (Fig. 4.2), we
observed a decrease from 539 posts to 438 posts (-18.7%)

  * •

Line chart displaying sub-chart when hovering over mark (Fig. 4.3), we
observed a decrease from 699 to 439 posts (-37.2%)

  * •

Choropleth map with tool-tip and filtering (Fig. 4.4), we observed a decrease
from 367 to 219 posts (-40.3%)

The feedback also helps improve the quality of the finished visualization by
encouraging students to design their visualizations by using D3 principles and
functions, instead of hard-coding values. For example, as we have a test case
that checks for the appropriate use of scale, for students who use for loops
to create individual SVG elements (e.g., marks on a line chart) instead of
using D3 selections and data join, they receive immediate feedback that calls
attention to the need for using a scale.

####  7.1.2 Facilitating Higher Quality Student Interaction

We also see evidence of improved learning through a re-distribution in types
of student questions on Ed Discussion. Specifically, by comparing the content
of Ed Discussion posts across semesters, we found that the auto-grader had
greatly reduced the number of repeated “routine” question posts related to
grading (“would I lose points for ___?”), acceptable code functions (“can I
use ___?”), and visualization styling. preempted these types of questions
through instant, informative feedback, allowing students to accomplish a
significant amount of self-learning as they navigated these issues. We
observed students completing more error discovery on their own and then
helping others, allowing students to get answers at scale [28]. (“I
experienced the above error… I did not set the value attribute of the option
element (wrongly set a different attribute instead for the game name).
Rectifying this fixed the issue for me.”). We are excited by having increased
student-instructor interaction on more qualitative topics about gaining
knowledge and experience with visualization design and implementation, and
less on logistical issues that could distract students.

####  7.1.3 Reduced Configuration Errors

Our approach has dramatically reduced configuration errors that students may
experience, such as incorrectly referenced libraries or data files; before
using auto-grader, such errors would prevent the visualization from being
rendered or graded, and graders would need to manually resolved them. The
auto-grader re-creates the student’s development environment and eliminates
potential system configuration mismatch between student and instructor
machines. As a result, ’s unified auto-grader environment eliminated the
occurrences of re-grade requests for system configuration issues.

####  7.1.4 Virtual Elimination of Re-Grade Requests

Historically, we employed a re-grading process where students could appeal
their grade if an error had been made. Large number of TA hours required to
address this effort often resulted in multiple communications and some
students submitted critiques that the process was frustrating due to small
differences between the development environment and the TAs grading
environment. After implementing and deploying the auto-grader for more than
1,100 student in Fall 2021, the re-grade requests amount dropped 98%, from
more than 500 in the semester before to less than 10. Among these 10 re-grade
requests, the most common error was that the student forgot to activate their
highest scoring submission in Gradescope.

###  7.2 Instructor Impact

####  7.2.1 Reduced TA Grading Hours

The auto-grader deployment resulted in a reduction of 400 TA hours (a
conservative estimate) spent on grading effort every semester. Before using ,
a grader would typically spend 5 minutes to grade one submission. For a class
size of 1,100, this requires approximately 100 hours, or 5 part-time TAs per
visualization. Scaling to four D3 visualizations in one assignment required
400 hours, or 20 part-time TAs who focus only on grading. This effort does not
account for any hours spent actually interfacing with students by answering
questions, conducting office hours, preparing future assignments, or reviewing
re-grade requests.

####  7.2.2 Virtual Elimination of Re-grade Work

The reduction in re-grade requests (Sec. 7.1.4) also resulted in a drastic
reduction in the required TA hours needed to re-grade these assignments. also
eliminated an entire class of re-grade requests caused by grading errors that
arise from manual grading workflows, i.e.,  we no longer require manual
tabulation of scores or have to reconcile student and instructor development
environment discrepancies.

####  7.2.3 Increased Time for Qualitative Feedback

In response to the reduction in required TA grading hours, we re-distributed
TA effort to supporting the students questions during the assignment window
through Office Hours and increased interaction on EdDiscussion. As discussed
in the (Sec 7.1.2), TAs were able to provide higher quality instruction and
focus on more qualitative questions rather than repetitive questions on
machine configuration, etc. In addition, the instructional staff was able to
spend more time collaborating and improving the auto-grader from semester to
semester.

###  7.3 Lessons Learned

####  7.3.1 Balancing Focus Between structure and Design Choices

When we first started experimenting with auto-grading visualizations, we
required that the visualization follow a rigid DOM structure, allowing only
small deviations, which unintentionally caused students to focus on getting
the structure “right” rather than experimenting with different designs. We
quickly recognized that we could simplify the required structure (e.g., fewer
elements in the DOM, and not requiring strict element ordering and nesting)
without affecting the quality of the visualization. In hindsight, we realized
that while the DOM structure of a visualization is naturally produced during
the implementation (e.g., it is natural to append  elements within a  grouping
element), it might not be natural for the students to consider it upfront when
they begin their design process. As we further refined our approach, we
learned that we need to guide students toward a design structure that can be
easily implemented and can provide sufficient structural features amenable to
grading at a large scale.

####  7.3.2  Helping Students Learn Better Coding Practices

During periodic manual code reviews of student submissions, we learned that
the most frequently missed test cases were due to students using a wide
variety of methods to implement the specification of chart dimensions and
margins. D3 axes and scales depend upon this lay out, e.g., the x-axis size in
pixels depends upon the chart width minus the left and right margins. We
observed that when a student “hard-codes” the maximum width of the axis
without referring to the chart dimensions they might make a small mistake
e.g., even a few pixels can cause the plotted data point to have an incorrect
horizontal positioning in the chart.

To address this, we suggested that students use the “Margin Convention” chart
construction technique as a consistent way to layout a visualization. To help
students use this technique, we designed additional advisory (no-penalty) test
cases that present the student with a preliminary brief report of how the
auto-grader detected their chart dimensions and margins. The insight we share
is that using has elevated our teaching of D3 beyond just helping students
just get the “right” answer but to also teach consistent coding conventions
and train students to use a best practice. Using these techniques helps us
address the frequent question: “What is the best implementation of this
assignment?” We find that teaching students to code using a best practice
results in an improved implementation without necessarily showing them the
exact code they should have written.

####  7.3.3  Designing Informative Test Cases

We continuously monitor the discussion forums and office-hour conversations to
obtain information about the students’ experience. We learned that the limited
feedback that only returns a generic index error, runtime error, or only
displays limited information, e.g., “var a and b are not equal” are not
helpful in a learning environment and caused frustration among students. In
response, we began designing test cases that provide multi-level feedback in
an effort to help the student resolve complex programming issues. Now, our
unit testing design provides increased information about the rubric item being
evaluated. For example, a test now produces:

  1. 1.

Logging of helpful intermediate information during the test, alerting the
student to any assumptions made by the auto-grader for the element being
evaluated, e.g., “Found a <g> element with id x-axis”. This provides
information that helps the students verify what the auto-grader has detected.

  2. 2.

A display of actual versus expected results when the test case fails and
common mistakes that help them troubleshoot. E.g., “The x-axis was found in
your visualization but the tick marks are not spaced at the 10-year interval.
Found ticks [1980, 1985, …], but expected [1980, 1990, …]. See
https://d3js.org/d3-time#interval_every”.

###  7.4 Limitations

We discuss limitations of to inform our plans for improvement and future work.

####  7.4.1 Focus on Test Case and Score

The primary feedback within auto-grading is centered around the results of the
suite of test cases used for the visualization. While we endeavor to provide
adequate coverage and useful feedback, we acknowledge that there could also
exist tendencies for the students to only work to get the maximum score and
move on without further exploring learning in the design space. Therefore,
learning correlates with the quality and coverage of the test cases used. We
strive to design test cases that provide learning opportunities that
facilitate formative improvements and provide feedback that helps students
under why such improvements are beneficial (such as those discussed next in
Sec. 7.4.2).

####  7.4.2 Grading Design of a Visualization

In our course, we emphasize best design practices (e.g., color choices, chart
layout, axis limits) but currently have limited test cases on color choices.
If a student chose red and green colors without considering red-green color
blindness, they would not currently receive feedback guiding them toward a
more appropriate palette. This poses a question in how to best teach students
in the auto-grading environment — by providing advisory guidance or
associating such a design choice with a point value? We are planning an
improvement that will capture additional considerations for color-blind safe
palettes and proper contrast [16].

####  7.4.3 Allowing Open-Ended Design

Our auto-graded D3 assignments are specified at a level that describes the
type, appearance, and behavior of the visualization. However, we currently do
not support grading open-ended implementations where the choice of
visualization type or interactions is left to each student’s decision. For
example, one student may choose to visualize temporal data using a bar chart
while another chooses to make a line chart. We recognize that this limitation
could constrain students in exploring more approaches and that leads us to
consider how extending could permit this assignment type in the future.

##  8 Discussion and Future Work

In this section, we share our observations on future work for extending and
its capabilities.

###  8.1 Generalized Visualization Auto-Grading

Because D3 is a base technology and originally contributed as a “visualization
kernel”[12] it has been used as a foundation for many other visualization
toolkits/libraries: Vega, Vega-Lite, Observable Plot. Since all of these
libraries can produce SVG elements, their output can be easily accessed with
and analyzed by reading the underlying DOM structure. This poses a broader
question on how can be generalized to grade visualizations made with tools
other than D3. While has not been used for grading other libraries, the method
could easily be adapted to grade other visualizations that use HTML, CSS, and
SVG. Adaptations of could make it possible for instructors to teach different
visualization technologies at a large-scale and auto-grade them using our
method

###  8.2 Incorporating Design Suggestions

In the future, we want to increase focus on assisting students in design
choices by helping students design charts that are accessible, e.g.,
colorblind-safe schemes, proper color contrast, and font-sizes. The
Chartability[16] project provides guidance on how to implement a set of
auditing principles to promote visualization design that captures these
ideals. We share the view of Shin et al.[43] that the Chartability principles
could be incorporated into an automated tool. could be extended to adopt a
Chartability audit by adding test cases. We could extract the colors used for
visual encodings, measure font size, or determine the color contrast by
querying CSS property attributes and then display suggestions to the student
about how they could improve their design, similar to the accessibility
“hints” offered by WebHint [37]. We recommend that additional “design” unit
tests should not be used to penalize the student but to teach them better
design principles. In scenarios outside of teaching, could be used to analyze
design choices between different implementations of the same visualization.

###  8.3 ML Methods for Visualization Interpretation and Design

Auto-grading visualizations in general could generally benefit from machine
learning methods that could be employed to extract and interpret content and
assist in design [47] and even enable creation of more open-ended
visualization assignments that give students more design autonomy and rely
less upon prescriptive rubrics. Chen et al. use a multi-task deep neural
network to extract visualization components from bitmap images to generate
extensible templates [14]. Their work could be adapted extract information
from visualizations that are not composed of web standards HTML, CSS, and SVG.
Hu et al. contributed VizML[25], an visualization recommendation system that
uses ML to identify the top 5 design choices for a visualization based upon a
specific dataset. DeepEye [30] uses supervised learning to recognize a “good”
or “bad” visualizations based on expert rules and can also rank visualizations
to determine which one is better. PlotThread [46] uses reinforcement learning
to optimize the story line of a visualization and could also be use to improve
or suggest changes to a student’s work.

##  9 Conclusion

In this work, we present , an auto-grading method that enables scalable
grading for the static and interactive components of.a D3 visualization. We
discussed the key-features of our method and how it can be flexibly adapted to
other visualization assignments. In our discussion, we highlight how can be
extended to support other visualization libraries or adapted to support
incorporation of design suggestions and recommendations that will help
students develop better visualizations. We hope that our work helps students
overcome the learning curve associated with learning a new visualization
platform and that visualization courses that teach D3 can use our method or
adapt it for other visualization platforms.

## References

  * [1] CS444 - Data Visualization. University of Arizona.  https://cscheid.net/courses/fall-2019/csc444/, 2019.  Accessed on: Mar 02, 2023.
  * [2] CS171 - Visualization. Harvard University.  https://www.cs171.org/2022/, 2022.  Accessed on: March 2, 2023.
  * [3] CS5630/CS6630 - Visualization for Data Science. The University of Utah.  https://www.dataviscourse.net/2022/syllabus/, 2022.  Accessed on: Mar 02, 2023.
  * [4] CSE512 - Data Visualization. University of Washington.  https://courses.cs.washington.edu/courses/cse512/22sp/, 2022.  Accessed on : Mar 02, 2023.
  * [5] CS448B - Data Visualization. Stanford University.  https://online.stanford.edu/courses/cs448b-data-visualization, 2023\.  Accessed on: Mar 02, 2023.
  * [6] CS6242 Data and Visual Analytics. Georgia Institute of Technology.  https://poloclub.github.io/cse6242-2023spring-online/, 2023.  Accessed on: Jan 08, 2023.
  * [7] EdDiscussion.  https://edstem.org, 2023.  Accessed on: Aug, 08, 2022.
  * [8] Enrollment history of CS6242 Data and Visual Analytics. Georgia Institute of Technology.  https://poloclub.github.io/#cse6242, 2023.  Accessed on: Jan 08, 2023.
  * [9] U. Z. Ahmed, N. Srivastava, R. Sindhgatta, and A. Karkare.  Characterizing the pedagogical benefits of adaptive feedback for compilation errors by novice programmers.  In Proc. ACM/IEEE 42nd International Conference on Software Engineering: Software Engineering Education and Training, ICSE-SEET ’20, p. 139–150. ACM, New York, 2020. doi: 10 . 1145/3377814 . 3381703
  * [10] L. Battle, D. Feng, and K. Webber.  Exploring d3 implementation challenges on stack overflow.  In 2022 IEEE Visualization and Visual Analytics (VIS), pp. 1–5, 2022. doi: 10 . 1109/VIS54862 . 2022 . 00009
  * [11] Blackboard Inc.  Blackboard LMS.  https://www.blackboard.com/en-mea/teaching-learning/learning-management, 2023\.  Accessed on: Mar 01, 2023.
  * [12] M. Bostock, V. Ogievetsky, and J. Heer.  D³ data-driven documents.  IEEE Trans. Vis. Comput. Graph., 17(12):2301–2309, 2011. doi: 10 . 1109/TVCG . 2011 . 185
  * [13] Q. Chen, F. Sun, X. Xu, Z. Chen, J. Wang, and N. Cao.  Vizlinter: A linter and fixer framework for data visualization.  IEEE Trans. Vis. Comput. Graph., 28(1):206–216, 2022. doi: 10 . 1109/TVCG . 2021 . 3114804
  * [14] Z. Chen, Y. Wang, Q. Wang, Y. Wang, and H. Qu.  Towards automated infographic design: Deep learning-based auto-extraction of extensible timeline.  IEEE Trans. Vis. Comput. Graph., 26(1):917–926, 2020. doi: 10 . 1109/TVCG . 2019 . 2934810
  * [15] D2L Corporation.  Brightspace LMS.  https://www.d2l.com/brightspace/, 2023.  Accessed on: Mar 01, 2023.
  * [16] F. Elavsky.  Chartability.  https://chartability.github.io/POUR-CAF/, 2021.  Accessed on: Jul 1, 2021.
  * [17] J. Gao, B. Pang, and S. S. Lumetta.  Automated feedback framework for introductory programming courses.  In Proc. ACM Conference on Innovation and Technology in Computer Science Education, ITiCSE ’16, p. 53–58. ACM, New York, 2016. doi: 10 . 1145/2899415 . 2899440
  * [18] P. Godefroid, N. Klarlund, and K. Sen.  Dart: Directed automated random testing.  SIGPLAN Not., 40(6):213–223, 2005. doi: 10 . 1145/1064978 . 1065036
  * [19] Gradescope Inc.  Gradescope.  https://www.gradescope.com, 2020.  Accessed on: May 01, 2020.
  * [20] V. Gramoli, M. Charleston, B. Jeffries, I. Koprinska, M. McGrane, A. Radu, A. Viglas, and K. Yacef.  Mining autograding data in computer science education.  In Proc. Australasian Computer Science Week Multiconference, number 1 in ACSW ’16, pp. 1–10. ACM, New York, 2016. doi: 10 . 1145/2843043 . 2843070
  * [21] S. Gulwani, I. Radiček, and F. Zuleger.  Feedback generation for performance problems in introductory programming assignments.  In Proc. ACM SIGSOFT International Symposium on Foundations of Software Engineering, FSE 2014, p. 41–51. ACM, New York, 2014. doi: 10 . 1145/2635868 . 2635912
  * [22] J. Harper and M. Agrawala.  Deconstructing and restyling d3 visualizations.  UIST ’14, p. 253–262. ACM, New York, 2014. doi: 10 . 1145/2642918 . 2647411
  * [23] A. K. Hopkins, M. Correll, and A. Satyanarayan.  Visualint: Sketchy in situ annotations of chart construction errors.  In Computer Graphics Forum, vol. 39, pp. 219–228. Wiley Online Library, 2020. doi: 10 . 1111/cgf . 13975
  * [24] E. Hoque and M. Agrawala.  Searching the visual style and structure of d3 visualizations.  IEEE Trans. Vis. Comput. Graph., 26(1):1236–1245, 2020. doi: 10 . 1109/TVCG . 2019 . 2934431
  * [25] K. Hu, M. A. Bakker, S. Li, T. Kraska, and C. Hidalgo.  Vizml: A machine learning approach to visualization recommendation.  In Proc. CHI Conference on Human Factors in Computing Systems, CHI ’19, p. 1–12. ACM, New York, 2019. doi: 10 . 1145/3290605 . 3300358
  * [26] M. Hull, C. Guerin, J. Chen, S. Routray, and D. H. Chau.  Towards automatic grading of d3.js visualizations.  arXiv preprint arXiv:2110.11227, 2021. doi: 10 . 48550/arXiv . 2110 . 11227
  * [27] Instructure Inc.  Canvas LMS.  https://www.instructure.com/canvas, 2023.  Accessed on: Mar 01, 2023.
  * [28] D. Joyner.  Teaching at Scale: Improving Access, Outcomes, and Impact Through Digital Instruction.  Taylor & Francis, 2022. doi: 10 . 4324/9781003274834
  * [29] L. Y.-H. Lo, Y. Ming, and H. Qu.  Learning vis tools: Teaching data visualization tutorials.  In 2019 IEEE Visualization Conference (VIS), pp. 11–15, 2019. doi: 10 . 1109/VISUAL . 2019 . 8933751
  * [30] Y. Luo, X. Qin, N. Tang, and G. Li.  Deepeye: Towards automatic data visualization.  In 2018 IEEE 34th International Conference on Data Engineering (ICDE), pp. 101–112, 2018. doi: 10 . 1109/ICDE . 2018 . 00019
  * [31] E. Maicus, M. Peveler, A. Aikens, and B. Cutler.  Autograding interactive computer graphics applications.  SIGCSE ’20, p. 1145–1151. ACM, New York, 2020. doi: 10 . 1145/3328778 . 3366954
  * [32] A. McNutt, G. Kindlmann, and M. Correll.  Surfacing visualization mirages.  CHI ’20. ACM, New York, 2020. doi: 10 . 1145/3313831 . 3376420
  * [33] H. Mei, Y. Ma, Y. Wei, and W. Chen.  The design space of construction tools for information visualization: A survey.  J. Vis. Lang. Comput., 44:120–132, 2018. doi: 10 . 1016/j . jvlc . 2017 . 10 . 001
  * [34] Moodle PTY Ltd.  Moodle LMS.  https://moodle.com/solutions/lms/, 2023.  Accessed on: Mar 01, 2023.
  * [35] D. Moritz.  Draco: Formalizing Visualization Design Knowledge as Constraints.  https://uwdata.github.io/draco/, 2018.  Accessed on: Mar 09, 2023.
  * [36] D. Moritz, C. Wang, G. L. Nelson, H. Lin, A. M. Smith, B. Howe, and J. Heer.  Formalizing visualization design knowledge as constraints: Actionable and extensible models in draco.  IEEE Trans. Vis. Comput. Graph., 25(1):438–448, 2019. doi: 10 . 1109/TVCG . 2018 . 2865240
  * [37] Open JS Foundation.  WebHint.  https://https://webhint.io, 2023.  Accessed on: Jun 29, 2023.
  * [38] S. Parihar, Z. Dadachanji, P. K. Singh, R. Das, A. Karkare, and A. Bhattacharya.  Automatic grading and feedback using program repair for introductory programming courses.  In Proc. ACM Conference on Innovation and Technology in Computer Science Education, ITiCSE ’17, p. 92–97. ACM, New York, 2017. doi: 10 . 1145/3059009 . 3059026
  * [39] A. Satyanarayan, D. Moritz, K. Wongsuphasawat, and J. Heer.  Vega-lite: A grammar of interactive graphics.  IEEE Trans. Vis. Comput. Graph., 23(1):341–350, 2017. doi: 10 . 1109/TVCG . 2016 . 2599030
  * [40] S. Segura, G. Fraser, A. B. Sanchez, and A. Ruiz-Cortés.  A survey on metamorphic testing.  IEEE Trans. Softw. Eng., 42(9):805–824, 2016. doi: 10 . 1109/TSE . 2016 . 2532875
  * [41] SGW Communications.  Sakai LMS.  https://www.sakailms.org, 2023.  Accessed on: Mar 01, 2023.
  * [42] M. Sherman, S. Bassil, D. Lipman, N. Tuck, and F. Martin.  Impact of auto-grading on an introductory computing course.  J. Comput. Sci. Coll., 28(6):69–75, 2013. doi: doi/10 . 5555/2460156 . 2460171
  * [43] S. Shin, S. Hong, and N. Elmqvist.  Perceptual pat: A virtual human system for iterative visualization design.  arXiv preprint arXiv:2303.06537, 2023. doi: 10 . 48550/arXiv . 2303 . 06537
  * [44] Software Freedom Conservancy.  Selenium.  https://www.selenium.dev, 2021.  Accessed on: February 01, 2021.
  * [45] Software Freedom Conservancy.  Selenium Action Chain.  https://www.selenium.dev/selenium/docs/api/py/webdriver/selenium.webdriver.common.action_chains.html, 2021\.  Accessed on: March 14, 2021.
  * [46] T. Tang, R. Li, X. Wu, S. Liu, J. Knittel, S. Koch, T. Ertl, L. Yu, P. Ren, and Y. Wu.  Plotthread: Creating expressive storyline visualizations using reinforcement learning.  IEEE Trans. Vis. Comput. Graph., 27(2):294–303, 2021. doi: 10 . 1109/TVCG . 2020 . 3030467
  * [47] Q. Wang, Z. Chen, Y. Wang, and H. Qu.  A survey on ml4vis: Applying machine learning advances to data visualization.  IEEE Trans. Vis. Comput. Graph., 28(12):5134–5153, 2022. doi: 10 . 1109/TVCG . 2021 . 3106142
  * [48] C. Wilcox.  The role of automation in undergraduate computer science education.  SIGCSE ’15, p. 90–95. ACM, New York, 2015. doi: 10 . 1145/2676723 . 2677226
  * [49] J. Wood, A. Kachkaev, and J. Dykes.  Design exposition with literate visualization.  IEEE Trans. Vis. Comput. Graph., 25(1):759–768, 2019. doi: 10 . 1109/TVCG . 2018 . 2864836


# Numerical Approximation of Probability Mass Functions Via the Inverse
Discrete Fourier Transform

Richard L. Warr111Department of Mathematics and Statistics, Air Force
Institute of Technology, Wright-Patterson Air Force Base, Ohio, USA. The views
expressed in this article are those of the authors and do not reflect the
official policy or position of the United States Air Force, Department of
Defense, or the U.S. Government.

###### Abstract

First passage distributions of semi-Markov processes are of interest in fields
such as reliability, survival analysis, and many others. The problem of
finding or computing first passage distributions is, in general, quite
challenging. We take the approach of using characteristic functions (or
Fourier transforms) and inverting them, to numerically calculate the first
passage distribution. Numerical inversion of characteristic functions can be
numerically unstable for a general probability measure, however, we show for
lattice distributions they can be quickly calculated using the inverse
discrete Fourier transform. Using the fast Fourier transform algorithm these
computations can be extremely fast. In addition to the speed of this approach,
we are able to prove a few useful bounds for the numerical inversion error of
the characteristic functions. These error bounds rely on the existence of a
first or second moment of the distribution, or on an eventual monotonicity
condition. We demonstrate these techniques in an example and include R-code.

KEY WORDS: characteristic function, discrete Weibull, first passage
distribution, fast Fourier transform, semi-Markov process, statistical
flowgraph

##  1 Introduction

Statistical literature abounds with proofs using characteristic functions
(CFs). Asymptotic results such as the central limit theorem rely heavily on
the properties of CFs. However, when it comes to applied statistics the
reverse is true. In general statisticians seem very uncomfortable using the CF
or numeric approximations of it, even though they routinely use numerical
approximations and calculations for various other procedures. This could be
partly due to the fact that CFs are complex functions, but this is a deterrent
based on fear of the unknown, not difficulty.

This is not the case in many applied sciences. Engineers make heavy use of the
Fourier transform and are quite comfortable using it in practice. The Fourier
transform and the characteristic function are the same function with a change
of variables. To use one over the other is a matter of preference, the curves,
as drawn, are identical. There are some areas in applied statistics where use
of CFs are helpful. One such area is semi-Markov processes (SMPs),
specifically finding first passage distributions from one state to another, as
in statistical flowgraph models Huzurbazar (2005). Using characteristic
functions is a natural way to find first passage distributions in SMPs.

For example consider the graphical representation of a SMP in Figure 1, where
the nodes on the graph represent a state, and the branches represent waiting
time distributions before transition to the next state. Each branch is labeled
with a characteristic function $\varphi_{{}_{ij}}(s)$ and a probability of
taking that branch. The characteristic function of the first passage
distribution is:

$\varphi_{{}_{13*}}(s)=\frac{(1-p)\varphi_{{}_{12}}(s)\varphi_{{}_{23}}(s)}{1-p\varphi_{{}_{12}}(s)\varphi_{{}_{21}}(s)},$
(1)

the “*” denotes a first passage. For details on finding the first passage CF
see Huzurbazar (2005) or for a more theoretical development refer to Pyke
(1961). Once the CFs for the branches are known, it is trivial to calculate
the CF of the first passage from state $1$ to $3$. The challenge is to convert
the CF to a distribution. In most cases this must be done numerically.

Figure 1: An example semi-Markov process.

Work has been done to show that the discrete Fourier transform (DFT) can
accurately invert characteristic functions given sufficiently fast decay of
both the density and the characteristic function (see Hughett (1998)). One
class of distributions that has not been well studied for inversion using the
DFT is discrete distributions. Specifically we focus on distributions with
support $n\Delta t$ for $n=0,\pm 1,\pm 2,\ldots$ and $\Delta
t\in\mathbb{R}^{+}$. This type of distribution has been termed a lattice or an
arithmetic distribution, these include most of the well studied discrete
distributions such as the binomial, Poisson, negative binomial and many
others.

The primary goal of this paper is to promote the use of the inverse discrete
Fourier transform (iDFT) for the inversion of CFs to probability mass
functions (PMFs). A secondary benefit of using the DFT is easy calculation of
CFs when they do not have a closed form.

This paper is outlined as follows. The next section details some properties of
the DFT, in particular how the DFT is applied when dealing with lattice
distributions. Next, the DFT is shown in action, in an application. We include
code using the R software package (see R Development Core Team (2009)).
Finally, we conclude with a few comments.

##  2 The discrete Fourier transform

For a random variable $T$, with distribution $F$, its characteristic function
is

$\varphi_{{}_{T}}(s)\equiv\int_{-\infty}^{\infty}e^{ist}\,dF.$ (2)

Let $\hat{f}(\omega)$ be the Fourier transform of $T$, then the relationship
between the characteristic function and the Fourier transform is

$\varphi_{{}_{T}}(-2\pi\omega)=\hat{f}(\omega).$ (3)

In the reminder of the paper we use Fourier transforms, with the understanding
that the CF is easily obtained from the FT. We do this primarily for ease in
applying DFT methods, specifically using the fast Fourier transform (FFT)
algorithm.

The DFT can be used to approximate the Fourier transform and its inverse.
Under certain conditions, the error of this approximation can be controlled.
An excellent reference on the DFT is Briggs and Henson (1995). To use the DFT,
the support of the RV must be discretized at evenly spaced points, where
$\Delta t$ is the space between adjacent points. We term these points the
support of the DFT samples. Similarly the support of the iDFT samples the FT
at evenly spaced intervals of width $\Delta\omega$ in the transform domain.
These sampling widths are related by the reciprocity relation

$\Delta t\Delta\omega=\frac{1}{N}.$ (4)

With this information we apply the DFT and iDFT to lattice distributions.

###  2.1 DFT of lattice distributions

In this section error bounds for lattice distributions with nonnegative
support are derived. If $f(t_{n})$ is the PMF of a lattice distribution, then
the DFT of that distribution is:

$F_{k}\equiv\sum_{n=0}^{N-1}f(t_{n})e^{-2\pi i\frac{nk}{N}},\text{ for
}k=0,1,\ldots,N-1.$ (5)

Clearly the utility of the DFT as an approximation of the FT is dependent on
the size of $N$. The major benefit of using the DFT with discrete random
variables is that unlike RVs with PDFs, when sampling from lattice
distributions we are able to capture essentially all the information about the
random variable. In this paper we use the word “sampling” loosely to mean the
PMF values of the support that are included in the DFT. When sampling a RV
with a PDF the measure of our finite number of samples is zero, whereas when
sampling from a certain class of lattice distributions our “sample” has
measure that can approach one. In essence, we are losing little or no
information when sampling from a DRV, or in other words, with a finite number
of points we obtain more of a “census” than a “sample” of where the
probability is located in a distribution. This allows the DFT to accurately
approximate the FT at specified points given $N$ sufficiently large.

We confine our focus to nonnegative lattice RVs $T$ where, given any
$\varepsilon>0$, there exists an $N$ such that
$\sum_{i=0}^{N-1}P(T=t_{i})>1-\varepsilon$. Nearly all properly defined
nonnegative lattice RVs fall into this class. There may be a few pathological
cases which do not, such as the counting measure on all the integers, however,
in many cases one would argue that these are not properly defined
distributions. The assumption that $T$ is nonnegative is only slightly less
general than the unrestricted case, and derivations for lattice RVs with
unbounded support would be very similar.

To find the error bound for the DFT on lattice distributions one only needs to
look at the definition of the Fourier transform. Let $f(t_{n})\equiv
P(T=n\,\Delta t)$, then the definition of the Fourier transform is:

$\hat{f}(\omega)\equiv\sum_{n=0}^{\infty}f(t_{n})e^{-2\pi i\omega n\Delta
t}=\sum_{n=0}^{\infty}P(T=n\Delta t)e^{-2\pi i\omega n\Delta t}$ (6)

Now our goal is to bound the error $|\hat{f}(\omega_{k})-F_{k}|$ for all index
$k=0,1,\ldots,N-1$. Therefore we must find an optimal $\omega_{k}$ that
matches well with the DFT’s $F_{k}$. To do this we simply set the exponents of
Equations 5 and 6 equal to each other and solve for $\omega_{k}$. Therefore

$-2\pi i\omega_{k}n\Delta t=-2\pi i\frac{nk}{N},$ (7)

implies that

$\omega_{k}=\frac{k}{\Delta tN}.$ (8)

Now using the constraint that

$\sum_{n=0}^{N-1}P(T=n\,\Delta t)=\sum_{n=0}^{N-1}f(t_{n})\geq 1-\varepsilon,$

we show that the error can be controlled.

###### Lemma 2.1

For a nonnegative lattice random variable, defined on the support $n\,\Delta
t$ for $n=0,1,\ldots,\infty$, the pointwise error of the forward DFT is less
than or equal to $P(T\geq N\,\Delta t)$.

  * Proof

$\displaystyle\left|\hat{f}(\omega_{k})-F_{k}\right|$ $\displaystyle=$
$\displaystyle\left|\sum_{n=0}^{\infty}P(T=n\Delta t)e^{-2\pi
i\omega_{k}n\Delta t}-\sum_{n=0}^{N-1}P(T=n\Delta t)e^{-2\pi
i\frac{nk}{N}}\right|$ $\displaystyle=$
$\displaystyle\left|\sum_{n=0}^{\infty}P(T=n\Delta t)e^{-2\pi
i\frac{nk}{N}}-\sum_{n=0}^{N-1}P(T=n\Delta t)e^{-2\pi i\frac{nk}{N}}\right|$
$\displaystyle=$ $\displaystyle\left|\sum_{n=N}^{\infty}P(T=n\Delta t)e^{-2\pi
i\frac{nk}{N}}\right|$ $\displaystyle\leq$
$\displaystyle\sum_{n=N}^{\infty}P(T=n\Delta t)\left|e^{-2\pi
i\frac{nk}{N}}\right|\ =\ \sum_{n=N}^{\infty}P(T=n\,\Delta t)$
$\displaystyle=$ $\displaystyle\sum_{n=N}^{\infty}f(t_{n})\ =P(T\geq N\Delta
t).\nobreak\hskip 0.0pt\hskip 15.00002pt minus 5.0pt\nobreak\vrule
height=7.5pt,width=5.0pt,depth=2.5pt$

To give an example, consider a Poisson random variable $U$, with rate
parameter $\lambda=5$. The FT of $U$ is $\hat{f}(\omega)=\exp\\{5e^{-2\pi
i\omega}-5\\}$. If we choose $N=16$, where $\Delta t=1$, then
$\omega_{k}=k/16$ for $k=0,1,\ldots,15$. We set the error
$\varepsilon=P(U>15)\approx 0.000069$. The greatest error occurs when
computing $|\hat{f}(0/16)-F_{0}|\approx|1-0.999931|=0.000069$. Therefore we
can see in this example that
$\left|\hat{f}(\omega_{k})-F_{k}\right|\leq\varepsilon$.

Now that we have shown that the DFT can accurately approximate the Fourier
transform of a DRV, at specified points, we focus on the inverse DFT. This is
the more difficult of the two problems, but is in general more useful. Given
the Fourier transform of a DRV we now demonstrate how to accurately calculate
the PMF.

Given that $\hat{f}(\omega)$ is a known function, we show that the inverse DFT
has the same error bound as the forward DFT. The inverse DFT is defined as:

$f_{k}\equiv\frac{1}{N}\sum_{n=0}^{N-1}\hat{f}(\omega_{n})e^{2\pi
i\omega_{n}k\Delta t}.$ (9)

###### Lemma 2.2

Given the Fourier transform of a nonnegative lattice RV, $T$, evaluated at
points $k/(N\,\Delta t$), for $k=0,1,\ldots N-1$, the pointwise error of the
inverse DFT is less than or equal to $P(T\geq N\,\Delta t)$.

We introduce a couple of notational items to help with the following proof.
Let “mod” be the modulo operator, so for the positive integer $b$, and non-
negative integers $a$, $n$ and $r$; then $r=a\text{ mod }b$, where $n$ is the
largest non-negative integer that satisfies the equation $a=r+nb$. This
implies that $r<b$. Also, let

$I_{(\text{condition})}=\left\\{\begin{array}[]{ll}1&\mbox{if ``condition" is
true}\\\ 0&\mbox{otherwise}\end{array}\right.$ (10)

We’ll call $I_{(\text{condition})}$ the indicator function.

  * Proof

Using Equations 6 and 9 we can write the iDFT as:

$\displaystyle f_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\sum_{j=0}^{\infty}P(T=j\Delta
t)e^{-2\pi i\omega_{n}j\Delta t}e^{2\pi i\omega_{n}k\Delta t}$
$\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\sum_{j=0}^{\infty}P(T=j\Delta
t)e^{-2\pi i\frac{nj}{N}}e^{2\pi i\frac{nk}{N}}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{j=0}^{\infty}P(T=j\Delta
t)\sum_{n=0}^{N-1}e^{-2\pi i\frac{nj}{N}}e^{2\pi i\frac{nk}{N}}$
$\displaystyle=$ $\displaystyle\frac{1}{N}\sum_{j=0}^{\infty}P(T=j\Delta
t)\,N\,\text{I}_{(k=j\text{ mod }N)}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{N-1}P(T=j\Delta t)\,\text{I}_{(k=j\text{ mod
}N)}+\sum_{j=N}^{\infty}P(T=j\Delta t)\,\text{I}_{(k=j\text{ mod }N)}$
$\displaystyle=$ $\displaystyle P(T=k\Delta t)+\sum_{j=N}^{\infty}P(T=j\Delta
t)\,\text{I}_{(k=j\text{ mod }N)}.$

Therefore we can now express the error as:

$\displaystyle\left|f_{k}-P(T=k\Delta t)\right|$ $\displaystyle=$
$\displaystyle\left|P(T=k\Delta t)+\sum_{j=N}^{\infty}P(T=j\Delta
t)\,\text{I}_{(k=j\text{ mod }N)}-P(T=k\Delta t)\right|$ $\displaystyle\leq$
$\displaystyle P(T\geq N\Delta t).\nobreak\hskip 0.0pt\hskip 15.00002pt minus
5.0pt\nobreak\vrule height=7.5pt,width=5.0pt,depth=2.5pt$

This result is not surprising, because of the close relationship between the
forward and inverse DFT.

The next result assumes the the FT is unknown and must be approximated by the
DFT, following which, the iDFT is used to invert the approximated FT to a PMF.
This theorem shows this error is also bounded.

###### Theorem 2.3

Given that the FT of a nonnegative lattice random variable is known up to a
fixed error bound, then the error bound of the iDFT of this FT can be bounded
by $2P(T\geq N\,\Delta t)$.

  * Proof

Mimicking the proof of Lemma 2.2 we replace $\hat{f}(\omega_{n})$ with
$\hat{f}(\omega_{n})+\delta_{n}$, where $\varepsilon=P(T\geq N\,\Delta t)$ and
$|\delta_{n}|\leq\varepsilon$. This gives:

$\displaystyle f_{k}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\left[\hat{f}(\omega_{n})+\delta_{n}\right]e^{2\pi
i\omega_{n}k\Delta t}$ $\displaystyle=$
$\displaystyle\frac{1}{N}\sum_{n=0}^{N-1}\hat{f}(\omega_{n})e^{2\pi
i\frac{nk}{N}}+\frac{1}{N}\sum_{n=0}^{N-1}\delta_{n}e^{2\pi i\frac{nk}{N}}$
$\displaystyle=$ $\displaystyle P(T=k\Delta t)+\sum_{j=N}^{\infty}P(T=j\Delta
t)\,\text{I}_{(k=j\text{ mod }N)}+\frac{1}{N}\sum_{n=0}^{N-1}\delta_{n}e^{2\pi
i\frac{nk}{N}}$

Therefore if we only have an approximation for $\hat{f}(\omega_{n})$ then,

$\displaystyle\left|f_{k}-P(T=k\Delta t)\right|$ $\displaystyle=$
$\displaystyle\left|\sum_{j=N}^{\infty}P(T=j\Delta t)\,\text{I}_{(k=j\text{
mod }N)}+\frac{1}{N}\sum_{n=0}^{N-1}\delta_{n}e^{2\pi i\frac{nk}{N}}\right|$
$\displaystyle\leq$ $\displaystyle\left|\sum_{j=N}^{\infty}P(T=j\Delta
t)\,\text{I}_{(k=j\text{ mod
}N)}\right|+\left|\frac{1}{N}\sum_{n=0}^{N-1}\delta_{n}e^{2\pi
i\frac{nk}{N}}\right|$ $\displaystyle\leq$
$\displaystyle\varepsilon+\frac{1}{N}\sum_{n=0}^{N-1}\left|\delta_{n}\right|\left|e^{2\pi
i\frac{nk}{N}}\right|$ $\displaystyle\leq$
$\displaystyle\varepsilon+\frac{\varepsilon}{N}\sum_{n=0}^{N-1}1\ =\
2\varepsilon.\nobreak\hskip 0.0pt\hskip 15.00002pt minus 5.0pt\nobreak\vrule
height=7.5pt,width=5.0pt,depth=2.5pt$

What we have not addressed, thus far, is the error introduced when
manipulating FTs in the Fourier domain. The primary reason we use CFs and FTs
is for the convenient theoretical properties but when $\hat{f}(\omega_{n})$ is
estimated, then when mathematical manipulation such as multiplication or
division occurs the error is magnified. We do not specifically address this
problem, but warn the practitioner of this added source of error.
Additionally, machine precision error also plays a part in the overall error
bound.

###  2.2 Finding the inversion error bounds

The primary problem when using the inverse DFT is that one may not know a
priori $N$ such that

$\sum_{n=0}^{N-1}P(T=n\Delta t)\geq 1-\varepsilon,$

for a given $\varepsilon$. So although the error is bounded, this bound is not
obvious without the exact PMF, which we do not usually have. There are a few
approaches to overcome this difficulty. One solution is to use an inequality
to bound $P(T>n\Delta t)$. One bound is Markov’s inequality:

$P(T\geq a)\leq\frac{E(T)}{a},\ \ \text{ for }a>0.$

Therefore if the first moment exists for the RV $T$, and we either know or can
estimate it, this method provides a conservative error bound. The primary
issue is finding $E(T)$. In our case the random variable $T$’s distribution is
a first passage distribution in a semi-Markov process. It turns out if all the
expectations to the individual transitions in the SMP are known, then finding
the first passage expectation is the solution to a set of linear equations.
Literature exists that explains how one can find the moments of first passage
distributions, for example see Zhang and Hou (2012) and Yao (1985).

Another inequality that can assist in bounding the error is Cantelli’s
inequality. For a random variable $T$ with $\mu=E(T)$, $\sigma^{2}=Var(T)$,
and $k>0$ we have

$P(T\geq k\sigma+\mu)\leq\frac{1}{1+k^{2}}.$

Therefore if $Var(T)<\infty$, and given $E(T)$ and $Var(T)$, Cantelli’s
inequality can be useful in bounding the DFT error. Where $k>\sigma/\mu$,
Cantelli’s inequality provides a smaller bound and should be used over
Markov’s inequality. Finding the variance of a first passage random variable
is similar to the expectation, again see Yao (1985) for details.

If the two inequalities prove to be impractical, then another approach can be
taken if certain assumptions can be made about the distribution of $T$.

###### Theorem 2.4

If for some index $M$ where the following inequalities are satisfied
$P(T=n\Delta t)\leq P(T=m\Delta t)$ and $M<m<n$, then the error for the iDFT
can be expressed as: Choose an even $N$ (the number of DFT samples) such that
$N>2M$, then for all $n=0,1,\ldots,(N/2-1)$

$\left|f_{n}-P(T=n\Delta t)\right|\leq f_{N/2+n}.$

Essentially what this is saying is that after a certain point, if the first
passage PMF, $f(t)$, is monotonically nonincreasing, then we can bound the
error using that fact alone. This technique is certainly not universally
applicable, but it does provide a working error bound if monotonicity
eventually occurs. To our knowledge PMFs used for modeling processes will
often meet this assumption.

  * Proof

From the proof of Lemma 2.2 we know

$f_{n}=\sum_{j=0}^{\infty}P(T=j\Delta t)\,\text{I}_{(n=j\text{ mod }N)},$

Which can be rewritten as

$f_{n}=\sum_{j=0}^{\infty}P(T=(n+jN)\Delta t).$

Which implies

$f_{N/2+n}=\sum_{j=0}^{\infty}P(T=(N/2+n+jN)\Delta t)$

therefore

$\left|f_{n}-P(T=n\Delta t)\right|=\sum_{j=1}^{\infty}P(T=(n+jN)\Delta t)$

but by monotonicity we know

$P\left(T=\left(N/2+n+jN\right)\Delta t\right)\geq
P\left(T=\left(n+(j+1)N\right)\Delta t\right)\text{ for all }j=0,1,2\ldots$

This implies

$f_{N/2+n}\geq\sum_{j=1}^{\infty}P(T=(n+jN)\Delta t).$

Therefore

$\left|f_{n}-P(T=n\Delta t)\right|\leq f_{N/2+n}.\nobreak\hskip 0.0pt\hskip
15.00002pt minus 5.0pt\nobreak\vrule height=7.5pt,width=5.0pt,depth=2.5pt$

This bound can be the more effective then the previous bounds, if the
condition exists for it to be applied. However, it is difficult to prove the
monotonicity condition in a particular situation, and if sufficient doubt
exists, another error bounding method should be applied.

Before we move to the application section, we suggest an even broader
condition than eventual monotonicity that will provide the same error bound.
This condition is:

###### Theorem 2.5

If there exists some nonnegative integers $n$ and $N/2$ and a positive integer
$k$, such that, if $n<N/2$, and $P\left(T=\left(n+kN/2\right)\Delta
t\right)\geq P\left(T=\left(n+(k+1)N/2\right)\Delta t\right)$ then, for a DFT
with $N$ samples,

$\left|f_{n}-P(T=n\Delta t)\right|\leq f_{n+N/2}.$

These types of distributions might be termed eventually periodic
nonincreasing. This condition is very broad and can be applied in nearly all
first passage distributions, although we are sure there exist some
pathological cases that do not fit in this class of distributions. The proof
of Theorem 2.5 follows the same argument as Theorem 2.4.

In the next section we demonstrate using the DFT to calculate FTs, their
inversion, and also it’s error bounds.

##  3 An application of discrete time semi-Markov processes

Consider the problem described in Barbu and Liminios (2008), the waste
treatment for a textile factory. If the treatment facility is working then the
waste can be discarded; if the unit fails the untreated waste must be stored
in a holding tank until the treatment facility is again functioning. However,
if the repair to the treatment facility takes too long the holding tank
becomes full, and the textile factory must halt production until the repair is
complete. Figure 2 is a graphical depiction of the process.

Figure 2: A graphical depiction of the textile waste treatment process.

We use the model parameterization of Barbu and Liminios (2008), which is:

$\displaystyle T_{12}$ $\displaystyle\sim$
$\displaystyle\text{geometric}(0.8),$ $\displaystyle T_{21}$
$\displaystyle\sim$ $\displaystyle\text{discrete Weibull}(0.3,0.5),$
$\displaystyle T_{23}$ $\displaystyle\sim$ $\displaystyle\text{discrete
Weibull}(0.5,0.7),\text{ and}$ $\displaystyle T_{31}$ $\displaystyle\sim$
$\displaystyle\text{discrete Weibull}(0.6,0.9).$

The discrete Weibull as defined in Nakagawa and Osaki (1975) (slightly
modified) is

$f(t|q,b)=\begin{cases}q^{(t-1)^{b}}-q^{t^{b}}&\mbox{if
}t\in\\{1,2,\ldots\\}\\\ 0&\text{otherwise.}\end{cases}$

The SMP parameter $p$ (see Figure 2) is set at 0.95, or in words, on average
95% of the repairs to the treatment facility are completed before the tank
becomes full.

A few of the quantities that may be of interest from this process are the
first passage PMF from state $1$ to state $3$, the expected amount of time
spent in state $3$ at some time $t$, and the probability the factory is
shutdown due to waste treatment failure at some time $t$. The formulas for
these quantities can be found in Warr and Collins (2011). For this paper we
focus on finding the first passage PMF from state $1$ to state $3$.

The first passage CF is given in Equation 1, where we replace CFs with FTs in
all instances. So to calculate the first passage FT from state 1 to state 3,
we need the FT of $T_{12}$, $T_{21}$, and $T_{23}$. The FT of geometric RV
$T_{12}$ is known in closed form, however, the FT for the discrete Weibull is
not. So in our computations we use the exact FT for $T_{12}$ and use the DFT
approximation for the other two.

We first want to calculate the mean and variance of $T_{12}$, $T_{21}$, and
$T_{23}$ which will allow us to use the Cantelli inequality to bound our
error. Table 1 shows the expectations and variances for these RVs.

Table 1: The mean and variance of waiting time random variables in the textile waste treatment process. | Mean | Variance
---|---|---
$T_{12}$ | 1.2500 | 0.3125
$T_{21}$ | 2.0769 | 9.0765
$T_{23}$ | 2.7300 | 9.4618
$T_{13*}$ | 67.191 | 4394.1

These quantities allow us to calculate the number $N$ we need to use to obtain
a desired error bound. We choose $\varepsilon=10^{-6}$ which implies $k\geq
66356$. Therefore if $N=2^{17}$ the pointwise error for each probability will
be smaller than 2$\varepsilon$. The computation time of calculating the first
passage PMF is less than one second (on a Windows 7 PC with an AMD AthlonTM
7750 2.7 GHz dual-core processor).

The plot in Figure 3 shows what the first passage PMF from state $1$ to state
$3$ looks like for the first one hundred points. Using the developed theory in
this paper, we are assured the pointwise error is less than or equal to
2$\varepsilon$. Again this ignores the error introduced by multiplying and
dividing the FTs (as in Equation 1) and the machine round-off error.

Figure 3: The PMF of the first passage from state 1, “Working”, to state 3,
“Treatment failed, tank full”.

Figure 3 indicates that the PMF of this first passage distribution is
monotonically decreasing after roughly time $20$. Therefore we can attempt to
apply Theorem 2.4. Since we estimated that $P(T_{13*}=609)<\varepsilon$
Therefore if we choose $N=1218$ we only need to calculate roughly $1\%$ of the
values in the FFT and can still claim the pointwise error is less than or
equal to 2$\varepsilon$. This example shows the potential computation savings
of using Theorem 2.4 for first passage random variables. Also, Theorem 2.4
does not assume a finite mean or variance, but a monotonically decreasing PMF
after a selected point on the support. In this example we worked our way, by
trial and error, from a large $N$ down to a smaller $N$, however, we are also
able to work our way up from a small $N$ to a larger $N$. This can reduce the
computation time to find the desired error bound.

##  4 Discussion

It has been our goal to show for lattice random variables the DFT/FFT computes
the desired first passage PMF extremely quickly and to a prescribed accuracy.
It is often very desirable to handle probability problems in the transformed
CF domain, but computational methods to invert them back into the time or
spatial domain have been the largest deterrent. The DFT is a excellent
solution for the inversion of characteristic functions to PMFs. The DFT is
very fast using the FFT algorithm and it also provides error bounds for
estimates.

##  5 Acknowledgments

The authors would like to thank Patrick Chapin, David Collins and Aparna
Huzurbazar for their advice, assistance, and encouragement.

##  6 Appendix – R Code

    ##Discrete Weibull PMF
    dweibulldisc<-function(x,q,b){
      temp1=q^((x-1)^b)-q^(x^b); temp2=x-floor(x)
      temp3=temp2<1e-15 ;  temp4<-x==0; temp1[temp4]<-0
      return(temp1*temp3)
    }

    ##p is the probability of the treatment facility will be fixed
    ## before the holding tank becomes full
    p = 0.95

    N = 2^17
    support = 0:(N-1)

    ## The DFT samples of the two of the transition distributions
    T21 = dweibulldisc(support,0.3,0.5)
    T23 = dweibulldisc(support,0.5,0.7)

    ## The Fourier transforms of the 3 transition distributions
    F12 = p*exp(-2*pi*1i*support/N)/(1-(1-p)*exp(-2*pi*1i*support/N))
    F21 = fft(T21);  F23 = fft(T23)

    ## The Fourier transform of the first passage distribution from
    ## state 1 to state 3
    F_1st_Pas_13 = ((1-p)*F12*F23)/(1-p*F12*F21)

    ## The first passage PMF from state 1 to state 3
    T_1st_Pas_13 = 1/N*Re( fft(F_1st_Pas_13,inverse=T) )

## References

  * (1)
  * Barbu and Liminios (2008) Barbu, V. S. and Liminios, N. (2008).  Semi-Markov Chains and Hidden Semi-Markov Models Toward Applications: Their Use in Reliability and DNA Analysis, Springer, New York.
  * Briggs and Henson (1995) Briggs, W. L. and Henson, V. E. (1995).  The DFT: An Owner’s Manual for the Discrete Fourier Transform, SIAM, Philadelphia.
  * Hughett (1998) Hughett, P. (1998).  Error bounds for numerical inversion of a probability characteristic function, SIAM Journal on Numerical Analysis 35(4): 1368–1392.
  * Huzurbazar (2005) Huzurbazar, A. V. (2005).  Flowgraph Models for Multistate Time-to-Event Data, Wiley, New York.
  * Nakagawa and Osaki (1975) Nakagawa, T. and Osaki, S. (1975).  The discrete Weibull distribution, IEEE Transactions on Reliability R-24(5): 300–301.
  * Pyke (1961) Pyke, R. (1961).  Markov renewal processes with finitely many states, The Annals of Mathematical Statistics 32(4): 1243–1259.
  * R Development Core Team (2009) R Development Core Team (2009).  R: A Language and Environment for Statistical Computing, R Foundation for Statistical Computing, Vienna, Austria.  ISBN 3-900051-07-0.
http://www.R-project.org

  * Warr and Collins (2011) Warr, R. L. and Collins, D. H. (2011).  A comprehensive method for solving finite-state semi-Markov processes, Technical Report LA-UR-11-01596, Los Alamos National Laboratory, Los Alamos, NM.
  * Yao (1985) Yao, D. D. (1985).  First-passage-time moments of Markov processes, Journal of Applied Probability 22(4): 939–945.
  * Zhang and Hou (2012) Zhang, X. and Hou, Z. (2012).  The first-passage times of phase semi-Markov processes, Statistics & Probability Letters 82(1): 40 – 48.