text:
# Setup the Seurat Object

For this tutorial, we will be analyzing the a dataset of Peripheral Blood Mononuclear Cells (PBMC) freely available from 10X Genomics. There are 2,700 single cells that were sequenced on the Illumina NextSeq 500. The raw data can be found here.

We start by reading in the data. The Read10X() function reads in the output of the cellranger pipeline from 10X, returning a unique molecular identified (UMI) count matrix. The values in this matrix represent the number of molecules for each feature (i.e. gene; row) that are detected in each cell (column).

We next use the count matrix to create a Seurat object. The object serves as a container that contains both data (like the count matrix) and analysis (like PCA, or clustering results) for a single-cell dataset. For a technical discussion of the Seurat object structure, check out our GitHub Wiki. For example, the count matrix is stored in pbmc[["RNA"]]@counts.

library(dplyr)
library(Seurat)
library(patchwork)

# Initialize the Seurat object with the raw (non-normalized data).
pbmc <- CreateSeuratObject(counts = pbmc.data, project = "pbmc3k", min.cells = 3, min.features = 200)
pbmc
## An object of class Seurat
## 13714 features across 2700 samples within 1 assay
## Active assay: RNA (13714 features, 0 variable features)

What does data in a count matrix look like?

# Lets examine a few genes in the first thirty cells
pbmc.data[c("CD3D", "TCL1A", "MS4A1"), 1:30]
## 3 x 30 sparse Matrix of class "dgCMatrix"
##
## CD3D  4 . 10 . . 1 2 3 1 . . 2 7 1 . . 1 3 . 2  3 . . . . . 3 4 1 5
## TCL1A . .  . . . . . . 1 . . . . . . . . . . .  . 1 . . . . . . . .
## MS4A1 . 6  . . . . . . 1 1 1 . . . . . . . . . 36 1 2 . . 2 . . . .

The . values in the matrix represent 0s (no molecules detected). Since most values in an scRNA-seq matrix are 0, Seurat uses a sparse-matrix representation whenever possible. This results in significant memory and speed savings for Drop-seq/inDrop/10x data.

dense.size <- object.size(as.matrix(pbmc.data))
dense.size
## 709591472 bytes
sparse.size <- object.size(pbmc.data)
sparse.size
## 29905192 bytes
dense.size/sparse.size
## 23.7 bytes

# Standard pre-processing workflow

The steps below encompass the standard pre-processing workflow for scRNA-seq data in Seurat. These represent the selection and filtration of cells based on QC metrics, data normalization and scaling, and the detection of highly variable features.

## QC and selecting cells for further analysis

Seurat allows you to easily explore QC metrics and filter cells based on any user-defined criteria. A few QC metrics commonly used by the community include

• The number of unique genes detected in each cell.
• Low-quality cells or empty droplets will often have very few genes
• Cell doublets or multiplets may exhibit an aberrantly high gene count
• Similarly, the total number of molecules detected within a cell (correlates strongly with unique genes)
• The percentage of reads that map to the mitochondrial genome
• Low-quality / dying cells often exhibit extensive mitochondrial contamination
• We calculate mitochondrial QC metrics with the PercentageFeatureSet() function, which calculates the percentage of counts originating from a set of features
• We use the set of all genes starting with MT- as a set of mitochondrial genes
# The [[ operator can add columns to object metadata. This is a great place to stash QC stats
pbmc[["percent.mt"]] <- PercentageFeatureSet(pbmc, pattern = "^MT-")

Where are QC metrics stored in Seurat?

• The number of unique genes and total molecules are automatically calculated during CreateSeuratObject()
• You can find them stored in the object meta data
# Show QC metrics for the first 5 cells
head(pbmc@meta.data, 5)
##                  orig.ident nCount_RNA nFeature_RNA percent.mt
## AAACATACAACCAC-1     pbmc3k       2419          779  3.0177759
## AAACATTGAGCTAC-1     pbmc3k       4903         1352  3.7935958
## AAACATTGATCAGC-1     pbmc3k       3147         1129  0.8897363
## AAACCGTGCTTCCG-1     pbmc3k       2639          960  1.7430845
## AAACCGTGTATGCG-1     pbmc3k        980          521  1.2244898

In the example below, we visualize QC metrics, and use these to filter cells.

• We filter cells that have unique feature counts over 2,500 or less than 200
• We filter cells that have >5% mitochondrial counts
# Visualize QC metrics as a violin plot
VlnPlot(pbmc, features = c("nFeature_RNA", "nCount_RNA", "percent.mt"), ncol = 3)

# FeatureScatter is typically used to visualize feature-feature relationships, but can be used
# for anything calculated by the object, i.e. columns in object metadata, PC scores etc.

plot1 <- FeatureScatter(pbmc, feature1 = "nCount_RNA", feature2 = "percent.mt")
plot2 <- FeatureScatter(pbmc, feature1 = "nCount_RNA", feature2 = "nFeature_RNA")
plot1 + plot2

pbmc <- subset(pbmc, subset = nFeature_RNA > 200 & nFeature_RNA < 2500 & percent.mt < 5)

# Normalizing the data

After removing unwanted cells from the dataset, the next step is to normalize the data. By default, we employ a global-scaling normalization method “LogNormalize” that normalizes the feature expression measurements for each cell by the total expression, multiplies this by a scale factor (10,000 by default), and log-transforms the result. Normalized values are stored in pbmc[["RNA"]]@data.

pbmc <- NormalizeData(pbmc, normalization.method = "LogNormalize", scale.factor = 10000)

For clarity, in this previous line of code (and in future commands), we provide the default values for certain parameters in the function call. However, this isn’t required and the same behavior can be achieved with:

pbmc <- NormalizeData(pbmc)

# Identification of highly variable features (feature selection)

We next calculate a subset of features that exhibit high cell-to-cell variation in the dataset (i.e, they are highly expressed in some cells, and lowly expressed in others). We and others have found that focusing on these genes in downstream analysis helps to highlight biological signal in single-cell datasets.

Our procedure in Seurat is described in detail here, and improves on previous versions by directly modeling the mean-variance relationship inherent in single-cell data, and is implemented in the FindVariableFeatures() function. By default, we return 2,000 features per dataset. These will be used in downstream analysis, like PCA.

pbmc <- FindVariableFeatures(pbmc, selection.method = "vst", nfeatures = 2000)

# Identify the 10 most highly variable genes

# plot variable features with and without labels
plot1 <- VariableFeaturePlot(pbmc)
plot2 <- LabelPoints(plot = plot1, points = top10, repel = TRUE)
plot1 + plot2

# Scaling the data

Next, we apply a linear transformation (‘scaling’) that is a standard pre-processing step prior to dimensional reduction techniques like PCA. The ScaleData() function:

• Shifts the expression of each gene, so that the mean expression across cells is 0
• Scales the expression of each gene, so that the variance across cells is 1
• This step gives equal weight in downstream analyses, so that highly-expressed genes do not dominate
• The results of this are stored in pbmc[["RNA"]]@scale.data
all.genes <- rownames(pbmc)
pbmc <- ScaleData(pbmc, features = all.genes)

This step takes too long! Can I make it faster?

Scaling is an essential step in the Seurat workflow, but only on genes that will be used as input to PCA. Therefore, the default in ScaleData() is only to perform scaling on the previously identified variable features (2,000 by default). To do this, omit the features argument in the previous function call, i.e.

pbmc <- ScaleData(pbmc)
Your PCA and clustering results will be unaffected. However, Seurat heatmaps (produced as shown below with DoHeatmap()) require genes in the heatmap to be scaled, to make sure highly-expressed genes don’t dominate the heatmap. To make sure we don’t leave any genes out of the heatmap later, we are scaling all genes in this tutorial.

How can I remove unwanted sources of variation, as in Seurat v2?

In Seurat v2 we also use the ScaleData() function to remove unwanted sources of variation from a single-cell dataset. For example, we could ‘regress out’ heterogeneity associated with (for example) cell cycle stage, or mitochondrial contamination. These features are still supported in ScaleData() in Seurat v3, i.e.:

pbmc <- ScaleData(pbmc, vars.to.regress = "percent.mt")
However, particularly for advanced users who would like to use this functionality, we strongly recommend the use of our new normalization workflow, SCTransform(). The method is described in our paper, with a separate vignette using Seurat v3 here. As with ScaleData(), the function SCTransform() also includes a vars.to.regress parameter.

# Perform linear dimensional reduction

Next we perform PCA on the scaled data. By default, only the previously determined variable features are used as input, but can be defined using features argument if you wish to choose a different subset.

pbmc <- RunPCA(pbmc, features = VariableFeatures(object = pbmc))

Seurat provides several useful ways of visualizing both cells and features that define the PCA, including VizDimReduction(), DimPlot(), and DimHeatmap()

# Examine and visualize PCA results a few different ways
print(pbmc[["pca"]], dims = 1:5, nfeatures = 5)
## PC_ 1
## Positive:  CST3, TYROBP, LST1, AIF1, FTL
## Negative:  MALAT1, LTB, IL32, IL7R, CD2
## PC_ 2
## Positive:  CD79A, MS4A1, TCL1A, HLA-DQA1, HLA-DQB1
## Negative:  NKG7, PRF1, CST7, GZMB, GZMA
## PC_ 3
## Positive:  HLA-DQA1, CD79A, CD79B, HLA-DQB1, HLA-DPB1
## Negative:  PPBP, PF4, SDPR, SPARC, GNG11
## PC_ 4
## Positive:  HLA-DQA1, CD79B, CD79A, MS4A1, HLA-DQB1
## Negative:  VIM, IL7R, S100A6, IL32, S100A8
## PC_ 5
## Positive:  GZMB, NKG7, S100A8, FGFBP2, GNLY
## Negative:  LTB, IL7R, CKB, VIM, MS4A7
VizDimLoadings(pbmc, dims = 1:2, reduction = "pca")

DimPlot(pbmc, reduction = "pca")

In particular DimHeatmap() allows for easy exploration of the primary sources of heterogeneity in a dataset, and can be useful when trying to decide which PCs to include for further downstream analyses. Both cells and features are ordered according to their PCA scores. Setting cells to a number plots the ‘extreme’ cells on both ends of the spectrum, which dramatically speeds plotting for large datasets. Though clearly a supervised analysis, we find this to be a valuable tool for exploring correlated feature sets.

DimHeatmap(pbmc, dims = 1, cells = 500, balanced = TRUE)

DimHeatmap(pbmc, dims = 1:15, cells = 500, balanced = TRUE)

# Determine the ‘dimensionality’ of the dataset

To overcome the extensive technical noise in any single feature for scRNA-seq data, Seurat clusters cells based on their PCA scores, with each PC essentially representing a ‘metafeature’ that combines information across a correlated feature set. The top principal components therefore represent a robust compression of the dataset. However, how many components should we choose to include? 10? 20? 100?

In Macosko et al, we implemented a resampling test inspired by the JackStraw procedure. We randomly permute a subset of the data (1% by default) and rerun PCA, constructing a ‘null distribution’ of feature scores, and repeat this procedure. We identify ‘significant’ PCs as those who have a strong enrichment of low p-value features.

# NOTE: This process can take a long time for big datasets, comment out for expediency. More
# approximate techniques such as those implemented in ElbowPlot() can be used to reduce
# computation time
pbmc <- JackStraw(pbmc, num.replicate = 100)
pbmc <- ScoreJackStraw(pbmc, dims = 1:20)

The JackStrawPlot() function provides a visualization tool for comparing the distribution of p-values for each PC with a uniform distribution (dashed line). ‘Significant’ PCs will show a strong enrichment of features with low p-values (solid curve above the dashed line). In this case it appears that there is a sharp drop-off in significance after the first 10-12 PCs.

