La minería de patrones secuenciales es una tarea fundamental de minería de datos con aplicaciones en varios dominios. Estudiamos dos variantes de esta tarea: la primera es la extracción de patrones secuenciales frecuentes, cuya frecuencia en un conjunto de transacciones secuenciales es mayor que un umbral proporcionado por el usuario; la segunda es la minería de patrones secuenciales frecuentes verdaderos, que aparecen con una probabilidad superior a un umbral definido por el usuario en transacciones extraídas del proceso generativo subyacente de los datos. Presentamos el primer algoritmo basado en muestreo para extraer, con alta confianza, una aproximación rigurosa de los patrones secuenciales frecuentes en conjuntos masivos de datos. También presentamos los primeros algoritmos para extraer aproximaciones de los patrones secuenciales frecuentes verdaderos con garantías rigurosas sobre la calidad de la salida. Nuestros algoritmos se basan en aplicaciones novedosas de la dimensión de Vapnik-Chervonenkis y la complejidad de Rademacher, herramientas avanzadas de la teoría del aprendizaje estadístico, para la minería de patrones secuenciales. Nuestra extensa evaluación experimental muestra que nuestros algoritmos proporcionan aproximaciones de alta calidad para ambos problemas que consideramos.