没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源讲义probability and computing

probability and computing

probability

computing

data

analysi

5星 · 超过95%的资源需积分: 36 17 下载量 201 浏览量 2018-11-30 03:51:45 上传评论 1 收藏 2.58MB PDF 举报

温馨提示

试读

482页

This book will provide you with sufficient and necessary background in probability theory and computing theory. Specifically speaking, this book will introduce you some randomization and probabilistic techniques for algorithm design and data analysis. It's required textbook in some course in Stanford University.

资源推荐

资源详情

资源评论

Fuel-Type Identification Using Joint Probability Density Arbiter and Soft-Computing Techniques

Fuel-Type Identification Using Joint Probability Density Arbiter and Soft-Computing Techniques

Information Theory, Inference, and Learning Algorithms

Science, Mathematics, and Computing. It expects familiarity with calculus, probability theory, and linear algebra as taught in a rst- or secondyear undergraduate course on mathematics for scientists

Random Number Generation and Monte Carlo Methods

5星 · 资源好评率100%

Although some familiarity with probability and statistics is assumed, the book is accessible to a broad audience. The second edition is approximately 50% longer than the first edition. It includes ..

probability-monad

概率分布单子使创建，处理和采样概率分布变得容易。安装将此包含在您的sbt配置中： "org.jliszka" %% "probability-monad" % "1.0.3" 例子这是解决以下问题的方法：给您一个公平的硬币或有偏差的硬币。如果您将其翻转5次并且每次都出现正面，那么您拥有公平硬币的概率是多少？ case class Trial ( haveFairCoin : Bo

probability by Gubner

it's the complete solutiona manual of Gubner's book "Probability and Random Process for ECE"

probability grimmett

Grad level book on probability

probability.jar

概率处理工具

probability.pdf

probability.pdf

Hands-On Data Science and Python Machine Learning

5星 · 资源好评率100%

I hold 17 issued patents in the fields of distributed computing, data mining, and machine learning. In 2012, I left to start my own successful company, Sundog Software, which focuses on virtual ...

Probability and Computing

Randomization and Probabilistic

Techniques in Algorithms and

Data Analysis

Second Edition

Michael Mitzenmacher Eli Upfal

www.cambridge.org

Information on this title: www.cambridge.org/9781107154889

10.1017/9781316651124

First published 2017

Printed in the United States of America by Sheridan Books, Inc.

A catalogue record for this publication is available from the British Library.

Library of Congress Cataloging in Publication Data

Names: Mitzenmacher, Michael, 1969– author. | Upfal, Eli, 1954– author.

Title: Probability and computing / Michael Mitzenmacher Eli Upfal.

Description: Second edition. | Cambridge, United Kingdom ;

New York, NY, USA : Cambridge University Press, [2017] |

Includes bibliographical references and index.

Identiers: LCCN 2016041654 | ISBN 9781107154889

Subjects: LCSH: Algorithms. | Probabilities. | Stochastic analysis.

Classication: LCC QA274.M574 2017 | DDC 518/.1 – dc23

LC record available at https://lccn.loc.gov/2016041654

ISBN 978-1-107-15488-9 Hardback

Additional resources for this publication at www.cambridge.org/Mitzenmacher.

Contents

Preface to the Second Edition page xv

Preface to the First Edition xvii

1 Events and Probability 1

1.1 Application: Verifying Polynomial Identities 1

1.2 Axioms of Probability 3

1.3 Application: Verifying Matrix Multiplication 8

1.4 Application: Naïve Bayesian Classier 12

1.5 Application: A Randomized Min-Cut Algorithm 15

1.6 Exercises 17

2 Discrete Random Variables and Expectation 23

2.1 Random Variables and Expectation 23

2.1.1 Linearity of Expectations 25

2.1.2 Jensen’s Inequality 26

2.2 The Bernoulli and Binomial Random Variables 27

2.3 Conditional Expectation 29

2.4 The Geometric Distribution 33

2.4.1 Example: Coupon Collector’s Problem 35

2.5 Application: The Expected Run-Time of Quicksort 37

2.6 Exercises 40

3 Moments and Deviations 47

3.1 Markov’s Inequality 47

3.2 Variance and Moments of a Random Variable 48

3.2.1 Example: Variance of a Binomial Random Variable 51

3.3 Chebyshev’s Inequality 51

3.3.1 Example: Coupon Collector’s Problem 53

3.4 Median and Mean 55

3.5 Application: A Randomized Algorithm for Computing the Median 57

3.5.1 The Algorithm 58

3.5.2 Analysis of the Algorithm 59

3.6 Exercises 62

4 Chernoff and Hoeffding Bounds 66

4.1 Moment Generating Functions 66

4.2 Deriving and Applying Chernoff Bounds 68

4.2.1 Chernoff Bounds for the Sum of Poisson Trials 68

4.2.2 Example: Coin Flips 72

4.2.3 Application: Estimating a Parameter 72

4.3 Better Bounds for Some Special Cases 73

4.4 Application: Set Balancing 76

4.5 The Hoeffding Bound 77

4.6

∗

Application: Packet Routing in Sparse Networks 79

4.6.1 Permutation Routing on the Hypercube 80

4.6.2 Permutation Routing on the Buttery 85

4.7 Exercises 90

5 Balls, Bins, and Random Graphs 97

5.1 Example: The Birthday Paradox 97

5.2 Balls into Bins 99

5.2.1 The Balls-and-Bins Model 99

5.2.2 Application: Bucket Sort 101

5.3 The Poisson Distribution 101

5.3.1 Limit of the Binomial Distribution 105

5.4 The Poisson Approximation 107

5.4.1

∗

Example: Coupon Collector’s Problem, Revisited 111

5.5 Application: Hashing 113

5.5.1 Chain Hashing 113

5.5.2 Hashing: Bit Strings 114

5.5.3 Bloom Filters 116

5.5.4 Breaking Symmetry 118

5.6 Random Graphs 119

5.6.1 Random Graph Models 119

5.6.2 Application: Hamiltonian Cycles in Random Graphs 121

5.7 Exercises 127

5.8 An Exploratory Assignment 133

6 The Probabilistic Method 135

6.1 The Basic Counting Argument 135

6.2 The Expectation Argument 137

6.2.1 Application: Finding a Large Cut 138

6.2.2 Application: Maximum Satisability 139

6.3 Derandomization Using Conditional Expectations 140

6.4 Sample and Modify 142

6.4.1 Application: Independent Sets 142

6.4.2 Application: Graphs with Large Girth 143

6.5 The Second Moment Method 143

6.5.1 Application: Threshold Behavior in Random Graphs 144

6.6 The Conditional Expectation Inequality 145

6.7 The Lovász Local Lemma 147

6.7.1 Application: Edge-Disjoint Paths 150

6.7.2 Application: Satisability 151

6.8

∗

Explicit Constructions Using the Local Lemma 152

6.8.1 Application: A Satisability Algorithm 152

6.9 Lovász Local Lemma: The General Case 155

6.10

∗

The Algorithmic Lovász Local Lemma 158

6.11 Exercises 162

7 Markov Chains and Random Walks 168

7.1 Markov Chains: Denitions and Representations 168

7.1.1 Application: A Randomized Algorithm for 2-Satisability 171

7.1.2 Application: A Randomized Algorithm for 3-Satisability 174

7.2 Classication of States 178

7.2.1 Example: The Gambler’s Ruin 181

7.3 Stationary Distributions 182

7.3.1 Example: A Simple Queue 188

7.4 Random Walks on Undirected Graphs 189

7.4.1 Application: An s–t Connectivity Algorithm 192

7.5 Parrondo’s Paradox 193

7.6 Exercises 198

8 Continuous Distributions and the Poisson Process 205

8.1 Continuous Random Variables 205

8.1.1 Probability Distributions in R 205

8.1.2 Joint Distributions and Conditional Probability 208

8.2 The Uniform Distribution 210

8.2.1 Additional Properties of the Uniform Distribution 211

8.3 The Exponential Distribution 213

8.3.1 Additional Properties of the Exponential Distribution 214

8.3.2

∗

Example: Balls and Bins with Feedback 216

8.4 The Poisson Process 218

8.4.1 Interarrival Distribution 221

剩余481页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

BJWcn

2023-07-27

这本《Probability and Computing》非常系统地介绍了概率理论与计算的关系，对于理解计算机科学中的随机算法非常有帮助。
呆呆美要暴富

2023-07-27

这本文件很好地讲解了概率和计算的交叉领域，对于那些对随机算法和数据分析感兴趣的人来说，是一本难得的参考书。
柔粟

2023-07-27

《Probability and Computing》是一本很实用的文件，它结合了概率理论和计算机科学的实际应用，提供了很多有价值的解决问题的方法。
玛卡库克

2023-07-27

我很喜欢《Probability and Computing》这本文件，它深入浅出地解释了概率与计算的关系，不仅让我对这个领域有了更深的理解，还让我在实际的编程中受益匪浅。
焦虑肇事者

2023-07-27

这本书以质朴的语言阐述了概率和计算的基本概念，对于初学者来说很友好，也能帮助他们建立起扎实的基础。