JackStrawPlot(pbmc, dims = 1:15)

An alternative heuristic method generates an ‘Elbow plot’: a ranking of principle components based on the percentage of variance explained by each one (ElbowPlot() function). In this example, we can observe an ‘elbow’ around PC9-10, suggesting that the majority of true signal is captured in the first 10 PCs.

ElbowPlot(pbmc)

Identifying the true dimensionality of a dataset – can be challenging/uncertain for the user. We therefore suggest these three approaches to consider. The first is more supervised, exploring PCs to determine relevant sources of heterogeneity, and could be used in conjunction with GSEA for example. The second implements a statistical test based on a random null model, but is time-consuming for large datasets, and may not return a clear PC cutoff. The third is a heuristic that is commonly used, and can be calculated instantly. In this example, all three approaches yielded similar results, but we might have been justified in choosing anything between PC 7-12 as a cutoff.

We chose 10 here, but encourage users to consider the following:

• Dendritic cell and NK aficionados may recognize that genes strongly associated with PCs 12 and 13 define rare immune subsets (i.e. MZB1 is a marker for plasmacytoid DCs). However, these groups are so rare, they are difficult to distinguish from background noise for a dataset of this size without prior knowledge.
• We encourage users to repeat downstream analyses with a different number of PCs (10, 15, or even 50!). As you will observe, the results often do not differ dramatically.
• We advise users to err on the higher side when choosing this parameter. For example, performing downstream analyses with only 5 PCs does significantly and adversely affect results.

# Cluster the cells

Seurat v3 applies a graph-based clustering approach, building upon initial strategies in (Macosko et al). Importantly, the distance metric which drives the clustering analysis (based on previously identified PCs) remains the same. However, our approach to partitioning the cellular distance matrix into clusters has dramatically improved. Our approach was heavily inspired by recent manuscripts which applied graph-based clustering approaches to scRNA-seq data [SNN-Cliq, Xu and Su, Bioinformatics, 2015] and CyTOF data [PhenoGraph, Levine et al., Cell, 2015]. Briefly, these methods embed cells in a graph structure - for example a K-nearest neighbor (KNN) graph, with edges drawn between cells with similar feature expression patterns, and then attempt to partition this graph into highly interconnected ‘quasi-cliques’ or ‘communities’.

As in PhenoGraph, we first construct a KNN graph based on the euclidean distance in PCA space, and refine the edge weights between any two cells based on the shared overlap in their local neighborhoods (Jaccard similarity). This step is performed using the FindNeighbors() function, and takes as input the previously defined dimensionality of the dataset (first 10 PCs).

To cluster the cells, we next apply modularity optimization techniques such as the Louvain algorithm (default) or SLM [SLM, Blondel et al., Journal of Statistical Mechanics], to iteratively group cells together, with the goal of optimizing the standard modularity function. The FindClusters() function implements this procedure, and contains a resolution parameter that sets the ‘granularity’ of the downstream clustering, with increased values leading to a greater number of clusters. We find that setting this parameter between 0.4-1.2 typically returns good results for single-cell datasets of around 3K cells. Optimal resolution often increases for larger datasets. The clusters can be found using the Idents() function.

pbmc <- FindNeighbors(pbmc, dims = 1:10)
pbmc <- FindClusters(pbmc, resolution = 0.5)
## Modularity Optimizer version 1.3.0 by Ludo Waltman and Nees Jan van Eck
##
## Number of nodes: 2638
## Number of edges: 95927
##
## Running Louvain algorithm...
## Maximum modularity in 10 random starts: 0.8728
## Number of communities: 9
## Elapsed time: 0 seconds
# Look at cluster IDs of the first 5 cells
head(Idents(pbmc), 5)
## AAACATACAACCAC-1 AAACATTGAGCTAC-1 AAACATTGATCAGC-1 AAACCGTGCTTCCG-1
##                2                3                2                1
## AAACCGTGTATGCG-1
##                6
## Levels: 0 1 2 3 4 5 6 7 8

# Run non-linear dimensional reduction (UMAP/tSNE)

Seurat offers several non-linear dimensional reduction techniques, such as tSNE and UMAP, to visualize and explore these datasets. The goal of these algorithms is to learn the underlying manifold of the data in order to place similar cells together in low-dimensional space. Cells within the graph-based clusters determined above should co-localize on these dimension reduction plots. As input to the UMAP and tSNE, we suggest using the same PCs as input to the clustering analysis.

# If you haven't installed UMAP, you can do so via reticulate::py_install(packages =
# 'umap-learn')
pbmc <- RunUMAP(pbmc, dims = 1:10)
# note that you can set label = TRUE or use the LabelClusters function to help label
# individual clusters
DimPlot(pbmc, reduction = "umap")

You can save the object at this point so that it can easily be loaded back in without having to rerun the computationally intensive steps performed above, or easily shared with collaborators.

saveRDS(pbmc, file = "../output/pbmc_tutorial.rds")

# Finding differentially expressed features (cluster biomarkers)

Seurat can help you find markers that define clusters via differential expression. By default, it identifies positive and negative markers of a single cluster (specified in ident.1), compared to all other cells. FindAllMarkers() automates this process for all clusters, but you can also test groups of clusters vs. each other, or against all cells.

The min.pct argument requires a feature to be detected at a minimum percentage in either of the two groups of cells, and the thresh.test argument requires a feature to be differentially expressed (on average) by some amount between the two groups. You can set both of these to 0, but with a dramatic increase in time - since this will test a large number of features that are unlikely to be highly discriminatory. As another option to speed up these computations, max.cells.per.ident can be set. This will downsample each identity class to have no more cells than whatever this is set to. While there is generally going to be a loss in power, the speed increases can be significant and the most highly differentially expressed features will likely still rise to the top.

# find all markers of cluster 2
cluster2.markers <- FindMarkers(pbmc, ident.1 = 2, min.pct = 0.25)
head(cluster2.markers, n = 5)
##             p_val avg_log2FC pct.1 pct.2    p_val_adj
## IL32 2.892340e-90  1.2013522 0.947 0.465 3.966555e-86
## LTB  1.060121e-86  1.2695776 0.981 0.643 1.453850e-82
## CD3D 8.794641e-71  0.9389621 0.922 0.432 1.206097e-66
## IL7R 3.516098e-68  1.1873213 0.750 0.326 4.821977e-64
## LDHB 1.642480e-67  0.8969774 0.954 0.614 2.252497e-63
# find all markers distinguishing cluster 5 from clusters 0 and 3
cluster5.markers <- FindMarkers(pbmc, ident.1 = 5, ident.2 = c(0, 3), min.pct = 0.25)
head(cluster5.markers, n = 5)
##                       p_val avg_log2FC pct.1 pct.2     p_val_adj
## FCGR3A        8.246578e-205   4.261495 0.975 0.040 1.130936e-200
## IFITM3        1.677613e-195   3.879339 0.975 0.049 2.300678e-191
## CFD           2.401156e-193   3.405492 0.938 0.038 3.292945e-189
## CD68          2.900384e-191   3.020484 0.926 0.035 3.977587e-187
## RP11-290F20.3 2.513244e-186   2.720057 0.840 0.017 3.446663e-182
# find markers for every cluster compared to all remaining cells, report only the positive
# ones
pbmc.markers <- FindAllMarkers(pbmc, only.pos = TRUE, min.pct = 0.25, logfc.threshold = 0.25)
pbmc.markers %>%
group_by(cluster) %>%
slice_max(n = 2, order_by = avg_log2FC)
## # A tibble: 18 × 7
## # Groups:   cluster [9]
##        p_val avg_log2FC pct.1 pct.2 p_val_adj cluster gene
##        <dbl>      <dbl> <dbl> <dbl>     <dbl> <fct>   <chr>
##  1 9.57e- 88       1.36 0.447 0.108 1.31e- 83 0       CCR7
##  2 3.75e-112       1.09 0.912 0.592 5.14e-108 0       LDHB
##  3 0               5.57 0.996 0.215 0         1       S100A9
##  4 0               5.48 0.975 0.121 0         1       S100A8
##  5 1.06e- 86       1.27 0.981 0.643 1.45e- 82 2       LTB
##  6 2.97e- 58       1.23 0.42  0.111 4.07e- 54 2       AQP3
##  7 0               4.31 0.936 0.041 0         3       CD79A
##  8 9.48e-271       3.59 0.622 0.022 1.30e-266 3       TCL1A
##  9 5.61e-202       3.10 0.983 0.234 7.70e-198 4       CCL5
## 10 7.25e-165       3.00 0.577 0.055 9.95e-161 4       GZMK
## 11 3.51e-184       3.31 0.975 0.134 4.82e-180 5       FCGR3A
## 12 2.03e-125       3.09 1     0.315 2.78e-121 5       LST1
## 13 3.13e-191       5.32 0.961 0.131 4.30e-187 6       GNLY
## 14 7.95e-269       4.83 0.961 0.068 1.09e-264 6       GZMB
## 15 1.48e-220       3.87 0.812 0.011 2.03e-216 7       FCER1A
## 16 1.67e- 21       2.87 1     0.513 2.28e- 17 7       HLA-DPB1
## 17 1.92e-102       8.59 1     0.024 2.63e- 98 8       PPBP
## 18 9.25e-186       7.29 1     0.011 1.27e-181 8       PF4

Seurat has several tests for differential expression which can be set with the test.use parameter (see our DE vignette for details). For example, the ROC test returns the ‘classification power’ for any individual marker (ranging from 0 - random, to 1 - perfect).

cluster0.markers <- FindMarkers(pbmc, ident.1 = 0, logfc.threshold = 0.25, test.use = "roc", only.pos = TRUE)

We include several tools for visualizing marker expression. VlnPlot() (shows expression probability distributions across clusters), and FeaturePlot() (visualizes feature expression on a tSNE or PCA plot) are our most commonly used visualizations. We also suggest exploring RidgePlot(), CellScatter(), and DotPlot() as additional methods to view your dataset.

VlnPlot(pbmc, features = c("MS4A1", "CD79A"))

# you can plot raw counts as well
VlnPlot(pbmc, features = c("NKG7", "PF4"), slot = "counts", log = TRUE)

FeaturePlot(pbmc, features = c("MS4A1", "GNLY", "CD3E", "CD14", "FCER1A", "FCGR3A", "LYZ", "PPBP",
"CD8A"))

DoHeatmap() generates an expression heatmap for given cells and features. In this case, we are plotting the top 20 markers (or all markers if less than 20) for each cluster.

pbmc.markers %>%
group_by(cluster) %>%
top_n(n = 10, wt = avg_log2FC) -> top10
DoHeatmap(pbmc, features = top10\$gene) + NoLegend()

# Assigning cell type identity to clusters

Fortunately in the case of this dataset, we can use canonical markers to easily match the unbiased clustering to known cell types:

Cluster ID Markers Cell Type
0 IL7R, CCR7 Naive CD4+ T
1 CD14, LYZ CD14+ Mono
2 IL7R, S100A4 Memory CD4+
3 MS4A1 B
4 CD8A CD8+ T
5 FCGR3A, MS4A7 FCGR3A+ Mono
6 GNLY, NKG7 NK
7 FCER1A, CST3 DC
8 PPBP Platelet
new.cluster.ids <- c("Naive CD4 T", "CD14+ Mono", "Memory CD4 T", "B", "CD8 T", "FCGR3A+ Mono",
"NK", "DC", "Platelet")
names(new.cluster.ids) <- levels(pbmc)
pbmc <- RenameIdents(pbmc, new.cluster.ids)
DimPlot(pbmc, reduction = "umap", label = TRUE, pt.size = 0.5) + NoLegend()

saveRDS(pbmc, file = "../output/pbmc3k_final.rds")

