20
`
`Local DCOM value objects that are not primary DCOM value objects are not required
`to support this interface.
`
`20.6.2 ISynchr0nize and DISync/zronize
`
`These interfaces are implemented on local DCOM value objects (lsynchronize is
`found on COM proxies, DISynchronize is found on Automation proxies). lf the
`interface is available, it means that this is a local DCOM value object, not a regular
`object or a primary DCOM value object.
`
`20.6.2.1
`
`Mode Property
`
`The property Mode is used to control when synchronization is done. A value of
`kNeverSync means that the local and the primary value objects are never
`synchronized.
`
`A value of kSyncOnS end means that, if the local value object has been changed,
`the primary value object will be synchronized with the local value object when the
`local value object is sent to another client/server, which cannot be reliably determined
`to support the required DCOM value object. lmplementations can choose to
`synchronize using either batch synchronization through a call to IVa.1ueObject, or
`through calls for each changed member through the regular remote interface.
`
`A value of ksynconchange means that, as a member is changed, the update of the
`member should be propagated to the primary value object as a regular remote call.
`
`20.6.2.2
`
`SyncN0w Method
`
`The SyncNow method can be called by application code to force the changes to the
`local value object to be propagated to the primary value object. Implementations can
`choose to synchronize using either batch synchronization through a call to
`IValue0bj ect, or through calls for each changed member through the regular
`remote interface.
`
`20.6.2.3
`
`ReCopy Method
`
`The Recopy method can be called by application code to retrieve the current value of
`the_ primary value object and update the local value object.
`
`20.7 DCOM Value Objects
`
`20. 7.1 Passing Automation Compound Types as DCOM Value Objects
`
`Compound types such as structures and unions are encapsulated in Automation classes
`so they may be used by Automation applications. These are DCOM value objects.
`When a DCOM value object representing a compound type is passed to a remote
`
`December 2001
`
`CORBA, v2.6: DCOM Value Objects
`
`20-1]
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1026 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1026 of 1442
`
`

`
`20
`
`client, its interface pointer is marshaled using standard marshaling (as with any DCOM
`value object), and its value data is forwarded simultaneously using the extent described
`in Section 20.4, “Extent Definition,” on page 20-5.
`
`20. 7.2 Passing CORBA-Defined Pseudo-Objects as DCOM Value Objects
`
`To handle the DCOM views of CORBA pseudo objects as DCOM value objects, the
`memory representation of these data types must be defined. The following sections
`detail the value data that will be passed in the extent.
`
`20. 7.3 IForeign0bject
`
`Supporting IForeignObj ect’s as a DCOM value object is required to avoid
`proxy explosion. The marshaled data for value objects of type IForeignObj ect is
`described in Section 20.8.2, “COM Chain Avoidance," on page 20-17.
`
`20.7.4 DIFOreignC0mplexType
`
`The value data for DCOM value objects of type DIForeignComp1ex'1‘y'pe can
`be represented by the following structure (note that this also includes the state for
`DIObjectInfo):
`
`struct FOREIGN_COMPLEX
`{
`
`LPSTR
`LPSTR
`LPSTR
`
`}:
`
`'
`
`name;
`scopedName;
`repositoryld;
`
`// Name of type
`// scoped name (if available)
`// Repository ID of type
`
`20. 7.5 DIForeignException
`
`The value data for DCOM value objects of type DIForeignException can be
`represented by the following structure:
`
`S true 1: FORE I GN_EXCEPTION
`{
`
`FOREIGN__COMPLEX
`long
`
`base;
`maj orcode ,-
`
`};
`
`20. 7. 6 DISystemException
`
`The value data for DCOM value objects of type DISyatemException can be
`represented by the following structure:
`
`5 true t CORBA_SYS'I‘EM_EXCEP'1‘ION
`{
`
`FORE I GN_EXCEP'I'ION baa e ,-
`
`20-12
`
`Cnmmrm Object Request Broker/irchilecture (CORBA), v2. 6
`
`December 2001
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1027 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1027 of 1442
`
`

`
`20
`
`
`long
`long
`
`};
`
`minorcode;
`completionstatus;
`
`20. 7. 7 DICORBA UserException
`
`The value data for DICORBAUserException is identical to that of
`DIForeignException. Value objects deriving from
`DICORBAUserException are passed as DCOM value objects according to the
`previously defined format. The value data of exception members must be preceded by
`the value data of DIForeignException.
`
`20.7.8 DICORBAStruct
`
`The value data for DICORBAStruct is identical to that of
`
`DIForeignComp1ex'I'ype. Value objects deriving from DICORBAStruct are
`passed as DCOM value objects according to the previously defined format. The value
`data of struct members must be preceded by the value data of
`DIForeignComplex'I'ype.
`
`20.7.9 DICORBA Union
`
`The value data for DICORBAUnion is identical to that of
`
`DIForeignComplexType. Value objects deriving from DICORB1-\Union are
`passed as DCOM value objects according to the previously defined format. The value
`data of a union must be preceded by the value data of DI ForeignComp1exType. -
`The value data for the union itself is the discriminant followed by the selected member,
`if any.
`
`20.7.10 DICORBATypeC0de and ICORBATypeC0de
`
`The value data for type code DCOM value objects can be represented by the following
`struct:
`'
`A
`
`S t ruc t CORBA_'1'YPECODE
`{
`
`FOREIGN_COMPLEx
`'I‘CKind
`
`base ;
`kind; // rypecode kind
`
`"union Typespecific swit:ch(kind)
`{
`
`case tk_objref:
`LPSTR
`.LPS'rR
`
`id;
`name;
`
`case tk_st:ruct:
`case t:k_except:
`LPSTR
`
`id;
`
`December 2001
`
`CORBA, v2.6: DCOM Value Objects
`
`20-13
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1028 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1028 of 1442
`
`

`
`20
`
`LPSTR
`
`name;
`
`member_count;
`long
`*member_names;
`[size_is(member_count,)] LPSTR
`[size_is(member_count,)]
`IUnknown**member_types;
`
`case tk_union:
`LPSTR
`LPSTR
`
`id;
`name;
`
`member_count;
`long
`member_names[];
`LPSTR
`[size_is(member_count,)]
`IUnknown**member_types;
`[size_is(member_count)] VARIANT
`*member_labels;
`Iunknown
`*discriminator_type;
`long
`defau1t_index;
`
`case tk_enum:
`member_count;
`long
`*member_names;
`[size_is(member_count.)] LPSTR
`[size_is(member_count,)]
`IUnknown**member_typea;
`
`case tk_string:
`long
`
`length;
`
`case tk_array:
`case tk_sequence:
`long
`length;
`IUnknown
`*content_type;
`
`case tk_a1ias:
`LPSTR
`LPSTR
`
`id;
`name;
`
`long
`Iunknown
`
`length;
`*content_type;
`
`I
`
`}
`
`Note that members of type IUnknown will actually be ICORBATypeCode
`instances for COM and DICORBATypeCode instances for Automation.
`
`20. 7.11 DICORBAAny
`
`The valuc data for DCOM value objects of type DICORBAAny can be represented by
`the following structure:
`
`struct
`
`CORBA_ANY_AUTO
`
`{
`
`—a
`
`FOR
`VAR
`DIC
`
`EIGN_COMPLEXbase;
`IANT
`value;
`ORBATypeCode*typeCode;
`
`20-14
`
`Common Object Request BmkerArchiIecture (CORBA). v2.6
`
`December 2001
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex.1102,p.1029of1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1029 of 1442
`
`

`
`20
`
`20.7.12 ICORBAAny
`
`The value data for DCOM value objects of type ICORBAAny can be represented by a
`CORBAAnyDataUnion as defined in COM/CORBA Part A.
`
`20.7.13 User Exceptions In COM
`
`ln COM, all CORBA user exceptions used in an interface are represented by another
`interface, which contains one method per user exception. The value data for one of
`these exception interfaces is an encapsulated DCOM union where each member of the
`union is one of the exception definition structures. The discriminant values are the
`indices of the corresponding structure retrieval method from the user exception
`interface.
`
`module Bank
`
`{
`
`exception lnsufFunds {float balance; );
`exception lnva|idAmount { float amount; };
`
`interface Account
`
`l
`
`}:
`
`}:
`
`exception NotAuthorized 0;
`
`float Deposit(in float amount)
`raises(lnva|idAmount);
`
`float Withdraw(in float amount)
`raises(lnvalidAmount, NotAuthorized);
`
`Per the COM/CORBA Part A specification, the above lDL results in the following
`interface used for user exceptions:
`
`struct Bank_InsufI-‘unds { float balance; };
`struct Bank_Inva1idAmount
`{ float amount; };
`struct Bank_Account_NotAuthorized
`
`interface IBank_AccountUserExceptions :
`{
`
`Ivnknown
`
`HRESULT get_Ir1sufFunds( [out] Bank_Insufl-‘unds *);
`HRESULT get_Inva1idAmount( [out] Bank_Inva1idAmount *);
`HRESULT get_NotAuthorized( [out] Bank_Account_NotAuthorized *) ;
`
`};
`
`When this DCOM value object is passed, the value data is marshaled as the following
`data structure:
`
`December 2001
`
`CORBA. V2.6: DCOM Value Objects
`
`20-15
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1030 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1030 of 1442
`
`

