没有合适的资源?快使用搜索试试~ 我知道了~
首页probability and computing
probability and computing
5星 · 超过95%的资源 需积分: 36 17 下载量 35 浏览量
更新于2023-05-21
评论 1
收藏 2.58MB PDF 举报
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.
资源详情
资源评论
资源推荐
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
© Michael Mitzenmacher and Eli Upfal 2017
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.
Identiers: LCCN 2016041654 | ISBN 9781107154889
Subjects: LCSH: Algorithms. | Probabilities. | Stochastic analysis.
Classication: 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 Classier 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 Buttery 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 Satisability 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: Satisability 151
6.8
∗
Explicit Constructions Using the Local Lemma 152
6.8.1 Application: A Satisability 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: Denitions and Representations 168
7.1.1 Application: A Randomized Algorithm for 2-Satisability 171
7.1.2 Application: A Randomized Algorithm for 3-Satisability 174
7.2 Classication 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页未读,继续阅读
ceyuanhaijing
- 粉丝: 0
- 资源: 4
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论5