Session Info

sessionInfo()
## R version 4.1.0 (2021-05-18)
## Platform: x86_64-pc-linux-gnu (64-bit)
## Running under: Ubuntu 20.04.2 LTS
##
## Matrix products: default
##
## locale:
##  [1] LC_CTYPE=en_US.UTF-8       LC_NUMERIC=C
##  [3] LC_TIME=en_US.UTF-8        LC_COLLATE=en_US.UTF-8
##  [5] LC_MONETARY=en_US.UTF-8    LC_MESSAGES=C
##  [7] LC_PAPER=en_US.UTF-8       LC_NAME=C
## [11] LC_MEASUREMENT=en_US.UTF-8 LC_IDENTIFICATION=C
##
## attached base packages:
## [1] stats     graphics  grDevices utils     datasets  methods   base
##
## other attached packages:
## [1] ggplot2_3.3.5      patchwork_1.1.1    SeuratObject_4.0.4 Seurat_4.0.6
## [5] dplyr_1.0.7
##
## loaded via a namespace (and not attached):
##   [1] Rtsne_0.15             colorspace_2.0-2       deldir_1.0-6
##   [4] ellipsis_0.3.2         ggridges_0.5.3         rprojroot_2.0.2
##   [7] fs_1.5.2               spatstat.data_2.1-2    farver_2.1.0
##  [10] leiden_0.3.9           listenv_0.8.0          ggrepel_0.9.1
##  [13] RSpectra_0.16-0        fansi_1.0.0            codetools_0.2-18
##  [16] splines_4.1.0          cachem_1.0.6           knitr_1.33
##  [19] polyclip_1.10-0        jsonlite_1.7.2         ica_1.0-2
##  [22] cluster_2.1.2          png_0.1-7              uwot_0.1.11
##  [25] shiny_1.7.1            sctransform_0.3.2.9011 spatstat.sparse_2.1-0
##  [28] compiler_4.1.0         httr_1.4.2             assertthat_0.2.1
##  [31] Matrix_1.3-3           fastmap_1.1.0          lazyeval_0.2.2
##  [34] cli_3.1.0              limma_3.48.0           later_1.3.0
##  [37] formatR_1.11           htmltools_0.5.2        tools_4.1.0
##  [40] igraph_1.2.11          gtable_0.3.0           glue_1.6.0
##  [43] RANN_2.6.1             reshape2_1.4.4         Rcpp_1.0.7
##  [46] scattermore_0.7        jquerylib_0.1.4        pkgdown_1.6.1
##  [49] vctrs_0.3.8            nlme_3.1-152           lmtest_0.9-39
##  [52] xfun_0.25              stringr_1.4.0          globals_0.14.0
##  [55] mime_0.12              miniUI_0.1.1.1         lifecycle_1.0.1
##  [58] irlba_2.3.5            goftest_1.2-3          future_1.23.0
##  [61] MASS_7.3-54            zoo_1.8-9              scales_1.1.1
##  [64] spatstat.core_2.3-2    ragg_1.1.3             promises_1.2.0.1
##  [67] spatstat.utils_2.3-0   parallel_4.1.0         RColorBrewer_1.1-2
##  [70] yaml_2.2.1             memoise_2.0.0          reticulate_1.22
##  [73] pbapply_1.5-0          gridExtra_2.3          sass_0.4.0
##  [76] rpart_4.1-15           stringi_1.7.6          highr_0.9
##  [79] desc_1.4.0             rlang_0.4.12           pkgconfig_2.0.3
##  [82] systemfonts_1.0.2      matrixStats_0.61.0     evaluate_0.14
##  [85] lattice_0.20-44        tensor_1.5             ROCR_1.0-11
##  [88] purrr_0.3.4            labeling_0.4.2         htmlwidgets_1.5.4
##  [91] cowplot_1.1.1          tidyselect_1.1.1       parallelly_1.30.0
##  [94] RcppAnnoy_0.0.19       plyr_1.8.6             magrittr_2.0.1
##  [97] R6_2.5.1               generics_0.1.1         DBI_1.1.1
## [100] withr_2.4.3            mgcv_1.8-35            pillar_1.6.4
## [103] fitdistrplus_1.1-6     abind_1.4-5            survival_3.2-11
## [106] tibble_3.1.6           future.apply_1.8.1     crayon_1.4.2
## [109] KernSmooth_2.23-20     utf8_1.2.2             spatstat.geom_2.3-1
## [112] plotly_4.10.0          rmarkdown_2.10         grid_4.1.0
## [115] data.table_1.14.2      digest_0.6.29          xtable_1.8-4
## [118] tidyr_1.1.4            httpuv_1.6.5           textshaping_0.3.5
## [121] munsell_0.5.0          viridisLite_0.4.0      bslib_0.3.1


text:
This problem and its natural higher-dimensional generalization is connected with the recent MO questions Covering a unit ball with balls half the radius and covering disks with smaller disks : let $K_d$ be the smallest constant such that for any sequence $(z_i)_{i \geq 1}$ of vectors of $\mathbb{R}^d$ of (euclidean) norm at most one, there's some choice of signs $s_i = \pm 1$ such that the partial sums $\sum_{1 \leq i \leq n} s_i z_i$ are all bounded by $K_d$.
Now let $N_d$ be the minimal number of balls of radius $\frac{1}{2}$ needed to cover a ball of radius $1$ (in $\mathbb{R^d}$). I claim that $K_d \leq N_d$.
Proof : Let $K_{d,n}$ be the same constant as $K_d$, but for which we require only the first $n$ partial sums to be bounded by $K_{d,n}$. Then a straightforward averaging argument yields $K_{d,n} \leq \sqrt{n}$. sqrt{n} \leq n$. Now let$n > N_d$. Fixing a covering of the unit ball with$N_d$balls of radius$\frac{1}{2}$, then there must be two distinct$ i < j \leq N_d +1$such that$z_i$and$z_j$lie in the same ball of radius$\frac{1}{2}$, and hence must satisfy$|| z_i - z_j || \leq 1$. If we replace$z_j$by$z_j - z_i$, suppress$z_i$, and then use$K_{d,n-1}$, we get a sequence of signs which achieve$K_{d,n} \leq \max ( N_d, K_{d,n-1} ) $. But Kônig's lemma (for infinite binary trees) gives$K_d \leq \sup_{n} K_{d,n} $, hence the desired result. 1 What follows is not an answer, but is too long for a comment. This problem and its natural higher-dimensional generalization is connected with the recent MO questions Covering a unit ball with balls half the radius and covering disks with smaller disks : let$K_d$be the smallest constant such that for any sequence$(z_i)_{i \geq 1}$of vectors of$\mathbb{R}^d$of (euclidean) norm at most one, there's some choice of signs$s_i = \pm 1$such that the partial sums$\sum_{1 \leq i \leq n} s_i z_i$are all bounded by$K_d$. Now let$N_d$be the minimal number of balls of radius$\frac{1}{2}$needed to cover a ball of radius$1$(in$\mathbb{R^d}$). I claim that$K_d \leq N_d$. Proof : Let$K_{d,n}$be the same constant as$K_d$, but for which we require only the first$n$partial sums to be bounded by$K_{d,n}$. Then a straightforward averaging argument yields$K_{d,n} \leq \sqrt{n}$. Now let$n > N_d$. Fixing a covering of the unit ball with$N_d$balls of radius$\frac{1}{2}$, then there must be two distinct$ i < j \leq N_d +1$such that$z_i$and$z_j$lie in the same ball of radius$\frac{1}{2}$, and hence must satisfy$|| z_i - z_j || \leq 1$. If we replace$z_j$by$z_j - z_i$, suppress$z_i$, and then use$K_{d,n-1}$, we get a sequence of signs which achieve$K_{d,n} \leq \max ( N_d, K_{d,n-1} ) $. But Kônig's lemma (for infinite binary trees) gives$K_d \leq \sup_{n} K_{d,n} \$, hence the desired result.

format: plain


text:
## Stream: MetaCoq

### Topic: Are typing derivations property ?

#### Kenji Maillard (Aug 27 2020 at 08:37):

Looking naively at the typing derivations for PCUIC (found there), I was wondering whether the derivations are a property of the triple $(\Gamma, t, A)$ or a structure over such a triple ?
For instance, are there lemmas showing that there is at most one typing derivation ? (likely not the case because conversion could apply anywhere)
Or if they are multiple typing derivations, whether a canonical one can be singled out ? (More likely if there are inversion lemmas) And if so, how it relates to the other derivations ?

Another related question is how reduction acts on such typing derivation. The proof of subject reduction shows that reduction can be lifted from terms to typing derivations but looking at the proof script it's hardly clear to me what's happening in the proof.

#### Gaëtan Gilbert (Aug 27 2020 at 09:06):

You can get a canonical one by running the decider
it will do something like interleaving structural and conversion steps, so there's never 2 conversions in a row

#### Paolo Giarrusso (Aug 27 2020 at 10:45):

Could you formulate an algorithmic version of pcuic, and relate it to the declarative version in the usual way?

#### Paolo Giarrusso (Aug 27 2020 at 10:45):

That would turn the decider into a syntax-directed type system

#### Kenji Maillard (Aug 27 2020 at 11:17):

Gaëtan Gilbert said:

You can get a canonical one by running the decider
it will do something like interleaving structural and conversion steps, so there's never 2 conversions in a row

That's indeed a first step towards an answer to my question, but how "canonical" is the resulting derivation ? For instance, is it (proven to be) idempotent ? Can we give a high level spec of the shape of the generated typing derivations (beside the alternation between structural and conversion rules, which is already a good starting point) ?

#### Kenji Maillard (Aug 27 2020 at 11:19):

Paolo Giarrusso said:

Could you formulate an algorithmic version of pcuic, and relate it to the declarative version in the usual way?

@Meven Bertrand was working on a bidirectional presentation of the typing, so he might be able able to answer our questions on that.

But even a syntax-directed system does not necessarily explain immediately how it relate to the non-syntax directed one.

#### Gaëtan Gilbert (Aug 27 2020 at 11:37):

Producing a derivation by the decider doesn't use the input derivation except in the aburd case where the decider says "no", so it must be idempotent

If you present your rules with conversion integrated, such that instead of

|- f : A -> B
|- x : A
========
|- f x : B

|- e : A
A <= B
=======
|- e : B

you have

|- f : A -> B
|- x : A
=========
|-0 f x : B

no constructor of |-0 for conversion

and |- e : T defined as exists T0, |-0 e : T0 /\ T0 <= T
then you have no choice about where to use conversion so it's propositional (assuming the conversion judgment is propositional)
and there is a canonical translation from the second presentation to the first which I think produces what the decider would

#### Paolo Giarrusso (Aug 27 2020 at 20:09):

hmm, how would you write the other typing rules? would you use |- or |-0 ?

#### Paolo Giarrusso (Aug 27 2020 at 20:11):

That example looks weird — looking at subtyping, I’d usually expect f : A1 -> B, x : A2, A1 == A2. Here -> might be hidden, but I’d still expect |- f : T1, T1 ==HNF=> A1 -> B, x : A2, A1 == A2.

#### Paolo Giarrusso (Aug 27 2020 at 20:13):

But even a syntax-directed system does not necessarily explain immediately how it relate to the non-syntax directed one.

By “relate it in the usual way” I imply also proving equivalence — TaPL shows how to do it for STLC+subtyping, I’m not sure I’ve seen anything fancier — at most they do F-Omega (?)

#### Gaëtan Gilbert (Aug 27 2020 at 20:24):

it's possible i got it wrong

#### Paolo Giarrusso (Aug 28 2020 at 06:20):

Mine is more a question than a statement :-)

#### Meven Lennon-Bertrand (Aug 28 2020 at 09:15):

