概率论与数理统计 (Spring 2023)/Problem Set 4: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
Zhangxy (talk | contribs)
No edit summary
Zhangxy (talk | contribs)
No edit summary
Line 17: Line 17:
:'''Input:'''  real numbers <math>U < 1</math>;
:'''Input:'''  real numbers <math>U < 1</math>;
----
----
 
:
:initialize <math>x = 1</math> and <math>count = 0</math>;
:initialize <math>x = 1</math> and <math>count = 0</math>;
:while <math> x > U </math> do
:while <math> x > U </math> do

Revision as of 08:46, 22 May 2023

  • 目前作业非最终版本!
  • 每道题目的解答都要有完整的解题过程,中英文不限。
  • 我们推荐大家使用LaTeX, markdown等对作业进行排版。

Assumption throughout Problem Set 4

Without further notice, we are working on probability space [math]\displaystyle{ (\Omega,\mathcal{F},\mathbf{Pr}) }[/math].

Without further notice, we assume that the expectation of random variables are well-defined.

The term [math]\displaystyle{ \log }[/math] used in this context refers to the natural logarithm.

Problem 1

Algorithm
Input: real numbers [math]\displaystyle{ U \lt 1 }[/math];

initialize [math]\displaystyle{ x = 1 }[/math] and [math]\displaystyle{ count = 0 }[/math];
while [math]\displaystyle{ x \gt U }[/math] do
  • choose [math]\displaystyle{ y \in (0,1) }[/math] uniformly at random;
  • update [math]\displaystyle{ x = x * y }[/math] and [math]\displaystyle{ count = count + 1 }[/math];
return [math]\displaystyle{ count }[/math];