`
`20
`
`union Bank_AccountUserExceptionsData switchmnsigned short)
`{
`
`mo;
`case 0: Bank_InsufFunds
`1111;
`case 1: Bank_Inva1idAmount
`case 2: Bank__Account_NotAuthorized m2;
`
`20.8 Chain Avoidance
`
`To avoid view chaining (and thus proxy explosion), we define a general mechanism to
`carry chain information along with object references. This mechanism is defined in
`both COM and in CORBA to allow for bidirectional chain avoidance. Views in either
`
`system carry this information along with their object references. For example, the
`information carried in the object reference to a CORBA view of an Automation object
`would describe the object referred to by the view; that is, information about the
`Automation object.
`
`20.8.1 CORBA Chain Avoidance
`
`ln CORBA, the chain avoidance information is carried as an lOP profile in an object
`reference that is part of a chain.
`
`module Cosflridging
`{
`
`typedef sequence<octet> OpaqueRe£;
`typedef sequence<octet> Opaquenata;
`typedef unsigned long
`ObjectSystemID,-
`
`interface Resolver
`
`{
`
`.};
`
`OpaqueRef Resolve(in ObjectSystemID objSysID,
`in unsigned long chainDataFormat,
`in octet
`chainnataversion,
`in Opaquenata
`chainnata);
`
`struct ResolvableRef
`
`{
`
`};
`
`resolver;
`Resolver
`ObjectSystemID objSysID;
`unsigned long chainDataFormat;
`octet
`chainnataversion;
`Opaquenata
`chainData;
`
`typedef sequence<ResolvableRe£> Resolvablechain;
`
`struct BridgingProfi1e
`{
`
`20-16
`
`Common Object Request Broker Architecture (CORBA), v2.6
`
`December 200]
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1031 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1031 of 1442
`
`