Kenji Maillard said:

Meven Bertrand was working on a bidirectional presentation of the typing, so he might be able able to answer our questions on that.

My feeling right now is that there is a gap in the formalization, namely a declarative, but bidirectional variant of typing, to mediate between the decider and the undirected declarative typing. This one I would hope to have some kind of uniqueness of derivation, corresponding to the derivation given by the decider when it succeeds, and giving a canonical undirected variant.

This canonical variant would correspond to what @Gaëtan Gilbert hints at, namely the one that concentrates conversion steps to the typing rules for eliminators (this is the only place where they are really needed).

A tentative description of such a bidirectional system is done in section 4 there https://hal.archives-ouvertes.fr/hal-02896776/document if you want to look at it, but I hope to investigate it for itself soon.

Last updated: Aug 11 2022 at 01:03 UTC


text:
# Modifying apacite reference style

I am trying to simulate my graduate school's references style using apacite package with bibtex. They claim their guidelines are close to APA but it is indeed an hybrid that no-one really accomplishes fully. Even though there seems to be no differences in entries with a single author between mine:

there is a quite difference when the resources have two

or more authors .

Here are the two author

and multiple author

in the reference style of the school. (The word ve means 'and' in Turkish.) Is there anyway to accomplish this entry style by modifying apacite 's attributes about two and multiple authored papers?

