Среди рандомизированных алгоритмов вероятность

Question

Я прохожу курс рандомизированных алгоритмов на уровне выпускника осенью. Профессор известен тем, что он очень ориентирован на детали и математически строгий, поэтому я должен будет иметь глубокое понимание вероятности. Что было бы хорошей книгой вероятности, чтобы извлечь из этого, это было бы интуитивно понятным, но также иметь некоторую математическую строгость?

Answer 1

Какие учебники рекомендуют курс? Мне нравится «вероятность и вычисления» от Mitzenmacher и Upfal и «рандомизированные алгоритмы» от Motwani и Raghavan. Они вводят необходимую теорию с точки зрения алгоритмов. Я также рекомендую книгу о неравенстве, так как ограничивающие вещи вполне важны для анализа рандомизированных алгоритмов. По крайней мере этот шпаргалка.

Answer 2

Вам на самом деле не нужен математически строгий текст по теории вероятности. Я сомневаюсь, что профессор будет использовать $ sigma $-Algebras и тому подобное (если они не упомянут Мартингингес и предпочтут обсуждать их, используя эти термины; никто не сможет следовать). Вам, вероятно, нужно понимание теории вероятности, которую вы можете получить только по «игре» с ней, например, в таком курсе. Если у вас вообще нет фона, просто возьмите вступительный текст и проведите некоторые упражнения.