`
`20
`
`
`Resolvablechainchain;
`
`The content of the profile is defined as a single BridgingProfile structure. The
`1D for this profile will be allocated by the OMG. The profile structure contains a
`sequence of Re so lvab1eRef structures, potentially one for each object system in
`the chain.
`‘
`
`The Re so 1va.b1eRef structure contains a resolver CORBA object reference
`that can be called at runtime through its Resolve method to return an opaque
`(because it is not CORBA) object reference for the specified link in the chain. The link
`in the chain is identified by the object system lD, objsys ID.
`
`1 for CORBA, 2 for Automation, and 3 for
`Currently defined object system IDs are:
`COM. lDs in the range from 0 through 100000 are reserved for use by the OMG for -
`future standardization.
`
`The Re so lvab leRef structure also contains information that can be used by the
`resolver as context to find the appropriate information to return. While this chain
`data is opaque, it is also tagged with a format identifier so that bridges that understand
`the format can directly interpret the contents of chainData instead of making a
`remote call to Resolve. The only currently defined format tag is 0, which is
`currently defined as “private." That is, chainData tagged as private cannot be
`directly interpreted and must be passed to the resolver for interpretation. All other
`format tags are specific to each object system. Format tags in the range of l to 100000
`are reserved for allocation by the OMG.
`
`The result of calling the Resolve method on a COM or Automation
`Re solvableRef is an NDR marshaled DCOM object reference with at least one
`strong reference.
`
`20.8.2 COM Chain Avoidance
`
`A similar approach is adopted to resolve the same chain avoidance issues‘ in COM;
`however, since DCOM does not support profiles, the implementation is different. The
`information for chain avoidance (also used by IForeignObject and
`IForeignObj ec t2) is provided as DCOM value data associated with each passed
`view object. This information is represented by a Reso1vab1eRefChain.
`
`struct Opaquekef
`{
`
`unsigned long
`unsigned long
`BYTE [size_is(1en)l
`
`} ;
`
`struct Opaquebata
`{
`
`unsigned long
`unsigned long
`
`len;
`maxlen;
`‘data;
`
`len;
`maxlen;
`
`December 2001
`
`CORBA. v2.6: Chain Avoidance
`
`20-17
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex.1102,p.1032of1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1032 of 1442
`
`

`
`20
`
`BYTE [size_is(len)]
`
`‘data:
`
`};
`
`typedef unsigned long ObjectSystemID;
`
`struct Resolvab1eRef
`
`IResolver
`
`ObjectSystemID
`unsigned long
`BYTE
`Opaquenata
`
`};
`
`struct Resolvablenefchain
`
`resolver;
`
`objSysID:
`chainDataFormat;
`' chainnataversion;
`chainnata;
`
`unsigned long
`unsigned long
`Resolvab1eRef
`
`len;
`maxlen;
`[size_is(1en,)]**data;
`
`};
`
`[
`
`object,
`pointer_defau1t(unique),
`uuid(5473e440—20ac—11d1-8a22-006097cc044d)
`
`nterface Ikesolver :
`
`Iunknown
`
`] i
`
`{
`
`0paqueRef Reso1ve([in] ObjectSystemID objSysID,
`'
`[in] unsigned long
`chainDataFormat,
`[in] BYTE
`chainnataversion,
`[in] Opaquenata .
`chainData);
`
`} 7
`
`object,’
`pointer_de£ault(unique),
`uuid(60674760-20ac-lldl-Ba22—0O6097cc044d)
`
`1 i
`
`{
`
`nterface IForeign0bject2 : IForeignObject
`
`Resolvedkefchain ChainInfo();
`
`};
`
`The use semantics of the resolver is identical to the use semantics described in
`
`Section 20.8.1, “CORBA Chain Avoidance,” on page 20-16. One format tag with value
`1
`is defined for a Resolvablenef with objsys ID 1 (CORBA). lfthe format tag
`Sl,mechainDataVersionrmmtbeOandmechainDatacomnmsa(CDR
`marshalcd) byte defining the byte ordering for the rest of the chainDa.ta (the byte
`value is identical to that used to encode GIOP messages) followed by a CDR
`
`20-18
`
`Cnmmon Object Request Broker A rch ilecture (CORB/1). v2. 6
`
`December 2001
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex.1102,p.1033of1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1033 of 1442
`
`

`
`20
`
`
`20.9 Chain Bypass
`
`marshaled object reference. lf Resolve were called for this Reso1vab1eRe£,
`the same value as contained in the chainnata would be returned by Resolve
`(i.e., a CDR-marshaled object reference).
`
`ln addition to this mechanism, the interface IForeignObject2 is defined on
`COM or Automation views to return the Reso1va.b1eRefChain in cases where
`this information has been lost.
`
`Using the chain avoidance technique defined in this specification, the formation of
`view chains can be avoided. However, there are cases where the chain avoidance
`information carried with the object references may have been discarded (for instance,
`as the object reference is passed through a firewall). In this case, chaining of views
`cannot be avoided without an explicit performance hit, which was deemed
`unacceptable. However, at the point when the first invocation is performed, information
`about the current chain can be returned as out-of-band data. This information can then
`
`be used on subsequent invocations to bypass as many views as possible in order to
`avoid the performance hit of multiple view translations.
`
`CORBA Client
`
`C8i§f,3,A
`
`CORBA Server
`
`CORBA Client
`
`
`
`CORBA Server
`
`
`
`Figure 20-3 lnvocation With and Without Chain Bypass
`
`Figure 20-3 shows an example of a call that does not perform chain bypass followed
`by one "that does. Note that chain bypass cannot eliminate all unnecessary calls since
`the client already has a reference to the view (not to the original object) and thus
`invokes an operation on the view. It is the responsibility of the view to perform the
`chain bypass if it so chooses -- in this case the view essentially becomes a rebindable
`stub.
`
`20.9.1 CORBA Chain Bypass
`
`For views to discover the chain information, two service contexts are defined as
`follows:
`
`ChainBypassCheck = 2
`Chairmypasslnfo = 3
`
`module Cosaridging
`{
`
`struct Reso1vedRef
`
`December 2001
`
`CORBA, v2. 6: Chain Bypass
`
`20-19
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1034 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1034 of 1442
`
`

`
`20
`
`Resolver
`
`resolver;
`
`ObjectSystemID objSysID;
`unsigned long chainDa.ta1'-‘ormat;
`octet
`chainnataversion;
`Opaquenata
`chainData.;
`opaqueRef
`reference;
`
`typedef sequence<Reso1vedRe£> Resolvednefchain;
`
`struct ChainBypassCheck // Outgoing service context
`{
`
`Obj ect
`
`objectToCheck;
`
`}:
`
`struct ChainBypassInfo // Reply service context
`{
`
`Reso1vedRefChain
`
`chain;
`
`}:
`
`} ;
`
`The ChainBypassCheck service context is sent out with the first outgoing (non-
`oneway) request. Since the service context is propagated automatically to subsequent
`calls, an object is provided in the service context to avoid returning chain information
`for an incorrect object. For a reply service context to be generated, the object in the
`service context must match the object (a view) being invoked.
`
`If a reply service context, ChainBypassInfo, is received with the reply message,
`then a view has been detected. The information in the Reso1vedRefC'ha.in can be
`
`used to bypass intermediate views. Each Reso1vedRef is identical to a
`Re so lvab1eRef except that it also contains the result of the resolution -- the
`reference member contains the data that would be returned if Resolve were
`
`called on the included resolver. if the reference field of Reso1vedRef is an empty
`sequence, then the marshaled object reference is assumed to be identical to the
`chainnata.
`'
`
`20.9.2 COM Chain Bypass
`
`The technique used for COM chain bypass is very similar to the technique used in
`CORBA. The only difference is the result of the fact that DCOM extents are not
`propagated into subsequent calls unlike CORBA service contexts.
`
`struct Resolvednef
`
`{
`
`IReso1ver
`Obj ectSystemID
`unsigned long
`BYTE
`Opaquenata
`
`resolver;
`objSysID;
`chainnatal-‘orrnat;
`chainnataversion;
`chainbata;
`
`20-20
`
`Common Object Request Broker/irchitecture (CORBA). v2.6
`
`December 200]
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1035 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1035 of 1442
`
`

`
`20
`
`OpaqueRef
`
`};
`
`reference;
`
`struct Reso1vab1eRe£Chain
`
`{
`
`};
`
`unsigned long
`unsigned long
`Reso1vab1eRef
`
`len;
`maxlen;
`[size_is(1en,)]**data;
`
`struct Chainnypasscheck
`
`// Outgoing extent body
`
`{ }
`
`;
`
`struct ChainBypassInfo
`{
`
`Reso1vab1eRefChain
`
`};
`
`// Reply extent body
`
`chain;
`
`The Chainliypasscheck extent is sent out with the first outgoing request. If a
`reply extent, ChainBypassInfo, is received with the reply message, then a view
`has been detected. The information in the Reso1vedRe fchain can be used to
`
`bypass intermediate views. Each Reso1vedRef is identical to a
`Resolvab1eRef except that it also contains the result of the resolution -- the
`reference member contains the data that would be returned if Resolve were
`
`called on the included resolver. lf the reference field of ResolVedRef is an empty
`sequence, then the marshaled object reference is assumed to be identical to the
`chainnata.
`
`The UUID for the request and reply extents are both:
`
`leba96aO -2 0bl- lldl-8a22 - 006097cc044d
`
`20.1 0 Thread Iderttz’/‘ication
`
`To correlate incoming requests with previous outgoing requests, DCOM requires a
`causality ID. The identifier is essentially a logical thread lD used to determine whether
`an incoming request is from an existing logical thread or is a different logical thread of
`execution. CORBA, on the other hand, does not strictly require a logical thread lD. To
`maintain the logical thread lD as requests pass through both DCOM and CORBA, we
`define a general purpose service context, which can be used to maintain logical thread
`identifiers for any system a thread of execution passes through.
`
`module CosBridging
`{
`
`struct OneThreadID
`
`{
`
`Obj ectsys texnID obj Sya ID ;
`Opaquebata
`th.rea.dID ;
`
`December 2001
`
`CORE/1. v2. 6: Thread Identification
`
`20-21
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1036 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1036 of 1442
`
`

`
`20
`
`};
`
`typedef sequence<OneThreadID> 'I‘hreadIDs;
`
`struct Logica1'I‘hreadID // Service context
`{
`
`ThreadIDs
`
`IDs;
`
`};
`
`} ;
`
`The logical thread ID information is propagated through a CORBA call chain using a
`service context (lDs to be assigned by the OMG) containing the
`Logica1ThreadID structure.
`
`For future use, a DCOM extent is defined to allow the same logical thread
`identification information to be passed through a DCOM call chain. If the OMG
`chooses to standardize a logical thread ID format for CORBA, this can be passed
`through a DCOM call chain using this extent.
`
`5 truct One'.l'.‘hreadID
`
`{ ObjectSystemID objSysID;
`
`Opaquenata
`
`threadID;
`
`};
`
`struct ThreadIDs
`
`{
`
`};
`
`len;
`unsigned long
`maxlen;
`unsigned long
`oneThreadID [size_is(1en)] ‘data;
`
`struct Logica1ThreadID // DCOM extent
`{
`
`ThreadIDs
`
`IDs;
`
`};
`
`This extent, used for passing logical thread IDs, is identified by the following UUID:
`
`f81f4e20—2234-lldl-8a22-006097cc044d
`
`20-22
`
`Common Object Request Broker Architecture (CORBA). v2.6
`
`December 200]
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex.1102,p.1037of1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1037 of 1442
`
`

`
`The Random Walk For Dummies
`
`RICHARD A. MONTE
`
`Abstract. We look at the principles governing the onedimensional discrete random walk.
`First we review five basic concepts of probability theory. Then we consider the Bernoulli
`process and the Catalan numbers in greater depth. Finally we detennine the probability
`that, if a. drunk is found again at the bar, then this is his first return visit.
`
`1. Introduction. The random walk has been a topic of interest in many disciplines,
`but it has been of particular interest in probability theory.
`Indeed, every student of
`probability theory has heard of the random walk, especially in the form of a drunk
`leaving a bar and wandering aimlessly up and down the street.
`Among other issues, the following four have been investigagqi in one, two, and three
`dimensions:
`
`0 The expected position 2: of the drunk after n steps.
`0 The maximum position m that the drunk has reached after 11 steps.
`0 The expected time of the drunk’s last visit to 0.
`0 The probability that the drunk hasn’t stumbled upon his own path after n steps.
`
`These issues are discussed, for example, in Rota’s book on probability
`The one-dimensional discrete case is most widely known because it is simple, yet
`illustrates many interesting and important features. In this paper, we treat this case of
`the first issue above. Thus we answer a basic question: What is the probability that
`the drunk is at a certain distance 2:, from the bar, after 17. steps‘?
`In Section 2, we review five basic topics: the sample space, the binomial coeflicient,
`random variables, the Bernoulli process, and Catalan numbers.
`In Section 3, we find
`the probability distribution for the position of the drunk after 11 steps. In Section 4, we
`proceed to calculate the probability that the drunk arrives at the bar for the first time
`after n steps. Finally, in Section 5, we determine the conditional probability that the
`drunl<"s first return occurs on the nth step given that he is indeed at the bar then; the
`formula is surprisingly simple.
`
`In this section, we review five concepts of probability theory, which
`2. The Basics.
`we will use to study the random walk of the drunk.
`First, a sample space 9 is defined to be the set of all possible outcomes of an
`experiment. Consider the coin toss as an example. A single toss has two possible
`outcomes: heads H, or tails T; thus 9 = (H, T}. If we toss the coin twice, then there
`are 22 different. possibilities; now 9 = {TT, TH, HT, HH}.
`Second, the binomial coefficient
`is defined to be the number of k-combinations
`of an n.-element set. ln other words, it is the number of different ways to pick .1: elements
`out of 17.. The binomial coefficient is given by the formula,
`
`143 _
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1038 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1038 of 1442
`
`

`
`..‘|
`
`144
`
`MIT UNDERGRADUATE JOURNAL or NIATHEMATICS
`
`This formula is proved in [1, p. 61].
`to each element
`Third, a random variable is defined to be a function X that
`in the sample space of an experiment, one and only one real number X The
`c,
`sample space Q of X is the set of real numbers :2: such that :17 = X for some r: in the
`sample space of the experiment. This definition is found in [2, p. 28].
`Fourth, a Bernoulli process is defined to be a sequence of random variables X1,
`X2, X3, .
`. .. Each X, records the outcome of an experiment modeled by the toss of a
`coin. Let 1) equal the probability of getting a head, and q the probability of getting a
`tail. Since these are the only possible outcomes, 11 + q = 1. Let X, be 1 if the nth trial
`yields a head, and be -1 if a tail. Thus, the sample space 9 of a Bernoulli process is
`the set of all possible sequences of 1 and -1.
`Fifth and finally, the nth Catalan number an counts certain arrangements of 2n
`parentheses. A well-formed arrangement is a list of 2n parentheses where each open
`parenthesis can be paired with a corresponding closed parenthesis to its right. The nth
`Catalan number is the number of such well-formed arrangements. For example, when
`n = 3, the possible well-formed arrangements are
`
`000, 0(0), (0)0. (00), ((()))-
`
`According to [1, p. 253], the nth Catalan number an is given by the formula,
`
`2n
`1
`_
`c"_n+1 n‘
`
`Thus, for example, the first six Catalan numbers are 1, 1,2, 5, 14, and 42.
`
`3. How It All Ties In. Suppose a drunk leaves a bar and walks aimlessly up and
`down the street, totally disoriented. We model the street as a line with the bar at the
`origin, and assume that the drunk takes unit steps, so we may record his position with
`an integer. Thus, for example, if he takes 5 steps to the left, he will be at position -5.
`VVe now calculate the probability that the drunk is at position :1: after n steps.
`Assume that the drunk’s walk can be modeled by a Bernoulli process. Say that the ith
`step is represented by the random variable X,~. A value of ‘-1’ indicates a step to the
`left; a value of ‘1’, a step to the right, so that
`
`G,,=X1+X2+...+X,,
`
`gives the position of the drunk after 11. steps. We want to know the distribution of the
`random variable G”.
`Denote the value of G" by 2:. Denote the number of steps taken to the right by r,
`the number to the left by I. Then
`
`It follows that
`
`m=r—landn=r+l.
`
`1": %(:I:+n)andl=%(n—a:).
`
`ways that l given steps can occur among 11 total steps. This is also
`Now, there are
`the number of ways of arriving at the point 1., and each way has probability p’q’. Note
`that n and 2: must have the same parity because 17. — 2: = 2l. We can therefore conclude
`that the probability distribution at point :1: is given by the formula,
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1039 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1039 of 1442
`
`

`
`THE RANDOM WALK Fon DUMMIES
`
`145
`
`__
`
`_
`
`P(G" _» 3) — { 0:
`
`(”)p’q',
`
`if z = n mod 2;
`
`otherwise.
`
`this is the case of the symmetric random
`Consider for example the case p = q =
`walk. The probability P(G,, = z) of being at position 2: after it steps is given in Table
`3-1. This table is simply a pascal triangle interspersed with Os.
`
`Table 3-1
`
`The Symmetric Random Walk
`
`
`
`The probability distribution in this particular case is given by
`
`<;>"=<:>/2»
`
`Since every path is equally likely in the symmetric random walk, the probability can be
`interpreted purely combinatorially. The probability is the number of different ways of
`arriving at .7.‘ divided by the size of the sample space. The sample space is the set of all
`the possible paths of length 11. Since the drunk has two choices at each point, and he
`takes a total of n steps, the total number of possibilities is 2".
`
`4. Taking a Step Further. From now on, we assume that the random walk is sym-
`metric; that is, p = What is the probability that the drunk’s first return is at the
`211th step‘! Here is where Catalan numbers enter. Observe that there is a one-to-one
`correspondence between paths and arrangements of parentheses. First,
`let an open
`parenthesis represent a step to the left, and a closed parenthesis a step to the right. For
`now, we consider only the case where the drunk’s first step is towards the left, since the
`case to the right is clearly symmetric to it.
`it is the number of
`From Section 2, recall the definition of the Catalan number r:,,:
`217. well-formed arrangements of parentheses. Note that, for well-formed arrangements,
`the number of" open parentheses is always at least that of closed parentheses, regardless
`of" what first Ir. parenthesis we pick. Because of the correspondence between paths and
`arrangements, the Catalan numbers count the number of paths that the drunk can take,
`which start and end at the bar, without ever crossing to the right side of the bar.
`We now adapt our correspondence to the problem of the drunk’s first return. The
`drunk takes his first step to the left. On the next 2n-2 steps, we insist that the drunk’s
`path corresponds to a well-formed arrangement so that at step 2n — 1 he is at position
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1040 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1040 of 1442
`
`

`
`.4!
`
`146
`
`MIT UNDERGRADUATE JOURNAL 01-‘ IVIATHEMATICS
`
`-1 without ever crossing to the right of -1. Then the final step brings the drunk back
`into the bar. This counts the total number of different paths that the drunk can take
`given the condition that the first return be at the 2nth step.
`Summarizing, we have the following sequence of steps:
`
`'
`
`0 Step 1. The drunk takes one step to the left.
`o The next 2n-2 steps. The drunk follows a path, which corresponds to a 211,- 2
`well—formed arrangement, that restricts the drunk to be either at point -1 or to
`the left of it, and that forces him to be at -1 after the (Zn — 1)st step.
`0 Step 2n. The dr11nk’s first return visit occurs when he takes one step to the
`right and into the bar.
`
`Hence, the number of paths the drunk can take is simply the Catalan number r;,,_1,
`since the well-ordered restriction applies only to the middle 2n -— 2 steps.
`We know that the nth Catalan number is equal to
`
`1
`
`2n
`
`n+1 n '
`
`So the (n - 1)st Catalan number is simply
`
`1 2n — 2
`n
`n — 1
`
`'
`
`Allowing the drunk to take his first step to the right will double the total number of
`paths that the drunk can take. So the total is
`
`'1
`n
`
`2 —
`n — 1
`
`2- ( " 2).
`
`To compute the probability of first return, we need only divide this quantity by the
`size of the total sample space. The latter was seen at the end of Section 3 to be 22"
`since there are 2n steps. Therefore, the probability that the drunk reaches the bar for
`the first time after 271 steps is
`
`21 <27), — 2) / 22,,’
`
`n — 1
`
`11.
`
`So, for example, consider the probability that the first return is at Step 21:. = 6; this
`probablity is given by
`
`4
`
`1
`2-
`
`3(2)/
`
`1
`2“ = —.
`
`16
`
`5. Conditional Probability and the First Return. We now consider a variant of
`the problem studied in the previous section: Given that the drunk is at the bar at Step
`211., what is the probability that this is his first return visit‘? This problem is like the
`previous One. The only difference is that the sample space has been reduced. Instead of
`considering all of the possible paths, we now consider the total number of paths given
`that, in the end, the drunk will be at the bar, which he may or may not have passed by
`earlier.
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1041 of 1442
`
`IPR2016-00726 -ACTIVISION, EA, TAKE-TWO, 2K, ROCKSTAR,
`Ex. 1102, p. 1041 of 1442
`
`

`
`THE RANDOM WALK FOR DUMMIES
`
`147
`
`To find the probability that the drunk will be at the bar after 217. steps, we use the
`conclusions from Section 3 to obtain
`
`P(G2” :
`
`.
`
`2
`71
`
`: < n>p%(2n7q%(211)_
`
`Since 17 = q = %, this expression becomes
`
`<2:>/22»
`
`The numerator in this expression represents the number of paths the drimk can take
`provided he is at the bar at the 2nth step. This is sa.mple space we need for the
`conditional probability.
`From Section 4, recall that, if the drunk’s first return visit is on the 2nth step, then
`the number of paths that the drunk can take is
`
`21 (271 -— 2> _
`
`11. —- 1