• My Turkish is a little rusty: "ve" is "and"? – mafp Jul 14 '13 at 8:53
• Yes, exactly. Sorry I've forgotten to explain it. – oakenshield1 Jul 14 '13 at 9:40
• Is the issue the semicolon between multiple authors and the 've' instead of '&'? (Your school also puts a space between the volume and issue that isn't present in the APA version.) – Alan Munn Jul 14 '13 at 13:56
• @AlanMunn Yes as what you've said Alan. Also there is one additional issue; I found that instead of ampersand you can put any word you want, for example 'and' by \renewcommand{\BBAA}{and} but then the comma (,) before ampersand (&) remains. – oakenshield1 Jul 14 '13 at 14:11

Most of your school's specification can be obtained with the means of apacite, except the semicolon between multiple authors, which is hard-coded in apacite.bst.

The relevant changes are the redefinitions of \BBAA, \BCBT, and \BCBL, see the code. The space bewteen volume and issue is obtained by adding a ~ to \APACjournalVolNumPages when there is an issue number in the reference.

To get the semicolon, make a copy of apacite.bst, and change line 2320 in your copy from

FUNCTION {comma.between.names} { ", " }

to

FUNCTION {comma.between.names} { "; " }

Then we obtain

\documentclass{article}

\usepackage{url}
\usepackage{apacite}

\AtBeginDocument{%
\renewcommand{\BBAA}{ve}%% the 'and' between authors in a parenthetical citation and in the reference list
\renewcommand{\BCBT}{}%% comma between authors in the reference section when there are two authors
\renewcommand{\BCBL}{}%% comma before the last author when there are three or more authors in a citation and in the reference section
%% make a space between volume and issue:
\renewcommand{\APACjournalVolNumPages}[4]{%
\Bem{#1}%             journal
\ifx\@empty#2\@empty
\else
\unskip, \Bem{#2}%  volume
\fi
\ifx\@empty#3\@empty
\else
\unskip~({#3})%      issue number; added the '~'
\fi
\ifx\@empty#4\@empty
\else
\unskip, {#4}%      pages
\fi
}
}
\begin{document}
\cite{Ca04}% one author
\cite{StGu92}% two authors
\cite{GhJaEn02}% three authors

\bibliographystyle{oakenshieldapacite}%% based on apacite.bst
\bibliography{test}
\end{document}

• I was just about to post this answer too. Hopefully the school doesn't require a comma between multiple authors in citations as well as the semi-colon in the bibliography. – Alan Munn Jul 14 '13 at 17:23
• @AlanMunn Let's see whether the OP accepts it as is :-) – mafp Jul 14 '13 at 17:27
• @mafp It worked flawlessly. Thank you very much. I have two more question: 1) Is it a more structured way to write a turkish.apc file for these kind of problems? 2) How can i change the "et al." abbreviation in multiply authored papers' citations to its Turkish counterpart "vd." – oakenshield1 Jul 14 '13 at 19:54
• @oakenshield1 1) Yes, most definitely.You could even submit it to the authors of apacite. 2) The commands to change are \BOthers and \BOthersPeriod. Their default setting is et al.\hbox{}. – mafp Jul 15 '13 at 6:55


text:
# Trig Derivative

• Oct 11th 2009, 07:04 PM
VitaX
Trig Derivative
Find the derivative

$r = \left(\frac{1+Sin \Theta}{1-Cos \Theta}\right)^2$

I believe the chain rule and quotient rule are used here. So here's my first step, if someone can confirm I did this correct than I could probably go on from there.

$r' = 2 \left(\frac{1+Sin \Theta}{1-Cos \Theta}\right) \left(\frac{(1-Cos \Theta)(Cos \Theta) - (1 + Sin \Theta)(Sin \Theta)}{(1-Cos \Theta)^2}\right)$
• Oct 11th 2009, 07:26 PM
Arturo_026
looks good to me, from there on is pure trig.
• Oct 11th 2009, 07:34 PM
VitaX
$r' = 2 \left(\frac{1+Sin \Theta}{1-Cos \Theta}\right) \left(\frac{Cos \Theta - Cos^2 \Theta - Sin \Theta + Sin^2 \Theta}{(1-Cos \Theta)^2}\right)$


text:
# Is the definition of Gerstenhaber bracket related to operads?

I was reading these notes by Keller. On the page 19 he defines the Gerstenhaber bracket on the Hochschild cochain complex. But first of all he defines the operation $\bullet$ on the cochains by $$\small (f\bullet g)(a_1,\dots,a_{p+q-1})=\sum\limits_{i=0}^{p} (-1)^{i(q+1)} f(a_1,\dots,a_i,g(a_{i+1},\dots,a_{i+q}),a_{i+q+1},\dots,a_{p+q-1})$$ where $f$ is a $p$-cochain and $g$ is a $q$-cochain. After that he defines the Gerstenhaber bracket by $[f,g]_G=f\bullet g-(-1)^{(p-1)(q-1)}g\bullet f$.

I have noticed that the summands in the operation $\bullet$ look a lot like the partial composition in operads, as if $f$ was an element of arity $p$ and $g$ was an element of arity $q$ in some operad. So my question is, is it just a coincidence, or there is indeed some way to see $f,q$ as operations in some operad? Or maybe is there a way to see the operation $\bullet$ coming from some operadic context?

I am a complete novice in these things, so I am sorry if my question is silly. Anyways I would be happy if someone would explain that to me.

-
No this is absolutely true, there is a connection. The book in which I was reading about this is, unfortunately, in my office! I wonder if I can make some useful comment though... – Jon Beardsley Aug 15 '13 at 4:25
There's a rather interesting discussion of this in an article called "Operads and Nonassociative Deformations" by Eugen Paul. – Jon Beardsley Aug 15 '13 at 17:50

Yes, absolutely. I really think the best place for learning this is the book by Loday and Vallette.

This example fits more generally into the following context. Let $P$ be a Koszul operad and $A$ a $P$-algebra. There is attached to $P$ a cohomology theory for $P$-algebras. The two most well known examples is that when $P = \mathsf{Lie}$ we get ordinary Lie algebra cohomology, and that when $P = \mathsf{Ass}$ we get Hochschild homology. This is in general defined by the chain complex $$\mathrm{Hom}_{\mathbb S}(P^!,\mathrm{End}(A))$$ i.e. maps of $\mathbb S$-modules from the Koszul dual co-operad of $P$ to the endomorphism operad of $A$. This chain complex sits inside $$\mathrm{Hom}_{\mathbb k}(P^!,\mathrm{End}(A)),$$ i.e. maps which are not necessarily equivariant. The latter space is itself in a natural way the sum of all components of an operad, the convolution operad. Convolution gives an operad structure on maps from any co-operad to an operad.

Now on the sum of all components of an operad there is a pre-Lie structure given by operadic composition. This is the operation you called $\bullet$, and as you say, it is just given by composition. Antisymmetrizing this gives an honest Lie bracket. This bracket on $$\mathrm{Hom}_{\mathbb k}(P^!,\mathrm{End}(A)),$$ leaves $$\mathrm{Hom}_{\mathbb S}(P^!,\mathrm{End}(A))$$ invariant, giving a Lie bracket on the chain complex for the operadic cohomology. When $P = \mathsf{Ass}$ and $A$ is an associative algebra we have defined the Gerstenhaber bracket on the Hochschild complex. This is what you are seeing.

There are some degree shifts involved here (as one sees from your formulas) that I'm not going to try to work out.

-
Just wondering, what do you mean by equivariant" here with respect to $\mathbb{S}$? – Jon Beardsley Aug 15 '13 at 5:56
An $\mathbb S$-module $V$ is a collection $V(n)$ of representations of the symmetric groups $\mathbb S_n$. By an $\mathbb S$-module map $V \to W$ I mean a collection of $\mathbb S_n$-equivariant maps $V(n) \to W(n)$. – Dan Petersen Aug 15 '13 at 5:57
Aha, fantastic. Sorry, I was thinking you meant the sphere spectrum. – Jon Beardsley Aug 15 '13 at 6:09
@DanPetersen Great answer! Thank you very much! – Sasha Patotski Aug 15 '13 at 13:49


text:
# How do you solve x+3y=y+110 for y?

Sep 3, 2016

$y = \frac{110 - x}{2}$

#### Explanation:

Solve $x + 3 y = y + 110$ for $y$.

Subract $x$ from both sides of the equation.

$3 y = y + 110 - x$

Subtract $y$ from both sides.

$3 y - y = 110 + x$

Simplify $3 y - y$ to $2 y$.

$2 y = 110 + x$

Divide both sides by $2$.

$y = \frac{110 - x}{2}$


text:
# pygmt.surface¶

pygmt.surface(x=None, y=None, z=None, data=None, **kwargs)[source]

Grids table data using adjustable tension continuous curvature splines.

Surface reads randomly-spaced (x,y,z) triples and produces gridded values z(x,y) by solving:

(1 - T) * L (L (z)) + T * L (z) = 0

where T is a tension factor between 0 and 1, and L indicates the Laplacian operator.

Takes a matrix, xyz triples, or a file name as input.

Must provide either data or x, y, and z.

Full option list at https://docs.generic-mapping-tools.org/latest/surface.html

Aliases:

• G = outfile

• I = spacing

• R = region

Parameters
• x/y/z (1d arrays) – Arrays of x and y coordinates and values z of the data points.

• data (str or 2d array) – Either a data file name or a 2d numpy array with the tabular data.

• spacing (str) – 'xinc[unit][+e|n][/yinc[unit][+e|n]]'. x_inc [and optionally y_inc] is the grid spacing.

• region (str or list) – 'xmin/xmax/ymin/ymax[+r][+uunit]'. Specify the region of interest.

• outfile (str) – Optional. The file name for the output netcdf file with extension .nc to store the grid in.

Returns

ret (xarray.DataArray or None) – Return type depends on whether the outfile (G) parameter is set:

• xarray.DataArray if outfile (G) is not set

• None if outfile (G) is set (grid output will be stored in outfile)


text:
### An Island of Liars is an Ensemble of Experts

In my previous post I looked at how a group of experts may be combined into a single, more powerful, classifier which I call NaiveBoost after the related AdaBoost. I'll illustrate how it can be used with a few examples.

As before, we're faced with making a binary decision, which we can view as an unknown label $$L \in \{ +1, -1 \}$$. Furthermore, the prior distribution on $$L$$ is assumed to be uniform. Let our experts' independent probabilities be $$p_1 = 0.8, p_2 = 0.7, p_3 = 0.6$$ and $$p_4 = 0.5$$. Our combined NaiveBoost classifier is $C(S) = \sum_i \frac{L_i}{2}\log{\left( \frac{p_i}{1-p_i}\right)},$ where $$S = \{ L_i \}$$. A few things to note are that $$\log{\left( \frac{p_i}{1-p_i}\right)}$$ is $${\rm logit}( p_i )$$, and an expert with $$p = 0.5$$ contributes 0 to our classifier. This latter observation is what we'd expect, as $$p = 0.5$$ is random guessing. Also, experts with probabilities $$p_i$$ and $$p_j$$ such that $$p_i = 1 - p_j$$ are equivalent if we replace the stated label $$L_j$$ with $$-L_j$$.

Ignoring the last (uninformative) expert, we end up with the combined classifier $C(S) = \frac{L_1}{2} \log\left(4\right) + \frac{L_1}{2} \log\left(\frac{7}{3}\right) + \frac{L_3}{2} \log\left( \frac{3}{2} \right).$ If the overall value is positive, the classifier's label is $$L = +1$$; if it's negative, the classifier's label is $$L = -1$$. Note the base of the logarithm doesn't matter and we could also ignore the factor of $$\frac{1}{2}$$, as these don't change the sign of $$C(S)$$. However, the factor of $$\frac{1}{2}$$ must be left in if we want the ability to properly recover the actual combined probability via normalization.

Now say $$L_1 = -1, L_2 = +1, L_3 = +1$$. What's our decision? Doing the math, we get $$C(S) = \frac{1}{2} \log{ \left( \frac{7}{8} \right) }$$, and as $$7 < 8$$, $$C(S) < 0$$ and our combined classifier says $$L = -1$$. If we wanted to recover the probability, note $\exp\left( \frac{1}{2} \log \left( \frac{7}{8} \right) \right) = {\left( \frac{7}{8} \right)}^{1/2},$ hence our classifier states ${\rm Pr}(L = +1 | S ) = \frac{ {\left( \frac{7}{8} \right)}^{1/2} }{ {\left( \frac{7}{8} \right)}^{1/2} + {\left( \frac{7}{8} \right)}^{-1/2} } = \frac{ \frac{7}{8} }{ \frac{7}{8} + 1 } = \frac{7}{15},$ and of course $${\rm Pr}(L = -1 | S ) = \frac{8}{15}$$.

As a second example, consider the @CutTheKnotMath puzzle of two liars on an island. Here we have A and B, each of which lies with probability 2/3 and tells the truth with probability 1/3. A makes a statement and B confirms that it's true. What's the probability that A's statement is actually truthful? We can solve this in a complicated way by observing that this is equivalent to an ensemble of experts, where $$L \in \{ +1, -1 \}$$, the prior on $$L$$ is uniform and $$L_1 = L_2 = +1$$. The probability that $$L = +1$$ is precisely the probability that A is telling the truth.

Following the first example, $L_{+1} = \frac{L_1}{2}\log\left( \frac{1}{2} \right) + \frac{L_2}{2}\log\left( \frac{1}{2} \right) = \log\left( \frac{1}{2} \right).$ Continuing as before, we get ${\rm Pr}(L = +1 | S ) = \frac{ \frac{1}{2} }{ \frac{1}{2} + 2 } = \frac{1}{5}.$

1. In the event tree there are two cases where B says the response is true, one with probability of 1/9 (A says it's try and B also say's it is try, 1/3 * 1/3) and the other with probability of 4/9 (A lies and says it is false and B also lies and says it is true, 2/3 * 2/3). So the probability that A is really telling the truth given B said it is true is (1/9)/(1/9+4/9) or 1/5.

1. Yes, that's simpler. I used this approach to illustrate how a puzzle such as this is actually related to a more complicated idea such as ensembles in machine learning.

2. Understood. Just checking the math. I don't know anything about machine learning...

### A Bayes' Solution to Monty Hall

For any problem involving conditional probabilities one of your greatest allies is Bayes' Theorem. Bayes' Theorem says that for two events A and B, the probability of A given B is related to the probability of B given A in a specific way.

Standard notation:

probability of A given B is written $$\Pr(A \mid B)$$
probability of B is written $$\Pr(B)$$

Bayes' Theorem:

Using the notation above, Bayes' Theorem can be written: $\Pr(A \mid B) = \frac{\Pr(B \mid A)\times \Pr(A)}{\Pr(B)}$Let's apply Bayes' Theorem to the Monty Hall problem. If you recall, we're told that behind three doors there are two goats and one car, all randomly placed. We initially choose a door, and then Monty, who knows what's behind the doors, always shows us a goat behind one of the remaining doors. He can always do this as there are two goats; if we chose the car initially, Monty picks one of the two doors with a goat behind it at random.

Assume we pick Door 1 and then Monty sho…

### Mixed Models in R - Bigger, Faster, Stronger

When you start doing more advanced sports analytics you'll eventually starting working with what are known as hierarchical, nested or mixed effects models. These are models that contain both fixed and random effects. There are multiple ways of defining fixed vs random random effects, but one way I find particularly useful is that random effects are being "predicted" rather than "estimated", and this in turn involves some "shrinkage" towards the mean.

Here's some R code for NCAA ice hockey power rankings using a nested Poisson model (which can be found in my hockey GitHub repository):
model <- gs ~ year+field+d_div+o_div+game_length+(1|offense)+(1|defense)+(1|game_id) fit <- glmer(model, data=g, verbose=TRUE, family=poisson(link=log) ) The fixed effects are year, field (home/away/neutral), d_div (NCAA division of the defense), o_div (NCAA division of the offense) and game_length (number of overtime periods); off…

### Gambling to Optimize Expected Median Bankroll

Gambling to optimize your expected bankroll mean is extremely risky, as you wager your entire bankroll for any favorable gamble, making ruin almost inevitable. But what if, instead, we gambled not to maximize the expected bankroll mean, but the expected bankroll median?

Let the probability of winning a favorable bet be $$p$$, and the net odds be $$b$$. That is, if we wager $$1$$ unit and win, we get back $$b$$ units (in addition to our wager). Assume our betting strategy is to wager some fraction $$f$$ of our bankroll, hence $$0 \leq f \leq 1$$. By our assumption, our betting strategy is invariant with respect to the actual size of our bankroll, and so if we were to repeat this gamble $$n$$ times with the same $$p$$ and $$b$$, the strategy wouldn't change. It follows we may assume an initial bankroll of size $$1$$.

Let $$q = 1-p$$. Now, after $$n$$  such gambles our bankroll would have a binomial distribution with probability mass function \[ \Pr(k,n,p) = \binom{n}{k} p^k q^{n-k…


text:
Minimum Work needed?

1. Jan 5, 2009

Littlemin5

1. The problem statement, all variables and given/known data
what is the minimum wirk neede to push a 1000kg car 300m up a 17.5o incline?

Part a. Ignore friction

2. Relevant equations
So we are allowed to use the general equation

W=FdCos $$\theta$$

3. The attempt at a solution

So I thought you would just do:

W= (1000)(9.8)(300)(cos17.5)
W=2803927Joules

However according to my teacher we should be getting
W= 8.8 x105 Joules

Does anyone know what I am doing wrong?

2. Jan 5, 2009

Dick

Draw a picture. Are you sure cos is the right trig function to be using? The force is aligned with the direction of the car's motion so W=F*d. How does the angle of the slope affect F? Split the force into components.

3. Jan 5, 2009

Littlemin5

Oh, so you would have to use sin instead of cos. That makes more sense. I didnt know that you could interchange the trig function in the equation.

Thanks so much for your help!

4. Jan 5, 2009

Dick

You can't interchange the trig functions in the equation!! What happens when you are pushing the car up the incline is that the only force you have to overcome is the component of m*g that is tangent to the road. That's F_g=m*g*sin(incline angle). In the W=F*d*cos(theta) the theta is 0, since we are pushing in the same direction the car is moving. Those are two DIFFERENT angles. You aren't just substituting 'sin' for 'cos'. Try to be clear on this.

5. Jan 5, 2009

Littlemin5

But I do have one more question if I was told that in the next part there was an effective coefficent of friction of .25 , wuld I just multiple my answer for Part 1 by .25?

6. Jan 5, 2009

Dick

No. Not at all. Now you have to figure out the normal force before you can compute the frictional force. Can you do that?

7. Jan 5, 2009

Littlemin5

Wouldn't you do 9800Cos17.5=9346.26N

8. Jan 5, 2009

Dick

Right. So now get the frictional force. The total force you have to push up the hill then the tangential force (as in the first problem) PLUS the frictional force.

9. Jan 5, 2009

Littlemin5

so frictional force is 2336.565 and then I add that to 9800 which equals

12136.565.

From there I would do
(12136.565)(300)(sin17.5)

10. Jan 5, 2009

Dick

No again. F_total=F_tangential+F_friction. Ok, F_friction is 2336N. The gravitational force component you are opposing is m*g*sin(17.5). Now take F_total*d

11. Jan 5, 2009

Littlemin5

Wait I don't really understand the last comment you made. Could you please explain it in a bit more detail?

12. Jan 5, 2009

razored

Here is another perspective. The displacement occurs at 17.5 degrees from the horizontal. The force, that is gravitational force, is acting down. We ignore the normal work because it has no component of force in the displacement (cos90=0). So, since mg is acting down, and the displacement is at 17.5 above horiztonal, we use the FDcosO. We know the force, mg; we know the displacement, 300m, and we know the angle between them, 17.5 + 90. So.. it should be 1000kg * 300m * 9.8 * cos (17.5 + 90). I think this is right. This is assuming no friction. Also, the work is negative but magnitude is positive.

13. Jan 5, 2009

Dick

You could certainly do it that way. But it's pretty usual with inclined plane problems to split the m*g force into tangential and normal components. Going up the plane you only do work against the tangential component of m*g and the friction force. Add them and multiply by the distance.


text:
# Inductive definition of a set

I'm a beginner in set theory and I have doubt regarding mathematical induction. I came across the following examples.

Example 1:

Find the set given by the following definition:

1) $3 \in P$

2) For $x,y \in P, x + y \in P$

3) Only those elements obtained from steps (1) and (2) are in $P$

Solution: The set $P$ consists of positive integers which are multiples of 3.

Example 2:

Give an inductive definition of the set

$P = \{2,3,4,\ldots\} = N - \{0,1\}$

Solution:

1) $2 \in P$ and $3 \in P$

2) If $x,y \in P$, then $x+y \in P$.

3) Only those elements obtained from steps 1 and 2 are in $P$.

Could anyone explain the above two examples and how to write this kind of definitions? I googled it, but couldn't get what I need. Thanks in advance.

-
Which part do you not understand? – anthus Aug 23 '12 at 9:46
@DanielPietrobon How did they found that the set has multiples of 3 in example 1 and how to write the definitions in Example 2, Sir? – Gomathi Aug 23 '12 at 9:55
Well, what is 3+3? – anthus Aug 23 '12 at 10:00
@DanielPietrobon But, they didn't mention that y is also 3, Sir. – Gomathi Aug 23 '12 at 10:02
@DanielPietrobon So, initially as they have mentioned 3 belongs to P, we take both x and y as 3. Am I right, Sir? – Gomathi Aug 23 '12 at 10:06

Let us review the first solution, it's a bit simpler.

We begin with a set $P_0=\{3\}$. That is the base of the induction. Now suppose that $P_n$ was defined, we take $P_{n+1}$ to be $P_n$ with the addition of all elements of the form $x+y$ where $x,y\in P_n$.

Finally, $P$ is the union of the $P_n$'s, namely $\bigcup_{n=0}^\infty P_n$.

We can do the first few steps explicitly, to get the feel:

• $P_0=\{3\}$, that's the definition of the first step.
• $P_1=\{3,3+3\}$, we took $P_0$ and added $3+3$, which is the only possible combination of $x+y$ where $x,y\in P_0$.
• $P_2=\{3,6,9,12\}$, we took $P_1$ and now we add $3+6$ and $6+6$. We don't need to add $3+3$ because it's already in there.
• $P_3=\{3,6,9,12,15,18,24\}$, we added $3+12,6+12,9+12,12+12$. Note that this also included other pairs such as $6+9,9+9$, etc.

To prove that indeed $P$ is all the multiples of $3$ we need to argue that if $n=3m$ then there is some $k$ such that $n\in P_k$. We prove this by induction, of course, on $m$.

1. If $m=1$ then $n=3$ and therefore $n\in P_0$.
2. Suppose that for $3m$ we proved that $3m\in P_k$ for some $k$, and let $n=3(m+1)$. Since $3\in P_k$ we have that $3m+3\in P_{k+1}$, and therefore $n=3(m+1)=3m+3\in P_{k+1}$.

Now we need to prove that if a number is in $P$ then it is a multiple of $3$. Again we do this by induction, for example we can do this by induction on the index of $P_k$, namely:

• We know that $P_0=\{3\}$ and therefore all its elements are multiples of $3$.
• Suppose that for $P_k$ it is true that all its elements are multiples of $3$, we will show this is true for $P_{k+1}$.

Suppose that $n\in P_{k+1}$, then by the definition of $P_{k+1}$ there are $x,y\in P_k$ such that $n=x+y$. From the induction hypothesis for $P_k$ we have that $x,y$ are both multiples of $3$ and therefore their sum, $n$, is also a multiple of $3$.

Finally:

We have seen what exactly is the definition of $P$, and we have seen how to prove that it indeed has the wanted property. We prove these things carefully by induction, using the inductive definition of the stages constructing $P$.

-

We will prove the correctness of the two solutions first:

1. $P = 3\mathbb{N}$.

• Given $z \in P$, then either $z = 3$, in which case $z \in 3\mathbb{N}$ or $z = x+y$ for $x,y\in P$. After a finite number of steps and substitutions (at most $\frac{z}{3}$) we see that $z = \underbrace{3+\cdots+3}_n = 3n \in 3\mathbb{N}$.
• Conversely, let be given $3n\in 3\mathbb{N}$. For $n=1$, $3n=3\in P$. Suppose $3(n-1)\in P$ for some $n$, then $3n = 3+3(n-1)\in P$ by part 2 of the definition of $P$. By induction on $n\in\mathbb{N}$ we see $3\mathbb{N}\subset P$.
2. $P = \mathbb{N}\setminus\left\{0,1\right\}$

• Clearly, any finite sum of 2's and 3's is in $\mathbb{N}$, so $P\subset\mathbb{N}\setminus\left\{0,1\right\}$
• Conversely, given $z\in\mathbb{N}\setminus\left\{0,1\right\}$. Consider the largest $n\in\mathbb{N}$, such that $z_n:=z-2n>1$. If $z_n=2$, then $z$ is a finite sum of 2's, such that $z\in P$. If $z_n=3$, then $z=2n+3\in P$. This exhausts all possibilities, for if $z_n>3$, then $z_{n+1}>1$, which contradicts the maximality of $n$.

The examples you gave are not so much related to set theory as they're related to number theory. To come up with such examples yourself, you need to understand the basic principles of recursion and induction. See also, http://en.wikipedia.org/wiki/Mathematical_induction

A typical set theoretic example of induction is the following: A set $T$ is called transitive if $\forall x\in T: x\subset T$. A set is called an ordinal if it's transitive and well-ordered by $\in$. Let $S$ be the set of all finite ordinals. You can now prove that there is a bijection $\mathbb{N}\to S$. Hint: $0\mapsto \emptyset$, $1\mapsto\left\{\emptyset\right\}$, $2\mapsto\left\{\emptyset,\left\{\emptyset\right\}\right\}$, $\cdots$

-
I think that the point of these exercises is to help the student understand and be comfortable around inductive definitions, rather than focus on the number-theoretic properties of the example. $${}$$ The term "special" is often applied to other things in order-theory, what you described as special is known as "ordinal". – Asaf Karagila Aug 23 '12 at 10:24


text:
Following on from the last post I’ll quickly cover updating our input framework to allow for analogue controls such as Gamepad stick and triggers.

Code for the complete intermission 6 can be found here on Codeplex

### Available controls

With XNA we have a few analogue controls to choose from:

Two thumbstick controls – X/Y controls
Two Triggers – single direction feedback

These off a gradual response rather than the on/off switch from the digital controls.

Unfortunately Joysticks are not supported on the PC in XNA,yet…

Doesn’t take too much to update our code to use these analogue controls, first off we need to add a new function to our input class:

  1: private static Vector2 IsStickorTriggerMoved(Buttons button)

2: {

3:   switch (button)

4:   {

5:     case Buttons.LeftStick:

7:     case Buttons.RightStick:

9:     case Buttons.LeftTrigger:

11:     case Buttons.RightTrigger:

13:     default:

14:       return Vector2.Zero;

15:   }

16: }
Here we just check which control we are using and return the appropriate value, note that as the triggers only have a single value and the thumbsticks have 2, we convert the triggers in to a Vector2 to match the thumbsticks, this just makes it simpler and we only need one function and not two to handle the different types.
Then add the player control that will use this new function:
1: public static Vector2 TrooperMoveStick()

2: {

3:   return IsStickorTriggerMoved(m_InputMappings.AltMoveControl);

4: }
Now that we have our test function and control we need to update our game to use it.  This part is not as simple as we need to change the input handling for our trooper a fair bit to enable it to be able to use both analogue and digital controls, here’s what the updated update section looks like for the trooper in StarTrooperSprites:
1: Vector2 vel = Vector2.Zero;

2: switch (Input.InputMappings.AltMoveMethod)

3: {

4:   case MovementMethod.Analogue:

5:     vel = Input.TrooperMoveStick();

6:     break;

7:   default:

8:     if (Input.MoveUp())

9:       vel.Y = -2; // if trooper is under y=50 then go upward

10:     if (Input.MoveDown())

11:       vel.Y = 2; // if trooper is over y=450 then go upward

12:     if (Input.MoveLeft())

13:     {

14:       vel.X = -2; // go to the left

15:     }

16:     if (Input.MoveRight())

17:     {

18:       vel.X = 2; // go to the right

19:     }

20:     break;

21: }

22:

23: if (isWithinScreenBounds(Position + (vel * Speed))) Velocity = vel * Speed; else Velocity = Vector2.Zero;// set new velocity for Trooper

24:

25: if (Velocity.X > 0)

26:   SpriteEffect = SpriteEffects.None; // right flip trooper

27: else

28:   SpriteEffect = SpriteEffects.FlipHorizontally; // Left flip trooper

29:

30: // if space bar is triggered

31: if (Input.TrooperFired())

32:   TrooperFire();
There’s a lot in here so we will walk through the changes as I had applied them:
We had already updated the variable for capturing the change in movement to a Vector 2, so no change there (Vector2 vel).     Next I’ve added a test against a new configuration option to see if the player has chosen to use Analogue or Digital Controls in a switch statement (more on that in a bit).     If we are using analogue controls we update our movement vector (vel) by the amount returned from our new function.  now if the player only moves the stick a small amount the trooper will move slower.  The more the player moves the stick the faster the trooper will travel.     If we are not using analogue controls (assuming it’s digital) then we use the old functions.  Although they have been trimmed down a bit now to just move.     The next step adds a new function to check if the amount the trooper is going to move will put the player outside the bound of the drawable screen, if the trooper is going to move outside, we Zero it’s velocity so that it doesn’t move.  If the trooper still has room to move then we update it’s velocity (which in turn updates the sprite in the Sprite’s update call).     Finally we have added another test, since we need a way to check which way the trooper is travelling and we can no longer rely on which key the player is pressing (because with analogue we just have a movement amount not a specific move action like press left), we just check which way on the X axis the trooper is going to move, if the trooper is going to move left ( –X) then we flip the sprite to draw it the other way, if not we set it back to the original direction, right.
Here’s the code for the “IsWithinScreenBounds” function, which goes into the Sprite class in the engine folder:
1: public bool isWithinScreenBounds(Vector2 pos)

2: {

3:   if (pos.X > (float)StarTrooperGame.ScreenBuffer &&

4:     pos.X < (float)(StarTrooperGame.BackBufferWidth - (StarTrooperGame.ScreenBuffer * 2)) &&

5:     pos.Y > (float)StarTrooperGame.ScreenBuffer &&

6:     pos.Y < (float)(StarTrooperGame.BackBufferHeight - (StarTrooperGame.ScreenBuffer * 2)))

7:     return true;

8:   else

9:     return false;

10: }
This just checks the screen boundaries with a certain amount of buffer space, as you can see the ScreenBuffer is also a new attribute to the StarTrooperGame.cs Class, this goes in to the device specific settings, which allows a different screen buffer size to be set for mobile devices such as the ZUNE (note the ZUNE buffer is a lot smaller):
1: #if ZUNE

2:         private static int m_TargetFrameRate = 30;

3:         private const int m_BackBufferWidth = 240;

4:         private const int m_BackBufferHeight = 320;

5:         private const int m_ScreenBuffer = 10;

6: #else

7:         private static int m_TargetFrameRate = 60;

8:         private const int m_BackBufferWidth = 1280;

9:         private const int m_BackBufferHeight = 720;

10:         private const int m_ScreenBuffer = 50;

11: #endif
The smaller size would also be used in a Windows Phone 7 target, but more on that in a later post.
lastly to complete this update we need the new configuration setting for choosing which type of control we want to use and of course the setting to hold which control that is, so first add the new settings to the KeyMappings.cs class, first the enumeration for the type of control which goes after the InputMappings class
:
1: [Serializable]

2: public enum MovementMethod

3: {

4:   Digital,

5:   Analogue

6: }
Note that even the enum is marked as serializable for when we save the settings.   And now the keymappings themselves into the InputMappings class itself:
1: public MovementMethod AltMoveMethod; //switch to use analogue or digital control

2:

3: public Buttons AltMoveControl; //button or stick to use for control
So now that we have our settings, we just need to finish this off with the defaults and were done, so update the defaults in the Input.cs class:
1: m_InputMappings.AltMoveMethod = MovementMethod.Analogue;

2:

3: m_InputMappings.AltMoveControl = Buttons.LeftStick;
Now if we run the project our trooper now has a bit more freedom of movement on the left stick, but wait…
You should notice two things at this point:
The trooper moves down when I push up on the control stick     The background has disappeared
Actually the background disappeared a few builds ago and did take me a little time to figure out what went wrong (welcome to the happy world of unintended consequences), but more on that in a bit.
As for the trooper movement, there is a very simple explanation for this.  In our game world moving up actually means reducing the Y value of our sprite, as in our screen space Y increases down the screen.  However, the control stick increases the amount of Y movement as you push up, Up = more Y.   So in matter of fact pushing up increases the amount of Y movement and hence our trooper moves down the screen.
Simple answer to this, just flip the Y value when it moves, but as I am also a sucker for having things configurable (let the player decide on which is the right way, who knows some sucker may like it that way, no offence to those that do?), we’ll also add a configuration setting for this flipping.  So first add the new configuration and it’s default:

Flipping the controls
So to flip the Y axis for our control scheme we need the following updates.

1: public bool InvertYLeftStick;

2: public bool InvertYRightStick;

And add the defaults to the Input class:

1: m_InputMappings.InvertYLeftStick = true;

2: m_InputMappings.InvertYRightStick = false;

And finally update our movement code to recognise this configuration in the Input class, IsStickOrTriggerMoved function:

1: case Buttons.LeftStick:

3: case Buttons.RightStick:

Plus a little helper function to do the actual flipping for us, add the following “InvertY” function in the Input class:

1: private static Vector2 invertY(Vector2 move)

2: {

3:   move.Y = -move.Y;

4:   return move;

5: }

Here we simply invert the value on the Y axis of the value supplied and return it.  You could also add a InvertX option, but some might see that as silly (or really tricky if you wanted to add confusion in your control style, like a confusion bomb)

Conclusion
So there we have it, analogue controls.  Feel free to have a play and see what you can add to this, the project on codeplex also has some other configuration options added just so I could change the settings around while the game was running (very basic though).  See if you can update the Fire mode to shoot more fireballs the more the player leans on the triggers.
Next intermission is on something a little bit more snazzy, Particles, and also something a little less interesting but very important resource pools.  After that we have a much needed performance update and then update our WP7 project with what we have so far.
Technorati Tags: XNA

Almost done actually, we still need to update some of the code to get our background back.
Now this was a very strange bug and took a fair bit of time to fix, but I narrowed it down to the position on the screen the background was being drawn to, it was getting put well outside the visible screen, so it was being drawn still but not where we could see it.
First off was to move the origin property to the sprite class from the animation class, this fixes the centre point of the texture on the screen for drawing sprites, so add the attribute to the bottom of the Sprite class, like so:
1: Vector2 m_Origin = Vector2.Zero;
Then add the property to expose it, at the end of the properties section:
1: public Vector2 Origin

2: {

3:   set

4:   {

5:     m_Origin = value;

6:   }

7:   get

8:   {

9:     return m_Origin;

10:   }

11: }
Then to ensure the attribute is properly populated when the Sprite is constructed, update the constructors as follows:
1: public Sprite()

2: {

3:   m_Id = m_Counter++;

4: }

5:

6: public Sprite(Texture2D Texture)

7:   : base()

8: {

10:   m_Origin = new Vector2((float)Texture.Width / 2, (float)Texture.Height / 2);

11: }

12:

13: public Sprite(Texture2D Texture,int Frames, bool Loop)

14:   : base()

15: {

16:   Animation animation = new Animation(Texture,Frames);

17:   m_Origin = new Vector2((float)(Texture.Width / Frames) / 2, (float)Texture.Height / 2);

18:   animation.Loop = Loop;

19:   animation.Play();

20:

22: }
Adding the Origin references as appropriate.
Next we update the background creation logic to override the constructor and set the background Origin to Zero, makes it easier to draw background textures absolute:
1: Background bg = new Background(background);

2:

3: bg.Position = new Vector2(0, BackBufferHeight / 2);

4: bg.ScaleX = BackBufferWidth / background.Width;

5: bg.ScaleY = BackBufferHeight / background.Height;

6: bg.ZOrder = 10;

7: bg.Origin = Vector2.Zero;

8: bg.Velocity = new Vector2(0,1);
That should do it but I also made one other change here that will help us later, I’ve set the velocity of the main background so that the sprite update loop will move the background instead of just incrementing it by 1 all the time in the StarTrooperBackground class.  This enables us to change the speed of the background later.
But by setting this property we also need to update the StarTrooperBackground classes update method, else it will always move twice as fast, so update this code to:
1: public override void Update()

2: {

3:   Vector2 NewPosition = Position;

4:   if (NewPosition.Y == StarTrooperGame.BackBufferHeight)

5:   {

6:     NewPosition.Y = -StarTrooperGame.BackBufferHeight;

7:     Position = NewPosition;

8:   }

9: }
So all this update function does now is to shift the background up to the top once it has passed beyond view at the bottom of the screen.  However if the background was moving up this wouldn’t work.
Feel free to experiment with this if you want, to use a different velocity in a different direction.
To finish up you still need to remove all the references to m_Origin from the Animation.CS class m like the attribute at the end of the class, and the copy reference in the Clone constructor.
Basically search for all reference in the Animation class and remove them, the only exception is the Draw call which needs to be updated to:
1: spritebatch.Draw(m_SpritesheetTexture, sprite.Position, CurrentFrame, m_Colour, sprite.Rotation,

2:     sprite.Origin,sprite.Scale, sprite.SpriteEffect, 0);
Changing the Origin property to use the new Sprite Origin property.
Lastly, we need to tidy up the Position property in the Sprite class, so that it is no longer offset, like so:

1: public Vector2 Position

2: {

3:   set

4:   {

5:     m_Position = value;

6:

7:     //  UpdateCollisionRectangle();

8:   }

9:   get

10:   {

11:     return m_Position;

12:   }

13: }

Putting the property sett back to it’s default operation.
And were done.


text:
# Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$

I'm currently struggling to come up with a proof that the following language is irregular: $$L_2 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| \ne |w_2|\}$$ where $$\Sigma = \{a, b\}$$.

Now quite intuitively, the language needs to know what $$|w_1|$$ was in order to compare against $$|w_2|$$, so it has to be irregular, but I'm failing to formally prove that.

I was able to solve the previous problem from the book, which was proving that (similarly) $$L_1 := \{w_1aaw_2 \in \Sigma^* \mid w_1, w_2\in\Sigma^* \land |w_1| = |w_2|\}$$ is irregular, which was relatively simple using the pumping lemma.

So I thought maybe there was some kind of connection between the two problems, given that $$L_1\cup L_2$$ is regular, but there doesn't seem to be any kind of closure property I can robustly employ in order to prove that $$L_2$$ is irregular.

Any ideas are welcome and many thanks in advance!

• Your question suggests you are looking for applicable closure properties. One approach probably is to restrict to strings of the form $b^*aab^*$. Apr 4, 2021 at 1:08
• Hm, I didn't think such a restriction could prove fruitful. I don't get the implications of it yet, but I will have a thought. Apr 4, 2021 at 1:26

## 2 Answers

For $$i \ge 0$$ define $$w_i = b^i aa$$. For any $$i,j \ge 0$$ with $$i \neq j$$ you have that $$b^i$$ is a distinguishing extension for $$w_i$$ and $$w_j$$. Indeed, $$w_i b^i \not\in L_2$$ but $$w_jb^i \in L_2$$.

Then the number of equivalence classes of the set $$\{ w_i \mid i \ge 0\}$$ with respect to the equivalence relation "having a distinguishing extension" is not finite and, by the Myhill-Nerode theorem, $$L_2$$ is not regular.

Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.

Suppose that $$L_2$$ is regular. Then so is $$L' = \overline{L}_2 \cap \{b^i aa b^j\} = \{b^i aa b^i\}$$, which is easily shown to be non-regular using the pumping lemma.

Indeed, suppose that $$L'$$ was regular, and let $$p$$ be its pumping length. For some $$k \in \{1, \dots, p\}$$, the word $$b^p aa b^p \in L'$$ can be written as $$b^k b^{p-k} aa b^p$$ such that $$b^{ki} b^{p-k} aa b^p \in L'$$ for every $$i \ge 0$$. Nevertheless, for $$i=0$$ we have $$b^{p-k} aa b^p \not\in L'$$, yielding a contradiction.

• That's the first time I hear of that theorem, I will have a look at it. But since we haven't learned it yet, I guess the proof is achievable in a more, so to speak, simplistic manner. Thank you! Apr 4, 2021 at 1:21
• @D.Petrov. I added an alternative solution. Apr 4, 2021 at 1:31
• Thank you a hundredfold! That's exactly what I was looking for! Also reveals the implications of @HendrikJan's suggestion as well. Also, your proof for the irregularity of $L'$ is exactly the same as mine, which is another nice confirmation that I've got it right! Apr 4, 2021 at 1:35
• For your first line, did you mean to say that "Indeed, $w_ib^i\not\in L_2$ but $w_jb^i\in L_2$"? Apr 4, 2021 at 11:03
• @justhalf, yes. Thanks Apr 4, 2021 at 11:06

You can also use the pumping lemma directly. Let $$p$$ be the pumping length, and consider the word $$w = b^paab^{p+p!} \in L_2$$. According to the pumping lemma, there is a decomposition $$w = xyz$$ such that $$|xy| \leq p$$, $$y \neq \epsilon$$, and $$xy^tz \in L_2$$ for all $$t \geq 0$$. Thus $$y = b^q$$ for some $$q \in \{1,\ldots,p\}$$. If we take $$t = 1 + p!/q$$ then $$xy^tz = b^{p+p!}aab^{p+p!} \notin L_2$$.

• Now that's a clever idea, thank you! Apr 4, 2021 at 22:20


text:
# System of equations with finite set of values those unknowns take on

I'm wondering about systems of equations that take on a finite set of values for those variables. Is there a theory behind that? In particular, solving systems where the variable takes on values of either 0 or 1. The problem is probably NP-hard, but I'm wondering where to look to learn more about it.

Like for example,

$a^2 + bc - a = 0$

$b(a + d) - b = 0$

$c(a + d) - c = 0$

$d^2 + bc - d = 0$ where a, b, c, d are from {0, 1}.

-
can't you just try all alternatives? 2^4 isn't that big number. – tp1 Dec 8 '12 at 9:22
Sounds like you are interested in 0-1 programming. You might start with en.wikipedia.org/wiki/Linear_programming#Integer_unknowns – Gerry Myerson Dec 8 '12 at 11:49

Your system has a simple solution. Label the equations

[1] $a^2 + bc - a = 0$

[2] $b(a + d) - b = 0$

[3] $c(a + d) - c = 0$

[4] $d^2 + bc - d = 0$

Note that if $bc=1$ then equation [1] becomes $a^2+1-a=0$ which is false for $a=0,1$. Therefore one (or both) of $b,c$ is 0, and the term $bc$ drops out of equations [1] and [4], which become respectively $a(a-1)=0$ and $d(d-1)=0$ each of which is always true, so that the system reduces to only equations [2] and [3]. Either of these equations, given that one of $b,c$ is nonzero, implies that $a+d=1$, and furthermore $a+d=1$ implies that each of [2] and [3] hold, regardless of the values of $b,d$. Now if $b=c=0$ then $a,d$ can be any values, not just those satisfying $a+d=1$.

So the solution set can be expressed as:

$b=c=0$ and $a,d$ arbitrary, or

Exactly one of $b,c$ is $0$ and $a+d=1$.

-


text:
# How to calculate capacitor values in a Common Emitter amplifier?

Ok so I am designing a Common Emitter amplifier using a BJT and this has been driving me crazy for the past four days. Yes, this is for an assignment and I am not asking to have my homework done; my intent is to fully understand the circuit and how to design it. I mostly understand it but there are some caveats that are still confusing me.

The schematic is as follows:

simulate this circuit – Schematic created using CircuitLab

I've been using LTSpice to simulate this. Here's the LTSpice file for anybody who wants to download it and check it out.

I used a spreadsheet to run the calculations. Here's the link for that for anybody that wants to check it out.

So here's the process I went through designing this:

### Requirements

• $$\A_v = -100\$$
• $$\I_c \leq 5mA\$$
• $$\f_c \leq 100Hz\$$
• $$\V_{cc} = 10V\$$
• $$\Load = 10K\Omega\$$

### Design

• Finding $$\I_CR_C\$$

$$\A_v = -g_mR_C\$$ and $$\g_m = \frac{I_C}{V_T}\$$

So, $$\A_v = - \frac{I_C}{V_T}R_c\$$, where $$\V_T = 25mV\$$ at room temp.

So then, $$\I_CR_C = -A_vV_T = -(-100)\times 25mV = 2.5V\$$

• Finding Q-Point

Find maximum and minimum output voltage. The minimum output voltage is 0.2V, which is $$\V_{CE(sat)}\$$

The maximum output voltage is determined by $$\R_C\$$ and $$\R_L\$$ since the load is in parallel with $$\R_C\$$ in the AC model.

$$\V_{out,max}=V_{cc}\times\frac{R_L}{R_C+R_L} = 9.09V\$$

The Q-Point should be in the middle of the two boundaries (this is the Load-Line concept), so:

$$\ Q-Point = \frac{9.09-0.2}{2} = 4.45V \$$

Now here's the part where I am confused. The way my professor explains it is that we want a symmetric output above and below the Q-Point so we want an equal drop between the Q-Point and the Emitter Voltage, so we want to figure out what the voltage drop across the transistor should be. What he does is KVL from Vcc to ground through Rc, the transistor, and Rc, like this:

$$\ V_{R_E} = V_{cc} - I_CR_C - V_{CE}\$$ where $$\ V_{CE} \$$ is equal to the voltage drop across the collector branch, which is given by $$\I_CR_C\$$ to be 2.5V. Add the 0.2V for the saturation voltage to avoid that and you have $$\V_{CE} = 2.7V\$$. So in the KVL equation above:

$$\ V_{R_E} = 10 - 2.5 - 2.7 = 4.8V\$$ which makes no sense because if the Q-Point is at 4.45V, there won't be enough 'room' for the voltage output to fully swing below ground.

And then he went on to explain that because the Q-Point is 2.5V below Vcc so the min voltage, which is $$\V_{R_E}\$$ should be equally 2.5V below the Q-Point. I kind of understand it but the equations he's getting contradict the concept he's explaining. There isn't 2.5V drop on the collector branch. We started off with that but since the Q-Point is at 4.45 which the voltage at the collector, then there's a 5.5V drop. His value for the emitter voltage is way too high. It worked for the specific example he was using during lecture but it doesn't work for the one I'm doing.

The way I thought about it is that the emitter voltage should be 2.7V below the Q-Point (linking it to the middle of the Load-Line concept he explained) so the emitter voltage is at $$\ 4.45 - 2.7 = 1.75V = V_{R_E}\$$ and that's the value I used.

I then designed the voltage divider network (VDN) using the reflection rule for RB2 to be 10 times RE.

I simulated the circuit and I was able to get decent results with these values. My input voltage signal is $$\ 40mV_{pp}\$$ and the output is $$\4.3V_{pp}\$$ so I guess the gain is a bit higher than 100 but I guess it's negligible.

The issue is that $$\ I_C \ge 5mA\$$ and it's about 5.3mA so obviously that violates the requirement.

The other issue is the frequency response which brings me to the next point, calculating the capacitor values.

### Capacitors

So I understand that C1 must be chosen based on the low frequency cutoff. I have chosen the low frequency cutoff to be 20Hz (arbitrarily). Using the following formula:

$$\C_1 = \frac{1}{2\pi R_{in}f} \$$ where $$\R_{in}\$$ is the input impedance and it's the resistors of the VDN in parallel with $$\r_{\pi}\$$ and connected in series to the source impedance. I can't find/calculate the source output resistance and it's usually small enough so I neglected it. Then the input resistance becomes:

$$\ R_{in} = R_{B1} \parallel R_{B2} \parallel r_{\pi} = 413 \Omega\$$

and the capacitor value is then $$\19.27 \mu F\$$

I used the same formula to calculate the coupling capacitor at the output and I got a value in the range of nF and it caused the output to look like the graph of the tangent function haha so I gave it a standard $$\10\mu F\$$ value. Does the coupling capacitor at the output affect the low frequency cutoff?

I am unclear as to how to choose the bypass capacitor at the emitter. I understand that the capacitor must have a smaller impedance than the emitter resistance since in the AC model, the capacitor is seen as AC ground and it shorts out the emitter resistor. I read something more accurate in this website:

C3 must therefore remove as much of the AC from across RE as possible and so must have a low reactance at all audio frequencies. As the lowest frequency is going to be around 20Hz, C3 must have a reactance (XC) that is small compared to the value of RE at all frequencies above 20Hz

So I understand the reasoning behind the capacitor and how to choose its value. I've read that usually a large capacitor is used in this case. I don't understand why. How would I go about calculating the value? Is there a formula for this?

So, with the circuit I have so far, I get a semi-decent gain, a collector current that is a bit higher than the specification, and a frequency response that looks like this:

I am using the built-in general model for the transistor so that's why there's no frequency cutoff (or is there supposed to be one and I just did something wrong?). With the 2N2222 transistor it looks like this:

My transient response looks good, though. It's symmetrical wrt to ground even though the negative portion has a slightly bigger peak amplitude by 0.3V.

I have been reading so much in the past week regarding this amplifier. I have been watching so many youtube videos on this topic and I have been rewatching our lectures on this as well and I am starting to feel insane. There's so much contradictory information out there and it seems like our professor is stuck at using the old ways when he went to school and I can't seem to find formulas for calculating the values I need for those two capacitors.

I am open to all suggestions, recommendations, pointing me in the right directions, or anything that should be changed/fixed for that matter. At this point I understand how it works overall and I have a good grasp on the topic but there seems to be missing a few key things. Thanks in advance!

With 10mA thru the transistor (eyeball Ic), the transistor is in saturation.

I would do this.

Rbase_upper = 10K

Rbase_lower = 5.1K

Rcollector = 1Kohm

Remitter = 1K ohm

Expect about 7 volts on the collector

Expect about 3 volts on the base.

Expect about 2.3 volts on th emitter.

That gives 2.3mA Ie and Ic.

That gives 'reac' of 11 ohms.

If we could ignore the capacitors, you would have unloaded gain will be 1,000 ohms / 11 == 90 (- 90).

But you cannot ignore the capacitors. Make each capacitor 1,000 uF (in the 3 locations), and verify operation.

Now you have something that works, but needs a bit more gain, and to have a load.

Once you see the values I've given you are working, then iterate in the search space.

100Hertz needs 1.6 millisecond Tau for -3dB impact.

That across 1Kohm Re allows 1.6UF, except the gain is very poor because the 1K ohm Re is poorly bypassed. We need the 3dB corner, in that HIGH PASS FILTER, to be about 0.1 Hertz.

So increase Ce to have only 1 Ohm impact, requiring over 1,000 uF.

The input capacitor has to work with the LOW input resistance (beta * reac) or about 1,000 ohms.

The output capacitor has to work with the 10K ohm load.

All capacitors in your circuit will have an effect on the low-frequency cutoff your amplifier will have.

The $$\C_1\$$ and $$\C_2\$$ will form a classic high-pass filter.

And the corner frequency can be found using this equation :

$$F = \frac{1}{2\pi RC }\approx \frac{0.16}{RC}$$

Thus for the incut capcitor wil will have:

$$F_1 = \frac{1}{2\pi (R_{B1}||R_{B2}||r_{\pi})C_1}$$

I ignored the source impedance influence.

And for the output capacitor

$$F_2 = \frac{1}{2\pi(R_C + R_L)C_2}\approx \frac{0.16}{R_CC_2}$$

Now $$\C_E\$$ capacitor.

At DC the voltage gain is equal to $$\ \frac{R_C}{R_E}\$$. And the amplifer voltage gain will start to increses form $$\ \frac{R_C}{R_E}\$$ towards $$\(R_C||R_L)g_m\$$ at frequancy equal to: $$F_Z = \frac{1}{2\pi R_EC_E}$$

And the amplifier will reach this gain $$\(R_C||R_L)g_m\$$ value if the signal frequency is larger than: $$F_P\approx \frac{1}{2\pi \frac{1}{g_m}C_E}$$

Therefore, if we set for each individual filter cutoff frequency at 20Hz the overall lower cut-off frequency will be equal to:

$$F_C = \frac{F_L}{\sqrt{2^{\frac{1}{n}}-1}} = \frac{20Hz}{\sqrt{2^{\frac{1}{3}}-1}} \approx 39.2Hz$$

Thus, if you want the low cutoff frequency to be around $$\20Hz\$$ you need to select for example you need to set $$\F_1\$$ and $$\F_2\$$ at $$\\frac{20Hz}{2...10} = 2Hz\$$ and $$\C_E \approx \frac{0.16}{1/g_m*20Hz} \approx 1600\mu F\$$


text:
## Faculty Search in Nuclear Instrumentation at UC Berkeley’s Department of Nuclear Engineering

Posted by:

The Department of Nuclear Engineering at the University of California, Berkeley invites applications for a non-tenure or tenure faculty position targeting nuclear instrumentation. More information is available here.

## In Memoriam: Stanley Prussin, NSSC Berkeley PI

Posted by:

Professor Stanley Prussin died at home in Kensington, California on August 20, 2015 after a lengthy illness.

He received his B.S. (1960) from MIT, and his M.S. (1962) and Ph.D. (1964) from the University of Michigan, all in Chemistry.  After postdoctoral work at LBNL, he joined the Nuclear Engineering Department at Berkeley in 1966, where he served until his transition to Professor of the Graduate School in 2004.

Professor Prussin was internationally recognized in nuclear physics, chemistry, and instrumentation. He was the ...

Page 1 of 2 12


text:
## anonymous one year ago A group of adults and students went on a class trip to Washington, DC. The number of male students was 1 more than 7 times the number of adults. The number of female students was half the number of male students. If the total number of people who went on the trip is 82, find the numbers of male students and female students.

• This Question is Open
1. ganeshie8

I think you just need to setup two equations and solve

2. ganeshie8

@GG1997

3. ganeshie8

are you really sure the work adult was not a typo ?

4. anonymous

well how do you do that

5. anonymous

and I'm positive it's not a typo

6. ganeshie8

idk looks i have problem interpreting the question lol

7. ganeshie8

Lets start by labeling anyways let $$a$$ = number of adults $$m$$ = number of male students $$f$$ = number of female students

8. ganeshie8

The number of male students was 1 more than 7 times the number of adults. translates to $m = 7a+1\tag{1}$

9. ganeshie8

The number of female students was half the number of male students translates to $f=\frac{m}{2}\tag{2}$

10. ganeshie8

the total number of people who went on the trip is 82 translates to $a+m+f = 82\tag{3}$

11. ganeshie8

so we have a system with 3 equations, knw how to solve ?

12. anonymous

still struggling

13. anonymous

lol I really suck at math

14. ganeshie8

basically we have 3 equations and we need to solve 3 unknowns : $$a, m, f$$

15. anonymous

ok how

16. ganeshie8

$m = 7a+1\tag{1}$ $f=\frac{m}{2}\tag{2}$ $a+m+f = 82\tag{3}$ rearranging second equation gives, $$m=2f$$ plug this in the remaining equations

17. ganeshie8

$2f = 7a+1\tag{4}$ $a+2f+f=82\tag{5}$ can you solve this new two equation system with two unknowns ?

18. anonymous

do i didvide both sides by 2

19. ganeshie8

You could do that if you want to use substitution

20. ganeshie8

$2f=7a+1$ dividing 2 both sides gives $f=\dfrac{7a+1}{2}$ you want to plug this in the other equation and solve $$a$$ is it ?

21. ganeshie8

that works, do it

22. ganeshie8

still here ? @GG1997

23. anonymous

yes I'm here


text:
## Elementary and Intermediate Algebra: Concepts & Applications (6th Edition)

$\dfrac{5y^{3}}{x^{8}z^{2}}$
Using the laws of exponents, the given expression, $\dfrac{5x^{-8}}{y^{-3}z^{2}}$, is equivalent to \begin{array}{l}\require{cancel} \dfrac{5y^{3}}{x^{8}z^{2}} .\end{array}